Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

A note on domination in bipartite graphs

Tobias GerlachJochen Harant — 2002

Discussiones Mathematicae Graph Theory

DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.

Ordered and linked chordal graphs

Thomas BöhmeTobias GerlachMichael Stiebitz — 2008

Discussiones Mathematicae Graph Theory

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

Page 1

Download Results (CSV)