On Eulerian and Hamiltonian Graphs and Line Graphs

DOI10.4153/CMB-1965-051-3zbMath0136.44704OpenAlexW2005906639MaRDI QIDQ5509542

C. St. J. A. Nash-Williams, Frank Harary

Publication date: 1965

Published in: Canadian Mathematical Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4153/cmb-1965-051-3

zbMATH Keywords

topology

Related Items

Circumferences of 3-connected claw-free graphs. II. ⋮ Hamiltonian line graphs with local degree conditions ⋮ Claw-free 3-connectedP11-free graphs are hamiltonian ⋮ Maximal K3's and Hamiltonicity of 4-connected claw-free graphs ⋮ Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs. II ⋮ Updating the hamiltonian problem—A survey ⋮ On the \(s\)-hamiltonianicity of an hourglass-free line graph ⋮ Every 3-connected claw-free graph with domination number at most 3 is Hamiltonian-connected ⋮ A note on 3-connected hourglass-free claw-free Hamilton-connected graphs ⋮ Hamilton cycles in line graphs of 3-hypergraphs ⋮ Existence of spanning and dominating trails and circuits ⋮ On spanning disjoint paths in line graphs ⋮ Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs ⋮ On the hamiltonicity of line graphs of locally finite, 6-edge-connected graphs ⋮ Hamiltonicity and forbidden subgraphs in 4‐connected graphs ⋮ On line graphs of subcubic triangle-free graphs ⋮ Hamiltonian paths in spanning subgraphs of line graphs ⋮ Supereulerian graphs with constraints on the matching number and minimum degree ⋮ Cycles through all finite vertex sets in infinite graphs ⋮ A characterization of 2-connected \(\{ K_{1 , 3} , N_{3 , 1 , 1} \}\)-free non-Hamiltonian graphs ⋮ On circuits and pancyclic line graphs ⋮ Degree and neighborhood conditions for Hamiltonicity of claw-free graphs ⋮ Branch-bonds, two-factors in iterated line graphs and circuits in weighted graphs ⋮ Supereulerian graphs with small matching number and 2-connected hamiltonian claw-free graphs ⋮ Polynomially determining spanning connectivity of locally connected line graphs ⋮ Supereulerian graphs: A survey ⋮ Thomassen's conjecture for line graphs of 3-hypergraphs ⋮ Forbidden subgraphs on Hamiltonian index ⋮ A note on singular edges and Hamiltonicity in claw-free graphs with locally disconnected vertices ⋮ On sufficient degree conditions for traceability of claw-free graphs ⋮ Parameterized edge Hamiltonicity ⋮ Asymptotically sharpening the $s$-Hamiltonian index bound ⋮ Hamilton‐connected {claw,net}‐free graphs, II ⋮ On hamiltonian line graphs of hypergraphs ⋮ Forbidden pairs of disconnected graphs for 2‐factor of connected graphs ⋮ Hamilton‐connected {claw, bull}‐free graphs ⋮ Hamilton‐connected {claw, net}‐free graphs, I ⋮ On pancyclic line graphs ⋮ Unnamed Item ⋮ On computing the Hamiltonian index of graphs ⋮ Chvátal-Erdős conditions and almost spanning trails ⋮ On eulerian subgraphs of complementary graphs ⋮ A result on Hamiltonian line graphs involving restrictions on induced subgraphs ⋮ Hamiltonian claw-free graphs involving minimum degrees ⋮ Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs ⋮ On \(s\)-Hamiltonicity of net-free line graphs ⋮ On the line graph of a graph with diameter 2 ⋮ Contractions and hamiltonian line graphs ⋮ 3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian ⋮ Degree sums and dominating cycles ⋮ Extending perfect matchings to Hamiltonian cycles in line graphs ⋮ On the 2-factor index of a graph ⋮ A reduction method to find spanning Eulerian subgraphs ⋮ Spanning trails ⋮ Hamilton connectivity of line graphs and claw‐free graphs ⋮ Multigraphic degree sequences and Hamiltonian-connected line graphs ⋮ Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ On factors of 4-connected claw-free graphs ⋮ On hamiltonian line graphs ⋮ Hamiltonian results inK1,3-free graphs ⋮ On stability of the hamiltonian index under contractions and closures ⋮ Forbidden subgraphs that imply 2-factors ⋮ On Forbidden Pairs Implying Hamilton‐Connectedness ⋮ A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs ⋮ Forbidden Subgraphs for Hamiltonicity of 3-Connected Claw-Free Graphs ⋮ Regular graphs with given girth pair ⋮ Lai's conditions for spanning and dominating closed trails ⋮ HamiltonianN2-locally connected claw-free graphs ⋮ Subpancyclicity of line graphs and degree sums along paths ⋮ Hamiltonicity in 3-connected claw-free graphs ⋮ Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs ⋮ Hamilton cycles and closed trails in iterated line graphs ⋮ Every 3‐connected claw‐free Z ₈ ‐free graph is Hamiltonian ⋮ 2-connected Hamiltonian claw-free graphs involving degree sum of adjacent vertices ⋮ Graph theory ⋮ Supereulerian graphs with small circumference and 3-connected Hamiltonian claw-free graphs ⋮ Hamiltonian line graphs ⋮ Hamilton circuits and essential girth of claw free graphs ⋮ Every 4-connected line graph of a quasi claw-free graph is Hamiltonian connected ⋮ The Nash-Williams conjecture and the dominating cycle conjecture ⋮ On the independence number of traceable 2-connected claw-free graphs ⋮ Ein Struktursatz für 2-fach zusammenhängende Graphen mit großer Minimalvalenz ⋮ Pancyclic and panconnected line graphs ⋮ On \(s\)-Hamiltonian line graphs of claw-free graphs ⋮ Spanning trails in a 2-connected graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hamilton cycles in 6-connected claw-free graphs (Extended abstract) ⋮ The local structure of claw-free graphs without induced generalized bulls ⋮ Catlin’s reduced graphs with small orders ⋮ Ons-Hamiltonian Line Graphs ⋮ Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs ⋮ Circumferences and Minimum Degrees in 3-Connected Claw-Free Graphs ⋮ Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks ⋮ Equivalence of Jackson's and Thomassen's conjectures ⋮ Hamiltonian claw-free graphs with locally disconnected vertices ⋮ Graphs with the unique path property: Structure, cycles, factors, and constructions ⋮ Unnamed Item ⋮ A note on minimum degree conditions for supereulerian graphs ⋮ Circumferences of 3-connected claw-free graphs ⋮ The Hamiltonian index of a graph and its branch-bonds ⋮ A twelve vertex theorem for 3-connected claw-free graphs ⋮ Every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected ⋮ A simple upper bound for the hamiltonian index of a graph ⋮ A note on edge-disjoint Hamilton cycles in line graphs ⋮ Hamiltonian claw-free graphs and \(o\)-heavy graphs involving induced cycles ⋮ Hamiltonian cycles in spanning subgraphs of line graphs ⋮ Closure for \(\{K_{1,4},K_{1,4} + e\}\)-free graphs ⋮ Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs ⋮ On the Hamiltonian index ⋮ On pancyclic line graphs ⋮ Subgraph distances in graphs defined by edge transfers ⋮ The Chvátal-Erdős condition and pancyclic line-graphs ⋮ Graphs with maximal induced matchings of the same size ⋮ Minimum degree conditions for the Hamiltonicity of 3-connected claw-free graphs ⋮ Contractions of graphs with no spanning Eulerian subgraphs ⋮ Hamiltonicity of complements of middle graphs ⋮ Supereulerian graphs, independent sets, and degree-sum conditions ⋮ Eulerian subgraphs containing given vertices and hamiltonian line graphs ⋮ Every 3-connected \(\{K_{1,3},N_{3,3,3}\}\)-free graph is Hamiltonian ⋮ On the hamiltonian index and the radius of a graph ⋮ Hamiltonicity of 6-connected line graphs ⋮ Circumferences of 2-factors in claw-free graphs ⋮ Reconstructing a graph from its arc incidence graph ⋮ \(s\)-vertex pancyclic index ⋮ On 1-Hamilton-connected claw-free graphs ⋮ On Hamiltonicity of 2-connected claw-free graphs ⋮ Induced hourglass and the equivalence between Hamiltonicity and supereulerianity in claw-free graphs ⋮ On spanning tree packings of highly edge connected graphs ⋮ Hamilton cycles in 5-connected line graphs ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ On line graphs and the Hamiltonian index ⋮ Hamiltonian index is NP-complete ⋮ A lower bound on the Hamiltonian path completion number of a line graph ⋮ On 3-connected Hamiltonian line graphs ⋮ Closure, clique covering and degree conditions for Hamilton-connectedness in claw-free graphs ⋮ A note on collapsible graphs and super-Eulerian graphs ⋮ Degree sum and Hamiltonian-connected line graphs ⋮ Multigraphic degree sequences and supereulerian graphs, disjoint spanning trees ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Existence of dominating cycles and paths ⋮ 2-factors and independent sets on claw-free graphs ⋮ Hamiltonicity of claw-free graphs and Fan-type conditions ⋮ How many conjectures can you stand? A survey ⋮ Spanning connectivity of the power of a graph and Hamilton-connected index of a graph ⋮ 2-factors in claw-free graphs with lower bounds cycle lengths ⋮ On traceable line graphs ⋮ On \(s\)-Hamiltonian-connected line graphs ⋮ Collapsible graphs and Hamilton cycles of line graphs ⋮ The \(s\)-Hamiltonian index ⋮ Hamiltonicity in claw-free graphs ⋮ The Chvátal-Erdős condition for a graph to have a spanning trail ⋮ Chvátal-Erdős type conditions for Hamiltonicity of claw-free graphs ⋮ Pairs of forbidden subgraphs and 2-connected supereulerian graphs ⋮ Hamiltonian properties of 3-connected \{claw,hourglass\}-free graphs ⋮ DNA origami and the complexity of Eulerian circuits with turning costs ⋮ Hamiltonian jump graphs ⋮ Eulerian subgraphs and Hamilton-connected line graphs ⋮ The spanning connectivity of line graphs ⋮ On n-hamiltonian line graphs ⋮ Traversability and connectivity of the middle graph of a graph ⋮ The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index ⋮ Every 3-connected \(\{ K_{1 , 3} , Z_7 \}\)-free graph of order at least 21 is Hamilton-connected ⋮ Generalizations of line graphs and applications ⋮ Minimum number of components of 2-factors in iterated line graphs ⋮ An \(s\)-Hamiltonian line graph problem ⋮ Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks ⋮ The hamiltonian index of a 2-connected graph ⋮ Degree sequence and supereulerian graphs ⋮ Radius and subpancyclicity in line graphs ⋮ The Hamiltonian index of graphs ⋮ Induced nets and Hamiltonicity of claw-free graphs ⋮ Spanning trails in essentially 4-edge-connected graphs ⋮ On Hamiltonicity of 3-connected claw-free graphs ⋮ Edge-connectivity and edge-disjoint spanning trees ⋮ \(k\)-ordered hamiltonicity of iterated line graphs ⋮ Circumferences and minimum degrees in 3-connected claw-free graphs ⋮ Collapsible graphs and reductions of line graphs ⋮ Supereulerian line graphs ⋮ \( 1 / 2\)-conjectures on the domination game and claw-free graphs ⋮ Hamiltonian connectedness in 3-connected line graphs ⋮ On the extended Clark-Wormold Hamiltonian-like index problem ⋮ Traceability of line graphs ⋮ The supereulerian graphs in the graph family \(C(l,k)\) ⋮ Hamiltonicity in vertex envelopes of plane cubic graphs ⋮ Hamilton-connected indices of graphs ⋮ Closure, stability and iterated line graphs with a 2-factor ⋮ Pancyclicity of hamiltonian line graphs ⋮ Edge degree conditions for subpancyclicity in line graphs ⋮ Complete family reduction and spanning connectivity in line graphs ⋮ Hamiltonicity and minimum degree in 3-connected claw-free graphs ⋮ Finding minimum dominating cycles in permutation graphs ⋮ On hamiltonian line graphs and connectivity ⋮ On the dominating (induced) cycles of iterated line graphs ⋮ On dominating and spanning circuits in graphs ⋮ On the hamiltonian index of a graph ⋮ A condition on Hamilton-connected line graphs ⋮ Spanning trails containing given edges