Geodesic
On Spanning and Dominating Circuits in Graphs
Canadian mathematical bulletin, Tome 20 (1977) no. 2, pp. 215-220

Voir la notice de l'article provenant de la source Cambridge University Press

A set E of edges of a graph G is said to be a dominating set of edges if every edge of G either belongs to E or is adjacent to an edge of E. If the subgraph 〈E〉 induced by E is a trail T, then T is called a dominating trail of G. Dominating circuits are defined analogously. A sufficient condition is given for a graph to possess a spanning (and thus dominating) circuit and a sufficient condition is given for a graph to possess a spanning (and thus dominating) trail between each pair of distinct vertices. The line graph L(G) of a graph G is defined to be that graph whose vertex set can be put in one-to-one correspondence with the edge set of G in such a way that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. The existence of dominating trails and circuits is employed to present results on line graphs and second iterated line graphs, respectively.
DOI : 10.4153/CMB-1977-034-8
Mots-clés : 05C35, Dominating trail, dominating circuit, spanning trail, spanning circuit, hamiltonian path, hamiltonian cycle, hamiltonian graph, line graph 
Lesniak-Foster, L.; Williamson, James E. On Spanning and Dominating Circuits in Graphs. Canadian mathematical bulletin, Tome 20 (1977) no. 2, pp. 215-220. doi: 10.4153/CMB-1977-034-8
@article{10_4153_CMB_1977_034_8,
     author = {Lesniak-Foster, L. and Williamson, James E.},
     title = {On {Spanning} and {Dominating} {Circuits} in {Graphs}},
     journal = {Canadian mathematical bulletin},
     pages = {215--220},
     year = {1977},
     volume = {20},
     number = {2},
     doi = {10.4153/CMB-1977-034-8},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1977-034-8/}
}
TY  - JOUR
AU  - Lesniak-Foster, L.
AU  - Williamson, James E.
TI  - On Spanning and Dominating Circuits in Graphs
JO  - Canadian mathematical bulletin
PY  - 1977
SP  - 215
EP  - 220
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1977-034-8/
DO  - 10.4153/CMB-1977-034-8
ID  - 10_4153_CMB_1977_034_8
ER  - 
%0 Journal Article
%A Lesniak-Foster, L.
%A Williamson, James E.
%T On Spanning and Dominating Circuits in Graphs
%J Canadian mathematical bulletin
%D 1977
%P 215-220
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1977-034-8/
%R 10.4153/CMB-1977-034-8
%F 10_4153_CMB_1977_034_8

[1] 1. Behzad, M. and Chartrand, G., Introduction to the Theory of Graphs. Allyn and Bacon, Boston (1972). Google Scholar

[2] 2. Chartrand, G. and Wall, C. E., On the hamiltonian index of a graph. Studia Sci. Math. Hungar. 8 (1973), 43-48. Google Scholar

[3] 3. Harary, F. and Nash-Williams, C. St. J. A., On eulerian and hamiltonian graphs and line graphs. Canad. Math. Bull. 8 (1965), 701-710. Google Scholar

[4] 4. Ore, O., Note on Hamilton circuits. Amer. Math. Monthly. 67 (1960), 55. Google Scholar

Cité par Sources :