Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T05:24:23.201Z Has data issue: false hasContentIssue false

On Spanning and Dominating Circuits in Graphs

Published online by Cambridge University Press:  20 November 2018

L. Lesniak-Foster
Affiliation:
Louisiana State University, Baton Rouge Louisiana 70803 U.S.A.
James E. Williamson
Affiliation:
University of Dubuque, Dubuque Iowa 52001 U.S.A.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1977