We prove the following theorem. Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$r\ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> be an integer, and G be a <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$K_{1,r}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>r</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-free r-edge-connected r-regular graph. Then, for every set W of even number of vertices of G such that the distance between any two vertices of W in G is at least 3, G has vertex-disjoint paths and cycles <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$P_1, \ldots , P_m, C_1, \ldots , C_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>P</mi> <mi>m</mi> </msub> <mo>,</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>C</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> such that (i) <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$V(G)=V(P_1) \cup \cdots \cup V(P_m) \cup V(C_1) \cup \cdots \cup V(C_n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∪</mo> <mo>⋯</mo> <mo>∪</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>m</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∪</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∪</mo> <mo>⋯</mo> <mo>∪</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>C</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, (ii) each path <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$P_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> connects two vertices of W, and (iii) the set of the end-vertices of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$P_i$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation>’s is equal to W. A similar result for a 3-regular graph is obtained in [Graphs Combin. 39 (2023) #85]. However, our proof is widely different from its proof.

Spanning Path-Cycle Systems with Given End-Vertices in Regular Graphs

期刊论文
发表日期：

2025年11月19日

查看全文

Yoshimi Egawa,
Mikio Kano,
Kenta Ozeki

摘要

We prove the following theorem. Let $r\ge 4$ $r \geq 4$ be an integer, and G be a $K_{1,r}$ $K_{1, r}$ -free r-edge-connected r-regular graph. Then, for every set W of even number of vertices of G such that the distance between any two vertices of W in G is at least 3, G has vertex-disjoint paths and cycles $P_1, \ldots , P_m, C_1, \ldots , C_n$ $P_{1}, \dots, P_{m}, C_{1}, \dots, C_{n}$ such that (i) $V(G)=V(P_1) \cup \cdots \cup V(P_m) \cup V(C_1) \cup \cdots \cup V(C_n)$ $V (G) = V (P_{1}) \cup \dots \cup V (P_{m}) \cup V (C_{1}) \cup \dots \cup V (C_{n})$ , (ii) each path $P_i$ $P_{i}$ connects two vertices of W, and (iii) the set of the end-vertices of $P_i$ $P_{i}$ ’s is equal to W. A similar result for a 3-regular graph is obtained in [Graphs Combin. 39 (2023) #85]. However, our proof is widely different from its proof.