Stable dominating circuits in snarks

DOI10.1016/S0012-365X(00)00244-2MaRDI QIDQ5936035zbMATH OpenOpenAlexFDO

Authors Martin Kochol

Publication date 3 June 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00244-2

zbMATH Keywords

cycle double coverdominating circuitsnarkstable circuit

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

A snark is a cyclically 4-edge-connected, 3-valent graph with girth at least 5 that admits no 3-edge-coloring. A circuit \(C\) is said to be stable if no other circuit \(C'\) satisfies \(V(C)\subseteq V(C')\). \textit{H. Fleischner} proved in [J. Graph Theory 18, No. 5, 449-459 (1994; Zbl 0807.05050)] the equivalence of G. Sabidussi's ``compatibility conjecture with the conjecture that in a 3-valent graph \(G\), given any dominating circuit \(C\) (i.e., every edge of \(G\) is incident with some vertex of \(C\)), there exists a cycle double cover of \(G\) that includes \(C\). In the present paper it is shown that any smallest counterexample \(G\) to these conjectures must be a snark and an offending dominating cycle \(C\) must be stable. It is then shown by a construction that such structures \((G,C)\) indeed exist. In fact, for every even \(n\geq 82\), there exists a snark of order \(n\) having a stable dominating circuit.

Recommendations

• Self-Stabilizing Domination Algorithms
• Domination stability in graphs
• A note about the dominating circuit conjecture
• On dominating and spanning circuits in graphs
• Total domination stability in graphs
• Efficient domination in circulant graphs
• Semi square stable graphs and efficient dominating sets
• Dominating circuits in regular matroids
• scientific article; zbMATH DE number 1275900
• Domination in circulant graphs

Cited in

(11)

• A note on semiextensions of stable circuits
• Superposition and constructions of graphs without nowhere-zero k-flows
• Equivalence of Jackson's and Thomassen's conjectures
• Cycle double covers in cubic graphs having special structures
• Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks
• Circuit extension and circuit double cover of graphs
• On stable cycles and cycle double covers of graphs with large circumference
• Generation and properties of snarks
• Circuit double covers of graphs
• On semiextensions and circuit double covers
• Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks

This page was built for publication: Stable dominating circuits in snarks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936035)