Let G be a graph. For <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$x\in A$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>∈</mo> <mi>A</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$y\in B$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>y</mi> <mo>∈</mo> <mi>B</mi> </mrow> </math></EquationSource> </InlineEquation>, we define <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$d_A(x)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mi>A</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$d_B(y)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mi>B</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> as the vertices’ indegrees. Similarly, we define <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$d_A(y)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mi>A</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$d_B(x)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mi>B</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> as the outdegrees. A partition (A, B) of V(G) is an internal partition of G if <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\forall x\in A$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>∀</mo> <mi>x</mi> <mo>∈</mo> <mi>A</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$d_A(x)\ge d_B(x) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mi>A</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msub> <mi>d</mi> <mi>B</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\forall y\in B$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>∀</mo> <mi>y</mi> <mo>∈</mo> <mi>B</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$d_B(y)\ge d_A(y)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>d</mi> <mi>B</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <msub> <mi>d</mi> <mi>A</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. An internal bisection (A, B) of V(G) is an internal partition with <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\left| A\right| =\left| B\right| $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfenced close="|" open="|"> <mi>A</mi> </mfenced> <mo>=</mo> <mfenced close="|" open="|"> <mi>B</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. DeVos (2009) conjectures that for any integer d, every d-regular graph of sufficiently large order n has an internal partition. We proved that there exists a 5-regular graph of order 12 with no internal bisection. We also proved that every k-regular graph with minimum cut less than k has an internal partition where k is an odd integer.

On the Internal Partitions of some Regular Graphs

期刊论文
发表日期：

2026年6月20日

查看全文

Bo-Qian Zuo,
Ya-Hong Chen

摘要

Let G be a graph. For $x\in A$ $x \in A$ and $y\in B$ $y \in B$ , we define $d_A(x)$ $d_{A} (x)$ and $d_B(y)$ $d_{B} (y)$ as the vertices’ indegrees. Similarly, we define $d_A(y)$ $d_{A} (y)$ and $d_B(x)$ $d_{B} (x)$ as the outdegrees. A partition (A, B) of V(G) is an internal partition of G if $\forall x\in A$ $\forall x \in A$ , $d_A(x)\ge d_B(x) $ $d_{A} (x) \geq d_{B} (x)$ and $\forall y\in B$ $\forall y \in B$ , $d_B(y)\ge d_A(y)$ $d_{B} (y) \geq d_{A} (y)$ . An internal bisection (A, B) of V(G) is an internal partition with $\left| A\right| =\left| B\right| $ $|A| = |B|$ . DeVos (2009) conjectures that for any integer d, every d-regular graph of sufficiently large order n has an internal partition. We proved that there exists a 5-regular graph of order 12 with no internal bisection. We also proved that every k-regular graph with minimum cut less than k has an internal partition where k is an odd integer.