Recharacterizing Eulerian: Intimations of new duality

DOI10.1016/0012-365X(84)90004-9MaRDI QIDQ798673zbMATH OpenFDO

Authors Terry A. McKee

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(84)90004-9

zbMATH Keywords

binary matroidsEulerian graphs

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75)

Review text

A new characterization of Eulerian graphs is presented. It is formulated generally in terms of binary matroids. The edge-disjoint unions of circuits (or of cutsets) are called circs (or segs respectively). The set of all circs in a given binary matroid is denoted by \({\mathcal C}^+\), the set of all segs by \({\mathcal D}^+\). The symbol \(R_ e\), where e is an edge, denotes the set consisting of e and all edges x with the property that the number of circuits which contain both e and x is odd. Theorem. The following are equivalent for all binary matroids: (i) Each \(R_ e\) meets each seg evenly. (ii) Each \(R_ e\) is a circ. (iii) Every edge is contained in an odd number of circuits. (iv) Every cutset contains an even number of edges. This theorem has four corollaries; we quote three of them. Corollar 1. A connected graph is Eulerian if and only if each edge is in an odd number of circuits. Corollary 2. A connected graph is Eulerian if and only if for every edge e the set \(R_ e\) of edges induces a subgraph with Eulerian components. Corollary 3. A graph is bipartite if and only if every edge is in an odd number of cutsets.

Recommendations

• scientific article; zbMATH DE number 3901630
• The Euler line revisited
• Dualization of the Euler and Hamiltonian inclusions
• The Newton complementary dual revisited
• On Euler-Lagrange’s Equations: A New Approach
• A note on reparametrizations of the Euler equations
• scientific article; zbMATH DE number 3890468
• Euler Diagrams Through the Looking Glass: From Extent to Intent
• The structure of the Euler-Lagrange mapping

Cites work

• A quantifier for matroid duality
• Duality principles for binary matroids and graphs
• scientific article; zbMATH DE number 3394154 (Why is no real title available?)
• Logical Aspects of Combinatorial Duality
• Properties of a Euler graph

Cited in

(20)

• The structure of even factors in claw-free graphs
• Elementary proofs of (relatively) recent characterizations of Eulerian graphs
• Bipartite and Eulerian minors
• A proof of McKee's Eulerian-bipartite characterization
• The Hamiltonian index of a graph and its branch-bonds
• Cycles containing all the odd-degree vertices
• On the 2-factor index of a graph
• Characterizations of postman sets
• Some results in an Eulerian graph
• Parity equivalence in eulerian graphs
• Framed 4-graphs: Euler tours, Gauss circuits and rotating circuits
• The Dominating Circuit Conjecture and Subgraphs of Essentially 4-Edge Connected Cubic Graphs
• Eulerian and bipartite orientable matroids
• scientific article; zbMATH DE number 1790583 (Why is no real title available?)
• scientific article; zbMATH DE number 4114670 (Why is no real title available?)
• scientific article; zbMATH DE number 2230195 (Why is no real title available?)
• New characterizations of Eulerian and bipartite binary matroids
• Partition-based construction and stability analysis of Euler graphs using vertex strength
• Even poset and a parity result for binary linear code
• A note on the dominating circuit conjecture and subgraphs of essentially 4-edge-connected cubic graphs

This page was built for publication: Recharacterizing Eulerian: Intimations of new duality

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