Existence of dominating cycles and paths
Veldman, H.J. (1983) Existence of dominating cycles and paths. Discrete Mathematics, 43 (23). pp. 281296. ISSN 0012365X

PDF
1MB 
Abstract:  A cycle C of a graph G is called dominating cycle (Dcycle) if every edge of G is incident with at least one vertex of C. A Dpath is defined analogously. If a graph G contains a Dcycle (Dpath), then its edge graph L(G) has a hamiltonian cycle (hamiltonian path). Necessary conditions and sufficient conditions are obtained for graphs to have a Dcycle or Dpath. 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 NashWilliams 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/0012365X(83)901656 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page