### Abstract

Original language | English |
---|---|

Pages (from-to) | 281-296 |

Journal | Discrete mathematics |

Volume | 43 |

Issue number | 2-3 |

DOIs | |

Publication status | Published - 1983 |

### Fingerprint

### Keywords

- IR-69205

### Cite this

*Discrete mathematics*,

*43*(2-3), 281-296. https://doi.org/10.1016/0012-365X(83)90165-6

}

*Discrete mathematics*, vol. 43, no. 2-3, pp. 281-296. https://doi.org/10.1016/0012-365X(83)90165-6

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

Research output: Contribution to journal › Article › Academic › peer-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 -