Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$C_k$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation> be a cycle of length k. Let G be a graph with n vertices, m edges. Lin and Zeng proved that if G has a perfect matching and does not contain <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">$C_4$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">$C_6$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>6</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">$C_{2k}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mrow> <mn>2</mn> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, then G admits a bisection of size at least <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq5.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="156" /> </InlineMediaObject> <EquationSource Format="TEX">$\frac{m}{2}+c(k)m^{(2k+1)/(2k+2)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mi>m</mi> <mn>2</mn> </mfrac> <mo>+</mo> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>m</mi> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mo stretchy="false">(</mo> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> and showed that the bound is tight for <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">$k\in \{3,5\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>3</mn> <mo>,</mo> <mn>5</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we obtain a similar tight result by replacing <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">$C_4$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation> with two adjacent <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2889_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">$C_4$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>C</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>’s.

Maximum Bisections of Graphs Without Adjacent Quadrilaterals

期刊论文
发表日期：

2025年1月22日

查看全文

Qiming Hu,
Baogang Xu

摘要

Let $C_k$ $C_{k}$ be a cycle of length k. Let G be a graph with n vertices, m edges. Lin and Zeng proved that if G has a perfect matching and does not contain $C_4$ $C_{4}$ , $C_6$ $C_{6}$ and $C_{2k}$ $C_{2 k}$ , then G admits a bisection of size at least $\frac{m}{2}+c(k)m^{(2k+1)/(2k+2)}$ $\frac{m}{2} + c (k) m^{(2 k + 1) / (2 k + 2)}$ and showed that the bound is tight for $k\in \{3,5\}$ $k \in {3, 5}$ . In this paper, we obtain a similar tight result by replacing $C_4$ $C_{4}$ with two adjacent $C_4$ $C_{4}$ ’s.