Back to University of Twente portal
Existence of dominating cycles and paths
Veldman, H.J. (1983) Existence of dominating cycles and paths. Discrete Mathematics, 43 (2-3). pp. 281-296. ISSN 0012-365X
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 1190Kb |
| 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. |
| Item Type: | Article |
| Copyright: | © 1983 Elsevier Science |
| Link to this item: | http://purl.utwente.nl/publications/69205 |
| Official URL: | http://dx.doi.org/10.1016/0012-365X(83)90165-6 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page