On Milgram's construction and the Duke embedding conjectures

2013/03/10 by Sun, Timothy
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1303.2304

Abstract

Milgram constructed a 28-vertex cubic graph of genus 4 that disproved Duke's conjecture relating Betti number to minimum genus. We apply Milgram's method to construct to find graphs of higher genus violating Duke's conjecture, which gives a sharper bound on that relationship. These graphs are also counterexamples to a related conjecture of Nordhaus et al. on the relationship between minimum and maximum genera of graphs. As a side note, we give a simpler proof of correctness for Milgram's method and we show that Duke's conjecture is true for genus at most 3.

Related

• On the Genus Polynomial of Cubic Graphs
• Lower bound on the number of the maximum genus embedding of K_n,n
• Jungerman ladders and index 2 constructions for genus embeddings of dense regular graphs
• The maximum and minimum genus of a multibranched surface
• Polyhedral surfaces of high genus