Ordered and linked chordal graphs
Thomas J. Böhme, Tobias Gerlach, Michael Stiebitz · Discussiones Mathematicae Graph Theory · 2008
A graph G is called k-ordered if for every sequence of k distinct vertices there is a cycle traversing these vertices in the given order.In the present paper we consider two novel generalizations of this concept, k-vertex-edge-ordered and strongly k-vertex-edge-ordered .We prove the following results for a chordal graph G: (a) G is (2k -3)-connected if and only if it is k-vertex-edge-ordered (k ≥ 3).(b) G is (2k -1)-connected if and only if it is strongly k-vertex-edgeordered (k ≥ 2).(c) G is k-linked if and only if it is (2k -1)-connected.