Name
Abstract | ||
|---|---|---|
An eulerian subgraph of a graph is called a circuit. As shown by Harary and Nash-Williams, the existence of a Hamilton cycle in the line graph L ( G ) of a graph G is equivalent to the existence of a dominating circuit in G , i.e., a circuit such that every edge of G is incident with a vertex of the circuit. Important progress in the study of the existence of spanning and dominating circuits was made by Catlin, who defined the reduction of a graph G and showed that G has a spanning circuit if and only if the reduction of G has a spanning circuit. We refine Catlin's reduction technique to obtain a result which contains several known and new sufficient conditions for a graph to have a spanning or dominating circuit in terms of degree-sums of adjacent vertices. In particular, the result implies the truth of the following conjecture of Benhocine et al.: If G is a connected simple graph of order n such that every cut edge of G is incident with a vertex of degree 1 and d(u) + d(v) > 2( 1 5 n – 1) for every edge uv of G , then, for n sufficiently large, L ( G ) is hamiltonian. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0012-365X(92)00063-W | Discrete Mathematics |
Keywords | Field | DocType |
hamilton cycle,line graph | Discrete mathematics,Combinatorics,Loop (graph theory),Bound graph,Graph power,Graph factorization,Cycle graph,Neighbourhood (graph theory),Spanning tree,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
124 | 1 | Discrete Mathematics |
Citations | PageRank | References |
10 | 0.96 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. J. Veldman | 1 | 262 | 44.44 |