Balanced Cayley graphs and balanced planar graphs

2007/07/02 by Joy Morris, Pablo Spiga, Morris, Joy +3
Computer Science · Engineering · #05C99 #05E99 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Structural Analysis and Optimization

paper · pdf · doi:10.48550/arxiv.0707.0155

openalex publication_date 2007/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• The planar cubic Cayley graphs
• Balanced Abelian group valued functions on directed graphs
• 2-nearly Platonic graphs are unique
• On Cayley graphs of algebraic structures
• The planar Cayley graphs are effectively enumerable I: consistently planar graphs