Ordered and linked chordal graphs
Thomas Böhme; Tobias Gerlach; Michael Stiebitz
Discussiones Mathematicae Graph Theory (2008)
- Volume: 28, Issue: 2, page 367-373
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topThomas Böhme, Tobias Gerlach, and Michael Stiebitz. "Ordered and linked chordal graphs." Discussiones Mathematicae Graph Theory 28.2 (2008): 367-373. <http://eudml.org/doc/270596>.
@article{ThomasBöhme2008,
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) 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.
},
author = {Thomas Böhme, Tobias Gerlach, Michael Stiebitz},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {paths and cycles; connectivity; chordal graphs},
language = {eng},
number = {2},
pages = {367-373},
title = {Ordered and linked chordal graphs},
url = {http://eudml.org/doc/270596},
volume = {28},
year = {2008},
}
TY - JOUR
AU - Thomas Böhme
AU - Tobias Gerlach
AU - Michael Stiebitz
TI - Ordered and linked chordal graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 2
SP - 367
EP - 373
AB -
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.
LA - eng
KW - paths and cycles; connectivity; chordal graphs
UR - http://eudml.org/doc/270596
ER -
References
top- [1] B. Bollobás and A. Thomason, Highly linked graphs, Combinatorica 16 (1996) 313-320, doi: 10.1007/BF01261316. Zbl0870.05044
- [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. Zbl0098.14703
- [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. Zbl0967.05041
- [5] H.A. Jung, Eine veralgemeinerung des n-fachen zusammenhangs für graphen, Math. Ann. 187 (1970) 95-103, doi: 10.1007/BF01350174. Zbl0184.27601
- [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. Zbl0201.56801
- [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 Zbl0864.05062
- [8] R. Thomas and P. Wollan, An improved linear edge bound for graph linkages, to appear in European J. Comb. Zbl1056.05091
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.