Existence of dominating cycles and paths

H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

30 Citations (Scopus)
98 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

Keywords

  • IR-69205

Fingerprint

Dive into the research topics of 'Existence of dominating cycles and paths'. Together they form a unique fingerprint.

Cite this