Classification of planar Deza graphs

2025/04/27 by Maffucci, Riccardo W. · 2 citations
#05C10 #05C35 #05C75 #05C76 #05E30 #52B05 #52B10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.19204

Abstract

We classify the planar Deza graphs. We also classify all regular polyhedra according to their type i.e., the collection of number of common neighbours that any pair of distinct vertices may have (polyhedra are planar, 3-connected graphs). Among the classes of planar Deza graphs is an intriguing wide class of quartic polyhedra. We prove that these are the medial graphs of certain cubic polyhedra. Furthermore, within the aforementioned class of quartic polyhedral Deza graphs, we study the extremal graphs with respect to the ratio of number of triangular faces to the total. In the maximal extreme, we notably obtain the line graphs of cubic polyhedra of girth 5.

Citations

• Common neighbours in planar graphs
• Classification of polyhedral graphs by numbers of common neighbours
• Cancellation and regularity for planar, 3-connected Kronecker products
• q-Analogs of divisible design graphs and Deza graphs
• Generation of 3-connected, planar line graphs
• Classification and Construction of Planar, 3-Connected Kronecker Products
• Strongly regular graphs decomposable into a divisible design graph and a Hoffman coclique
• Rao's Theorem for forcibly planar sequences revisited
• On unigraphic polyhedra with one vertex of degree p-2
• Independence numbers of polyhedral graphs
• Characterising 3-polytopes of radius one with unique realisation
• Self-dual polyhedra of given degree sequence
• Deza graphs: a survey and new results
• On polyhedral graphs and their complements
• Tight gaps in the cycle spectrum of 3-connected planar graphs

Cited by

• Classification of polyhedral graphs by numbers of common neighbours
• Regularity and separation for Sierpiński products of graphs

Related

• Classification of polyhedral graphs by numbers of common neighbours
• The planar cubic Cayley graphs
• Characterizing Graphs of Zonohedra
• Generation of 3-connected, planar line graphs
• The planar cubic Cayley graphs of connectivity 2