A note on graphs of linear rank-width 1

Abstract. 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, to appear in Discrete Applied Mathe-matics] 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 An-drzej Proskurowski, Obstructions for linear rank-width at most 1, to appea