A Note on Graphs of Linear Rank-Width 1
2013
Online
report
Zugriff:
We prove that a connected graph has linear rank-width 1 if and only if it is a distance-hereditary graph and its split decomposition tree is a path. An immediate consequence is that one can decide in linear time whether a graph has linear rank-width at most 1, and give an obstruction if not. Other immediate consequences are several characterisations of graphs of linear rank-width 1. In particular a connected graph has linear rank-width 1 if and only if it is locally equivalent to a caterpillar if and only if it is a vertex-minor of a path [O-joung Kwon and Sang-il Oum, Graphs of small rank-width are pivot-minors of graphs of small tree-width, arxiv:1203.3606] if and only if it does not contain the co-K_2 graph, the Net graph and the 5-cycle graph as vertex-minors [Isolde Adler, Arthur M. Farley and Andrzej Proskurowski, Obstructions for linear rank-width at most 1, arxiv:1106.2533].
Comment: 9 pages, 2 figures. Not to be published
Titel: |
A Note on Graphs of Linear Rank-Width 1
|
---|---|
Autor/in / Beteiligte Person: | Bui-Xuan, Binh-Minh ; Kanté, Mamadou Moustapha ; Limouzy, Vincent |
Link: | |
Veröffentlichung: | 2013 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|