Recharacterizing Eulerian: Intimations of new duality
type: Item
instance of: scholarly article
title: Recharacterizing Eulerian: Intimations of new duality
zbMATH Open document ID: 0547.05043
DOI: 10.1016/0012-365X(84)90004-9
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 3871405
zbMATH Keywords: Eulerian graphs
zbMATH Keywords: binary matroids
author: Terry A. McKee
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: A quantifier for matroid duality
cites work: Duality principles for binary matroids and graphs
cites work: Logical Aspects of Combinatorial Duality
cites work: Properties of a Euler graph
cites work: Q5661516
Recommended article: Q3679897
Recommended article: The Euler line revisited
Recommended article: Dualization of the Euler and Hamiltonian inclusions
Recommended article: The Newton complementary dual revisited
Recommended article: On Euler-Lagrange’s Equations: A New Approach
Recommended article: A note on reparametrizations of the Euler equations
Recommended article: Q3223643
Recommended article: Euler Diagrams Through the Looking Glass: From Extent to Intent
Recommended article: The structure of the Euler-Lagrange mapping
description: scientific article; zbMATH DE number 3871405