Ordered and linked chordal graphs
Thomas Böhme ; Tobias Gerlach ; Michael Stiebitz
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 367-373 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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-edge-ordered (k ≥ 2). (c) G is k-linked if and only if it is (2k-1)-connected.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270596 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1412,
     author = {Thomas B\"ohme and Tobias Gerlach and Michael Stiebitz},
     title = {Ordered and linked chordal graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {367-373},
     zbl = {1156.05029},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1412}
}

Thomas Böhme; Tobias Gerlach; Michael Stiebitz. Ordered and linked chordal graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 367-373. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1412/

[000] [1] B. Bollobás and A. Thomason, Highly linked graphs, Combinatorica 16 (1996) 313-320, doi: 10.1007/BF01261316. | Zbl 0870.05044

[001] [2] R. Diestel, Graph Theory, Graduate Texts in Mathematics 173 (Springer, 2000).

[002] [3] G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776. | Zbl 0098.14703

[003] [4] R.J. Faudree, Survey on results on k-ordered graphs, Discrete Math. 229 (2001) 73-87, doi: 10.1016/S0012-365X(00)00202-8. | Zbl 0967.05041

[004] [5] H.A. Jung, Eine veralgemeinerung des n-fachen zusammenhangs für graphen, Math. Ann. 187 (1970) 95-103, doi: 10.1007/BF01350174. | Zbl 0184.27601

[005] [6] D.G. Larman and P. Mani, On the existence of certain configurations within graphs and the 1-skeleton of polytopes, Proc. London Math. Soc. 20 (1970) 144-160, doi: 10.1112/plms/s3-20.1.144. | Zbl 0201.56801

[006] [7] L. Ng and M. Schultz, k-ordered Hamiltonian graphs, J. Graph Theory 24 (1997) 45-57, doi: 10.1002/(SICI)1097-0118(199701)24:1<45::AID-JGT6>3.0.CO;2-J | Zbl 0864.05062

[007] [8] R. Thomas and P. Wollan, An improved linear edge bound for graph linkages, to appear in European J. Comb. | Zbl 1056.05091