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