# Ordered and linked chordal graphs

• Volume: 28, Issue: 2, page 367-373
• ISSN: 2083-5892

top

## Abstract

top
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.

## How to cite

top

Thomas 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. [1] B. Bollobás and A. Thomason, Highly linked graphs, Combinatorica 16 (1996) 313-320, doi: 10.1007/BF01261316. Zbl0870.05044
2. [2] R. Diestel, Graph Theory, Graduate Texts in Mathematics 173 (Springer, 2000).
3. [3] G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776. Zbl0098.14703
4. [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. [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. [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. [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. [8] R. Thomas and P. Wollan, An improved linear edge bound for graph linkages, to appear in European J. Comb. Zbl1056.05091

## NotesEmbed?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.