Ordered and linked chordal graphs | Zendy

Thomas Böhme | Zendy; Tobias Gerlach | Zendy; Michael Stiebitz | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Ordered and linked chordal graphs

Author(s) -

Thomas Böhme,

Tobias Gerlach,

Michael Stiebitz

Publication year - 2008

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1412

Subject(s) - combinatorics , mathematics , chordal graph , vertex (graph theory) , neighbourhood (mathematics) , graph , discrete mathematics , mathematical analysis

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research