2013/06/06 by Binh-Minh Bui-Xuan, Bui-Xuan, Binh-Minh, Mamadou Moustapha Kanté +3
Computer Science · Mathematics · #05C75 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.0 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #acm:05C75 #acm:68R10 #cs.DM #cs.DS #math.CO #msc:05C75 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1306.1345
9 pages, 2 figures. Not to be published
arxiv created 2014/07/08 · arxiv updated 2014/07/09
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-K2 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].