2026/07/28 by Austin Ulrigg
#math.CO
The orientable genus polynomial of a graph counts its cellular embeddings by genus. For finite simple 2-connected cubic graphs it is a cycle-matroid invariant: M(G)≅ M(H) implies ΓG=ΓH. The adjacency spectrum and the genus polynomial are incomparable: neither determines the other. We exhibit connected cubic graphs on 16 vertices sharing the adjacency spectrum, spanning-tree count, girth, diameter, vertex and edge connectivity, automorphism-group order, and cycle counts through length 10, yet with pairwise distinct genus polynomials. Splitting the expected face count at twice the girth explains the difference: short faces are spectral, long faces are not. We construct an explicit infinite family of connected cospectral cubic pairs (Gt,Ht) on 14+2t vertices whose minimum genera differ. We also compute the genus polynomials of all 7,875,918 connected cubic graphs through 22 vertices and derive from short-cycle counts a deterministic lower bound on the minimum genus.