Balanced Cayley graphs and balanced planar graphs
Authors:
Preprint
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Lifting Hamilton cycles of quotient graphsDiscrete Mathematics, 1989
- A survey: Hamiltonian cycles in Cayley graphsDiscrete Mathematics, 1984
- Inductive definition of two restricted classes of triangulationsDiscrete Mathematics, 1984
- A Class of Balanced Matrices Arising from Location ProblemsSIAM Journal on Algebraic Discrete Methods, 1983
- On balanced matrices1974