1‐Factor and Cycle Covers of Cubic Graphs. Issue 3 (14th April 2014)

• Record Type: Journal Article
• Authors: Steffen, Eckhard
• Is Part Of: Journal of graph theory. Volume 78:Issue 3(2015)
• Page Start: 195
• Page End: 206
• Publication Date: 2014-04-14
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21798
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <italic>G</italic> be a bridgeless cubic graph. Consider a list of <italic>k</italic> 1‐factors of <italic>G</italic>. Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcs2j" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>E</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math></alternatives></inline-formula> be the set of edges contained in precisely <italic>i</italic> members of the <italic>k</italic> 1‐factors. Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcs0f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>μ</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> be the smallest <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcrzc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:msub><mml:mi>E</mml:mi><mml:mn>0</mml:mn></mml:msub><mml:mrow><mml:mo>|</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> over all lists of <italic>k</italic> 1‐factors of <italic>G</italic>. Any list of three 1‐factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge‐covers and for the existence of three 1‐factors with empty intersection. Furthermore, if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcrxt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>μ</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≠</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>, then <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcrw8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>2</mml:mn><mml:msub><mml:mi>μ</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> is an upper bound for the girth of <italic>G</italic>. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcrt5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>μ</mml:mi><mml:mn>4</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> have a 4‐cycle cover of length <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh30vzcrr2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21798:jgt21798-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mfrac><mml:mn>4</mml:mn><mml:mn>3</mml:mn></mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>E</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>|</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula> and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang <xref ref-type="link" rid="jgt21798-bib-0018">18</xref>. We also give a negative answer to a problem stated in <xref ref-type="link" rid="jgt21798-bib-0018">18</xref>.</p> </abstract>