Path decompositions of regular graphs with prescribed girth
详细信息 查看全文
- 作者：F. Botler fbotler@ime.usp.br" class="auth_mail" title="E-mail the corresponding author ; G.O. Mota mota@ime.usp.br" class="auth_mail" title="E-mail the corresponding author ; M.T.I. Oshiro oshiro@ime.usp.br" class="auth_mail" title="E-mail the corresponding author ; Y. Wakabayashi yw@ime.usp.br" class="auth_mail" title="E-mail the corresponding author
- 关键词：regular graphs ; edge-decomposition ; girth ; path decomposition
- 刊名：Electronic Notes in Discrete Mathematics
- 出版年：2015
- 出版时间：November 2015
- 年：2015
- 卷：49
- 期：Complete
- 页码：629-636
- 全文大小：217 K
文摘
A mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si1.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=430375a47cfb2d571f7f5c2b7f7da7e7" title="Click to view the MathML source">PℓmathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mi>ℓmi>mrow>msub>math>-decomposition of a graph m>G m> is a set of pairwise edge-disjoint paths of m>G m> with m>ℓ m> edges that cover the edge set of m>G m>. Kotzig [Kotzig, A., m>Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades m>, Časopis Pěst. Mat. trong class="boldFont">82 trong> (1957), pp. 76–92.] proved that a 3-regular graph admits a mmlsi2" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si2.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=70da13acd78f96f7b924ba62475d1645" title="Click to view the MathML source">P3mathContainer hidden">mathCode"><math altimg="si2.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mn>3mn>mrow>msub>math>-decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an m>ℓ m>-regular graph to admit a mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si1.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=430375a47cfb2d571f7f5c2b7f7da7e7" title="Click to view the MathML source">PℓmathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mi>ℓmi>mrow>msub>math>-decomposition, for odd m>ℓ m>. Let m>g m>, m>ℓ m> and m>m m> be positive integers with mmlsi3" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si3.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=6e2dc201af6df2848fd1350db877a743" title="Click to view the MathML source">g≥3mathContainer hidden">mathCode"><math altimg="si3.gif" overflow="scroll"><mi>gmi><mo>≥mo><mn>3mn>math>. We prove that, (i) if m>ℓ m> is odd and mmlsi4" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si4.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=3fbcd404a02b4c518bdf3217fe9308ac" title="Click to view the MathML source">m>2⌊(ℓ−2)/(g−2)⌋mathContainer hidden">mathCode"><math altimg="si4.gif" overflow="scroll"><mi>mmi><mo>>mo><mn>2mn><mo stretchy="false">⌊mo><mo stretchy="false">(mo><mi>ℓmi><mo>−mo><mn>2mn><mo stretchy="false">)mo><mo stretchy="false">/mo><mo stretchy="false">(mo><mi>gmi><mo>−mo><mn>2mn><mo stretchy="false">)mo><mo stretchy="false">⌋mo>math>, then every m>mℓ m>-regular graph with girth at least m>g m> that contains an m>m m>-factor admits a mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si1.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=430375a47cfb2d571f7f5c2b7f7da7e7" title="Click to view the MathML source">PℓmathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mi>ℓmi>mrow>msub>math>-decomposition; (ii) if mmlsi5" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si5.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=5f68bf4efff16e8109a6847839d8a518" title="Click to view the MathML source">m>⌊(ℓ−2)/(g−2)⌋mathContainer hidden">mathCode"><math altimg="si5.gif" overflow="scroll"><mi>mmi><mo>>mo><mo stretchy="false">⌊mo><mo stretchy="false">(mo><mi>ℓmi><mo>−mo><mn>2mn><mo stretchy="false">)mo><mo stretchy="false">/mo><mo stretchy="false">(mo><mi>gmi><mo>−mo><mn>2mn><mo stretchy="false">)mo><mo stretchy="false">⌋mo>math>, then every mmlsi6" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si6.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=8a730c958c4e4221d16067009b413e73" title="Click to view the MathML source">2mℓmathContainer hidden">mathCode"><math altimg="si6.gif" overflow="scroll"><mn>2mn><mi>mmi><mi>ℓmi>math>-regular graph with girth at least m>g m> admits a mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065315001316&_mathId=si1.gif&_user=111111111&_pii=S1571065315001316&_rdoc=1&_issn=15710653&md5=430375a47cfb2d571f7f5c2b7f7da7e7" title="Click to view the MathML source">PℓmathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><msub><mrow><mi>Pmi>mrow><mrow><mi>ℓmi>mrow>msub>math>-decomposition.