<p>What is the maximum length <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textrm{f}_\textrm{max}(\ell , \Sigma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>f</mtext> <mtext>max</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of a facial cycle of an inclusion-maximal graph with girth at least <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\ell $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> embedded on a given surface <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Σ</mi> </math></EquationSource> </InlineEquation>? If <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Sigma =\mathcal {P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Σ</mi> <mo>=</mo> <mi mathvariant="script">P</mi> </mrow> </math></EquationSource> </InlineEquation> is a plane, we show that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$3\ell -11\le \textrm{f}_\textrm{max}(\ell , \mathcal {P})\le 8\ell -13$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mi>ℓ</mi> <mo>-</mo> <mn>11</mn> <mo>≤</mo> <msub> <mtext>f</mtext> <mtext>max</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi mathvariant="script">P</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>8</mn> <mi>ℓ</mi> <mo>-</mo> <mn>13</mn> </mrow> </math></EquationSource> </InlineEquation>. We also prove that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\textrm{f}_\textrm{max}(\ell , \Sigma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>f</mtext> <mtext>max</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is bounded for any integer <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\ell $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> and any closed surface <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\Sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Σ</mi> </math></EquationSource> </InlineEquation>. For a fixed <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\Sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Σ</mi> </math></EquationSource> </InlineEquation>, we show that <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\Omega (\ell ) =\textrm{f}_\textrm{max}(\ell , \Sigma ) = O(\ell ^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mtext>f</mtext> <mtext>max</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>O</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>ℓ</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, while for a fixed <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\ell \ge 6$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ℓ</mi> <mo>≥</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\textrm{f}_\textrm{max}(\ell , \Sigma )=\Theta (g)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>f</mtext> <mtext>max</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi mathvariant="normal">Θ</mi> <mrow> <mo stretchy="false">(</mo> <mi>g</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <i>g</i> is the genus of <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\Sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Σ</mi> </math></EquationSource> </InlineEquation>.</p>

Faces in Girth-Saturated Graphs on Surfaces

期刊论文
出版模式：

开放获取
发表日期：

2026年4月9日

查看全文

Maria Axenovich,
Leon Kießle,
Arsenii Sagdeev,
Maksim Zhukovskii

摘要

What is the maximum length $\textrm{f}_\textrm{max}(\ell , \Sigma )$ $f_{max} (ℓ, Σ)$ of a facial cycle of an inclusion-maximal graph with girth at least $\ell $ $ℓ$ embedded on a given surface $\Sigma $ $Σ$ ? If $\Sigma =\mathcal {P}$ $Σ = P$ is a plane, we show that $3\ell -11\le \textrm{f}_\textrm{max}(\ell , \mathcal {P})\le 8\ell -13$ $3 ℓ - 11 \leq f_{max} (ℓ, P) \leq 8 ℓ - 13$ . We also prove that $\textrm{f}_\textrm{max}(\ell , \Sigma )$ $f_{max} (ℓ, Σ)$ is bounded for any integer $\ell $ $ℓ$ and any closed surface $\Sigma $ $Σ$ . For a fixed $\Sigma $ $Σ$ , we show that $\Omega (\ell ) =\textrm{f}_\textrm{max}(\ell , \Sigma ) = O(\ell ^2)$ $Ω (ℓ) = f_{max} (ℓ, Σ) = O (ℓ^{2})$ , while for a fixed $\ell \ge 6$ $ℓ \geq 6$ , $\textrm{f}_\textrm{max}(\ell , \Sigma )=\Theta (g)$ $f_{max} (ℓ, Σ) = Θ (g)$ , where g is the genus of $\Sigma $ $Σ$ .