Given a graph G, its genus polynomial is <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_754_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="167" /> </InlineMediaObject> <EquationSource Format="TEX">$\Gamma _G(x) = \sum _{k\ge 0} g_k(G)x^k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Γ</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mo>∑</mo> <mrow> <mi>k</mi> <mo>≥</mo> <mn>0</mn> </mrow> </msub> <msub> <mi>g</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>x</mi> <mi>k</mi> </msup> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_754_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$g_k(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>g</mi> <mi>k</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the number of two-cell embeddings of G in an orientable surface of genus k. The Log-Concavity Genus Distribution (LCGD) Conjecture states that the genus polynomial of every graph is log-concave. It was further conjectured by Stahl that the genus polynomial of every graph has only real roots, however, this was later disproved. We identify several examples of cubic graphs whose genus polynomials, in addition to having at least one non-real root, have a quadratic factor that is non-log-concave when factored over the real numbers.

Genus Polynomials of Cubic Graphs with Non-real Roots

期刊论文
发表日期：

2025年4月3日

查看全文

MacKenzie Carr,
Varpreet Dhaliwal,
Bojan Mohar

摘要

Given a graph G, its genus polynomial is $\Gamma _G(x) = \sum _{k\ge 0} g_k(G)x^k$ $Γ_{G} (x) = \sum_{k \geq 0} g_{k} (G) x^{k}$ , where $g_k(G)$ $g_{k} (G)$ is the number of two-cell embeddings of G in an orientable surface of genus k. The Log-Concavity Genus Distribution (LCGD) Conjecture states that the genus polynomial of every graph is log-concave. It was further conjectured by Stahl that the genus polynomial of every graph has only real roots, however, this was later disproved. We identify several examples of cubic graphs whose genus polynomials, in addition to having at least one non-real root, have a quadratic factor that is non-log-concave when factored over the real numbers.