Balanced Cayley graphs and balanced planar graphs

DOI10.1016/J.DISC.2009.11.002MaRDI QIDQ712243zbMATHOpenAlexFDO

Authors Joy Morris, Pablo Spiga, Kerri Webb

Publication date 28 October 2010

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphbalanced graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: A balanced graph is a bipartite graph with no induced circuit of length 2 mod 4. These graphs arise in linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in Section 5 of this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented.

Recommendations

• On balanced Cayley maps over abelian groups
• scientific article; zbMATH DE number 125598
• Regular maps from Cayley graphs. I: Balanced Cayley maps
• The planar cubic Cayley graphs
• Regular maps from Cayley graphs. III: \(t\)-balanced Cayley maps

Cites work

• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• A Class of Balanced Matrices Arising from Location Problems
• A survey: Hamiltonian cycles in Cayley graphs
• Balanced matrices
• Balanced matrices
• Combinatorial optimization. Packing and covering
• Decomposition of balanced matrices
• Inductive definition of two restricted classes of triangulations
• Lifting Hamilton cycles of quotient graphs
• Pancyclicity of connected circulant graphs
• Perfect Elimination and Chordal Bipartite Graphs

Cited in

(3)

• CFI Construction and Balanced Graphs
• Linear balanceable and subcubic balanceable graphs
• Balanced 3-nearly Platonic graphs

Describes a project that uses

Uses Software

• GAP

This page was built for publication: Balanced Cayley graphs and balanced planar graphs

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