Decomposing Star-Like Cubic Graphs

Decomposing Star-like Cubic Graphs Oliver Bachtler, Sven O. Krumke TU Kaiserslautern Young Mathematicians Symposium of the Greater Region, 2020 Outline Basics 3-Decompositions Existence for Hamiltonian Graphs Constructing a Decomposition From the Centre To the Tips Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 1 / 15 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A3-decomposition of a connected cubic graph Gconsists of Ia spanning tree T, Ia set of cycles C, and Ia matching M such that E(G)is the disjoint union E(T)∪E(C)∪M. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 2 / 15 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A3-decomposition of a connected cubic graph Gconsists of Ia spanning tree T, Ia set of cycles C, and Ia matching M such that E(G)is the disjoint union E(T)∪E(C)∪M. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 2 / 15 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A3-decomposition of a connected cubic graph Gconsists of Ia spanning tree T, Ia set of cycles C, and Ia matching M such that E(G)is the disjoint union E(T)∪E(C)∪M. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 2 / 15 An Example Graph IGiven: connected cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 3 / 15 An Example Graph IGiven: connected cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 3 / 15 An Example Graph IGiven: connected cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 3 / 15 An Example Graph IGiven: connected cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 3 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Xie, Zhou, Zhou) Every graph with a contraction graph on 3 vertices has a 3-decomposition. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. IG−Mconsists of cycles. IContracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2vertices does not disconnect it. Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 5 / 15 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. chordless cycle Call this the decomposition given by the chordless cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 6 / 15 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. chordless cycle Call this the decomposition given by the chordless cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 6 / 15 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. chordless cycle Call this the decomposition given by the chordless cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 6 / 15 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. chordless cycle Call this the decomposition given by the chordless cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 6 / 15 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. chordless cycle Call this the decomposition given by the chordless cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 6 / 15 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. chordless cycle Call this the decomposition given by the chordless cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 6 / 15 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a chordless cycle avoiding any fixed vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 7 / 15 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a chordless cycle avoiding any fixed vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 7 / 15 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a chordless cycle avoiding any fixed vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 7 / 15 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a chordless cycle avoiding any fixed vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 7 / 15 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a chordless cycle avoiding any fixed vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 7 / 15 Decomposing the Centre ITake any chordless cycle C. ICheck amount of edges to each tip. IAt most 1. IAt least 2 to some tip. IUse decomposition Igiven by C. Iusing a part of C. I3 cases for the tips: Ionly black edges, I1 green edge, I2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 8 / 15 Decomposing the Centre ITake any chordless cycle C. ICheck amount of edges to each tip. IAt most 1. IAt least 2 to some tip. IUse decomposition Igiven by C. Iusing a part of C. I3 cases for the tips: Ionly black edges, I1 green edge, I2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 8 / 15 Decomposing the Centre ITake any chordless cycle C. ICheck amount of edges to each tip. IAt most 1. IAt least 2 to some tip. IUse decomposition Igiven by C. Iusing a part of C. I3 cases for the tips: Ionly black edges, I1 green edge, I2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 8 / 15 Decomposing the Centre ITake any chordless cycle C. ICheck amount of edges to each tip. IAt most 1. IAt least 2 to some tip. IUse decomposition Igiven by C. Iusing a part of C. I3 cases for the tips: Ionly black edges, I1 green edge, I2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 8 / 15 Decomposing the Centre ITake any chordless cycle C. ICheck amount of edges to each tip. IAt most 1. IAt least 2 to some tip. IUse decomposition Igiven by C. Iusing a part of C. I3 cases for the tips: Ionly black edges, I1 green edge, I2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 8 / 15 The Tips: Only Black Edges Take the decomposition given by a chordless cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 9 / 15 The Tips: Only Black Edges Take the decomposition given by a chordless cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 9 / 15 The Tips: Only Black Edges Take the decomposition given by a chordless cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 9 / 15 The Tips: One Green Edge ILook for a useful chordless cycle. IIf none exists ⇒All chords go from the left to the right path. IBoth paths have the same length ⇒Levels. ICall a chord long if its ends are at least 2 levels apart. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 10 / 15 The Tips: One Green Edge ILook for a useful chordless cycle. IIf none exists ⇒All chords go from the left to the right path. IBoth paths have the same length ⇒Levels. ICall a chord long if its ends are at least 2 levels apart. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 10 / 15 The Tips: One Green Edge Case 1: No long chord exists ITwo form of chords: Idirect Icross IObtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 11 / 15 The Tips: One Green Edge Case 1: No long chord exists ITwo form of chords: Idirect Icross IObtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 11 / 15 The Tips: One Green Edge Case 1: No long chord exists ITwo form of chords: Idirect Icross IObtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 11 / 15 The Tips: One Green Edge Case 1: No long chord exists ITwo form of chords: Idirect Icross IObtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 11 / 15 The Tips: One Green Edge Case 1: No long chord exists ITwo form of chords: Idirect Icross IObtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 11 / 15 The Tips: One Green Edge Case 1: No long chord exists ITwo form of chords: Idirect Icross IObtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 11 / 15 The Tips: One Green Edge Case 2: A long chord exists ITake the first such chord. IVertices before paired up. IRegard the other vertex on this level and its successor. INeighbours below the chord. IUse a two-chord cycle. ILeaves a tree. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 12 / 15 The Tips: One Green Edge Case 2: A long chord exists ITake the first such chord. IVertices before paired up. IRegard the other vertex on this level and its successor. INeighbours below the chord. IUse a two-chord cycle. ILeaves a tree. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 12 / 15 The Tips: One Green Edge Case 2: A long chord exists ITake the first such chord. IVertices before paired up. IRegard the other vertex on this level and its successor. INeighbours below the chord. IUse a two-chord cycle. ILeaves a tree. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 12 / 15 The Tips: One Green Edge Case 2: A long chord exists ITake the first such chord. IVertices before paired up. IRegard the other vertex on this level and its successor. INeighbours below the chord. IUse a two-chord cycle. ILeaves a tree. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 12 / 15 The Tips: Two Red Edges IOne path connects to centre. IPut it in Tand rest in C. IProblem: “red” chords. IIdea: use to shortcut. IMust connect new paths. ITake maximal sequence of chords such that Ipaths can be connected, Ichords are maximal. INeed: No more red chords. IBy maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 13 / 15 The Tips: Two Red Edges IOne path connects to centre. IPut it in Tand rest in C. IProblem: “red” chords. IIdea: use to shortcut. IMust connect new paths. ITake maximal sequence of chords such that Ipaths can be connected, Ichords are maximal. INeed: No more red chords. IBy maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 13 / 15 The Tips: Two Red Edges IOne path connects to centre. IPut it in Tand rest in C. IProblem: “red” chords. IIdea: use to shortcut. IMust connect new paths. ITake maximal sequence of chords such that Ipaths can be connected, Ichords are maximal. INeed: No more red chords. IBy maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 13 / 15 The Tips: Two Red Edges IOne path connects to centre. IPut it in Tand rest in C. IProblem: “red” chords. IIdea: use to shortcut. IMust connect new paths. ITake maximal sequence of chords such that Ipaths can be connected, Ichords are maximal. INeed: No more red chords. IBy maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 13 / 15 The Tips: Two Red Edges IOne path connects to centre. IPut it in Tand rest in C. IProblem: “red” chords. IIdea: use to shortcut. IMust connect new paths. ITake maximal sequence of chords such that Ipaths can be connected, Ichords are maximal. INeed: No more red chords. IBy maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 13 / 15 The Tips: Two Red Edges IOne path connects to centre. IPut it in Tand rest in C. IProblem: “red” chords. IIdea: use to shortcut. IMust connect new paths. ITake maximal sequence of chords such that Ipaths can be connected, Ichords are maximal. INeed: No more red chords. IBy maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 13 / 15 The Tips: Two Red Edges ICall vertices with neighbours in green paths or the centre good. ISuppose not all vertices in a red path are good. ITake two good vertices Iwith a bad one in between, Iof minimal distance. IThere exists a “crossing” chord. IExtends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 14 / 15 The Tips: Two Red Edges ICall vertices with neighbours in green paths or the centre good. ISuppose not all vertices in a red path are good. ITake two good vertices Iwith a bad one in between, Iof minimal distance. IThere exists a “crossing” chord. IExtends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 14 / 15 The Tips: Two Red Edges ICall vertices with neighbours in green paths or the centre good. ISuppose not all vertices in a red path are good. ITake two good vertices Iwith a bad one in between, Iof minimal distance. IThere exists a “crossing” chord. IExtends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 14 / 15 The Tips: Two Red Edges ICall vertices with neighbours in green paths or the centre good. ISuppose not all vertices in a red path are good. ITake two good vertices Iwith a bad one in between, Iof minimal distance. IThere exists a “crossing” chord. IExtends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs YMSGR 2020 14 / 15