Existence of dominating cycles and paths

H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)
38 Downloads (Pure)

Abstract

A cycle C of a graph G is called dominating cycle (D-cycle) if every edge of G is incident with at least one vertex of C. A D-path is defined analogously. If a graph G contains a D-cycle (D-path), then its edge graph L(G) has a hamiltonian cycle (hamiltonian path). Necessary conditions and sufficient conditions are obtained for graphs to have a D-cycle or D-path. They are analogous to known conditions for the existence of hamiltonian cycles or paths. The notions edge degree and remote edges arise as analogues of vertex degree and nonadjacent vertices, respectively. A result of Nash-Williams is improved.
Original languageEnglish
Pages (from-to)281-296
JournalDiscrete mathematics
Volume43
Issue number2-3
DOIs
Publication statusPublished - 1983

Fingerprint

Dominating Cycle
Hamiltonians
Path
Hamiltonian path
Hamiltonian circuit
Graph in graph theory
Vertex Degree
Analogue
Cycle
Necessary Conditions
Sufficient Conditions
Vertex of a graph

Keywords

  • IR-69205

Cite this

Veldman, H.J. / Existence of dominating cycles and paths. In: Discrete mathematics. 1983 ; Vol. 43, No. 2-3. pp. 281-296.
@article{61e2e5ee11b74b399dce35252434828c,
title = "Existence of dominating cycles and paths",
abstract = "A cycle C of a graph G is called dominating cycle (D-cycle) if every edge of G is incident with at least one vertex of C. A D-path is defined analogously. If a graph G contains a D-cycle (D-path), then its edge graph L(G) has a hamiltonian cycle (hamiltonian path). Necessary conditions and sufficient conditions are obtained for graphs to have a D-cycle or D-path. They are analogous to known conditions for the existence of hamiltonian cycles or paths. The notions edge degree and remote edges arise as analogues of vertex degree and nonadjacent vertices, respectively. A result of Nash-Williams is improved.",
keywords = "IR-69205",
author = "H.J. Veldman",
year = "1983",
doi = "10.1016/0012-365X(83)90165-6",
language = "English",
volume = "43",
pages = "281--296",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "2-3",

}

Existence of dominating cycles and paths. / Veldman, H.J.

In: Discrete mathematics, Vol. 43, No. 2-3, 1983, p. 281-296.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Existence of dominating cycles and paths

AU - Veldman, H.J.

PY - 1983

Y1 - 1983

N2 - A cycle C of a graph G is called dominating cycle (D-cycle) if every edge of G is incident with at least one vertex of C. A D-path is defined analogously. If a graph G contains a D-cycle (D-path), then its edge graph L(G) has a hamiltonian cycle (hamiltonian path). Necessary conditions and sufficient conditions are obtained for graphs to have a D-cycle or D-path. They are analogous to known conditions for the existence of hamiltonian cycles or paths. The notions edge degree and remote edges arise as analogues of vertex degree and nonadjacent vertices, respectively. A result of Nash-Williams is improved.

AB - A cycle C of a graph G is called dominating cycle (D-cycle) if every edge of G is incident with at least one vertex of C. A D-path is defined analogously. If a graph G contains a D-cycle (D-path), then its edge graph L(G) has a hamiltonian cycle (hamiltonian path). Necessary conditions and sufficient conditions are obtained for graphs to have a D-cycle or D-path. They are analogous to known conditions for the existence of hamiltonian cycles or paths. The notions edge degree and remote edges arise as analogues of vertex degree and nonadjacent vertices, respectively. A result of Nash-Williams is improved.

KW - IR-69205

U2 - 10.1016/0012-365X(83)90165-6

DO - 10.1016/0012-365X(83)90165-6

M3 - Article

VL - 43

SP - 281

EP - 296

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 2-3

ER -