Discussiones Mathematicae Graph Theory 28(2) (2008)
367-373
DOI: https://doi.org/10.7151/dmgt.1412
ORDERED AND LINKED CHORDAL GRAPHS
Thomas Böhme, Tobias Gerlach and Michael Stiebitz
Institut für Mathematik
Technische Universität Ilmenau
Ilmenau, Germany
e-mail: | tboehme@theoinf.tu-ilmenau.de |
e-mail: | tobias.gerlach@tu-ilmenau.de |
e-mail: | stieb@mathematik.tu-ilmenau.de |
Abstract
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)
|
(b)
|
(c)
|
Keywords: paths and cycles, connectivity, chordal graphs.
2000 Mathematics Subject Classification: 05C38, 05C40.
References
[1] | B. Bollobás and A. Thomason, Highly linked graphs, Combinatorica 16 (1996) 313-320, doi: 10.1007/BF01261316. |
[2] | R. Diestel, Graph Theory, Graduate Texts in Mathematics 173 (Springer, 2000). |
[3] | G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776. |
[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. |
[5] | H.A. Jung, Eine veralgemeinerung des n-fachen zusammenhangs für graphen, Math. Ann. 187 (1970) 95-103, doi: 10.1007/BF01350174. |
[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. |
[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. |
[8] | R. Thomas and P. Wollan, An improved linear edge bound for graph linkages, to appear in European J. Comb. |
Received 20 September 2007
Revised 1 April 2008
Accepted 2 April 2008
Close