Covers, orientations and factors

DOI10.37236/8767MaRDI QIDQ785575zbMATH OpenOpenAlexFDO

Authors Péter Csikvári, András Imolay

Publication date 7 August 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1905.06678

zbMATH Keywords

Eulerian graphsEulerian orientations

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Given a graph $G$ with only even degrees let $varepsilon(G)$ denote the number of Eulerian orientations, and let $h(G)$ denote the number of half graphs, that is, subgraphs $F$ such that $d_F(v)=d_G(v)/2$ for each vertex $v$. Recently, Borb'enyi and Csikv'ari proved that $varepsilon(G)geqh(G)$ holds true for all Eulerian graphs with equality if and and only if $G$ is bipartite. In this paper we give a simple new proof of this fact, and we give identities and inequalities for the number of Eulerian orientations and half graphs of a $2$-cover of a graph $G$.

Review text

Summary: Given a graph \(G\) with only even degrees, let \(\varepsilon(G)\) denote the number of Eulerian orientations, and let \(h(G)\) denote the number of half graphs, that is, subgraphs \(F\) such that \(d_F(v)=d_G(v)/2\) for each vertex \(v\). Recently, \textit{M. Borbényi} and \textit{P. Csikvári} [Discrete Math. 343, No. 6, Article ID 111842, 14 p. (2020; Zbl 1437.05101)] proved that \(\varepsilon(G)\geqslant h(G)\) holds true for all Eulerian graphs, with equality if and only if \(G\) is bipartite. In this paper we give a simple new proof of this fact, and we give identities and inequalities for the number of Eulerian orientations and half graphs of a \(2\)-cover of a graph \(G\).

Recommendations

• A note on the orientation covering number
• Flat covers and factorizations
• Covering numbers of rotations
• scientific article; zbMATH DE number 4019891
• scientific article; zbMATH DE number 763373
• scientific article; zbMATH DE number 7530
• Coverings of configurations, prime configurations, and orbiconfigurations
• scientific article; zbMATH DE number 3880734
• On some covering designs
• scientific article; zbMATH DE number 1241846

Cites work

• A Short Proof of the Factor Theorem for Finite Graphs
• An entropy approach to the hard-core model on bipartite graphs
• Bounds on the number of Eulerian orientations
• Condensed matter physics and exactly soluble models. Selecta of Elliott H. Lieb. Edited by B. Nachtergaele, J. P. Solovej and J. Yngvason
• Counting degree-constrained subgraphs and orientations
• Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• scientific article; zbMATH DE number 742958 (Why is no real title available?)
• Independent sets in regular graphs and sum-free subsets of finite groups
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Lifts, discrepancy and nearly optimal spectral gap
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• On the expansion of group-based lifts
• On the number of matchings in regular graphs
• On the number of perfect matchings in random lifts
• Shattering, graph orientations, and connectivity
• The number of independent sets in a regular graph

This page was built for publication: Covers, orientations and factors

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