Balanced Cayley graphs and balanced planar graphs

DOI10.1016/J.DISC.2009.11.002zbMATH Open1221.05203arXiv0707.0155OpenAlexW2028666977MaRDI QIDQ712243FDOQ712243

Joy Morris, Kerri Webb, Pablo Spiga

Publication date: 28 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Packing and covering
• Perfect Elimination and Chordal Bipartite Graphs
• Decomposition of balanced matrices
• A survey: Hamiltonian cycles in Cayley graphs
• Balanced matrices
• Inductive definition of two restricted classes of triangulations
• Balanced matrices
• Lifting Hamilton cycles of quotient graphs
• Pancyclicity of connected circulant graphs
• A Class of Balanced Matrices Arising from Location Problems

Cited In (2)

• Linear balanceable and subcubic balanceable graphs
• CFI Construction and Balanced Graphs

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)