Elementary proofs of (relatively) recent characterizations of Eulerian graphs

DOI10.1016/0166-218X(92)90277-HMaRDI QIDQ1124607zbMATH OpenFDO

Authors Herbert Fleischner

Publication date 1989

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(92)90277-H

zbMATH Keywords

characterizationsEulerian graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Review text

Toida showed that if a graph is Eulerian, then each edge belongs to an odd number of cycles. McKee established the converse of this implication using matroid theory. Shank used properties of binary vector spaces to show that a connected graph G is Eulerian if and only if the number of subsets of E(G) each of which is contained in a spanning tree of G, is odd. The author provides in this paper graph theoretical proofs of these results.

Recommendations

• A proof of McKee's Eulerian-bipartite characterization
• Recharacterizing Eulerian: Intimations of new duality
• scientific article; zbMATH DE number 5016710
• A characterization of binary Eulerian matroids
• New characterizations of Eulerian and bipartite binary matroids

Cites work

• Graph theory
• scientific article; zbMATH DE number 3675922 (Why is no real title available?)
• Parity theorems for paths and cycles in graphs
• Properties of a Euler graph
• Recharacterizing Eulerian: Intimations of new duality

Cited in

(8)

• A proof of McKee's Eulerian-bipartite characterization
• Cycles containing all the odd-degree vertices
• Tosha-degree of an edge in a graph
• Characterizations of postman sets
• Some results in an Eulerian graph
• scientific article; zbMATH DE number 4150213 (Why is no real title available?)
• Even poset and a parity result for binary linear code
• A short constructive proof of the Erdős-Gallai characterization of graphic lists

This page was built for publication: Elementary proofs of (relatively) recent characterizations of Eulerian graphs

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