Decomposing a Cubic Graph

Decomposing a Cubic Graph Oliver Bachtler Department of Mathematics TU Kaiserslautern Future Research in Combinatorial Optimization, 2019 Outline Motivation 3-Decompositions Existence for Hamiltonian Graphs Our Result Existence of Long 3-Decompositions An Algorithm to Compute Them Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 1 / 11 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A long 3-decomposition of a connected, cubic graph Gconsists of Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 2 / 11 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A long 3-decomposition of a connected, cubic graph Gconsists of Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 2 / 11 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A long 3-decomposition of a connected, cubic graph Gconsists of Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 2 / 11 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) Along 3-decomposition of a connected, cubic graph Gconsists of Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 2 / 11 An Example Graph IGiven a connected, cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1 or 2. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 3 / 11 An Example Graph IGiven a connected, cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1 or 2. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 3 / 11 An Example Graph IGiven a connected, cubic graph. ITake a spanning tree. IThe remaining edges form cycles and paths. IWant paths of length 1 or 2. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 3 / 11 The 3-Decomposition Conjecture Definition (3-Decomposition) Along 3-decomposition of a connected, cubic graph Gis Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Conjecture (3-Decomposition Conjecture) Every connected, cubic graph has a 3-decomposition. Theorem (Main Result) Every connected, cubic graph has a long 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 4 / 11 The 3-Decomposition Conjecture Definition (3-Decomposition) Along 3-decomposition of a connected, cubic graph Gis Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Conjecture (3-Decomposition Conjecture) Every connected, cubic graph has a 3-decomposition. Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 4 / 11 The 3-Decomposition Conjecture Definition (3-Decomposition) Along 3-decomposition of a connected, cubic graph Gis Ia spanning tree T, Ia 2-regular subgraph C, and Ia union of disjoint paths Pof length 1 or 2 such that E(G)is the disjoint union E(T)∪E(C)∪E(P). Conjecture (3-Decomposition Conjecture) Every connected, cubic graph has a 3-decomposition. Theorem (Main Result) Every connected, cubic graph has a long 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 4 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected, cubic, Hamiltonian graph has a 3-decomposition. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 5 / 11 Existence of Long 3-Decompositions Theorem Every connected, cubic graph has a long 3-decomposition. Preliminaries ILet Gbe connected and cubic with spanning tree T. IG−E(T)consists of disjoint cycles and paths. IP2(T)is the set of those paths of length at least 2. IThe potential of Tis X P∈P2(T) |E(P)|2 . Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 6 / 11 Existence of Long 3-Decompositions Theorem Every connected, cubic graph has a long 3-decomposition. Preliminaries ILet Gbe connected and cubic with spanning tree T. IG−E(T)consists of disjoint cycles and paths. IP2(T)is the set of those paths of length at least 2. IThe potential of Tis X P∈P2(T) |E(P)|2 . Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 6 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence Idea ITake a spanning tree Tof minimal potential. IAssume Tdoes not yield a long 3-decomposition. ITake a path Pfrom P2(T)of maximal length k≥3. IUsing P, find a transformation of Tthat decreases the potential. Proof. ILet Tand Pas in the idea. ILet Qbe the path from the second to the third vertex of P. IDoes Qhave a vertex not incident to a path-edge? Q P Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 7 / 11 Proof of the Existence II Case 1: Such a vertex exists ISwap the edge to its predecessor with the second edge of P. IThis yields a new tree T0. IP2(T0)loses Pbut gains a path of length k−2. ILet the predecessor be the end of a path of length l≤k. IThe length of the second path increases from lto l+1. IThe potential decreases. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 8 / 11 Proof of the Existence II Case 1: Such a vertex exists ISwap the edge to its predecessor with the second edge of P. IThis yields a new tree T0. IP2(T0)loses Pbut gains a path of length k−2. ILet the predecessor be the end of a path of length l≤k. IThe length of the second path increases from lto l+1. IThe potential decreases. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 8 / 11 Proof of the Existence III Case 2: No such vertex exists IThen the last edge incident to any vertex in Qis a path-edge. IAs Q⊆Tand Tis connected Q=T. IAs Tis spanning, V(Q) = V(G). IQand the second edge of Pform a Hamiltonian cycle. ISo Ghas a 3-decomposition and a tree of potential 0. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 9 / 11 Proof of the Existence III Case 2: No such vertex exists IThen the last edge incident to any vertex in Qis a path-edge. IAs Q⊆Tand Tis connected Q=T. IAs Tis spanning, V(Q) = V(G). IQand the second edge of Pform a Hamiltonian cycle. ISo Ghas a 3-decomposition and a tree of potential 0. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 9 / 11 Proof of the Existence III Case 2: No such vertex exists IThen the last edge incident to any vertex in Qis a path-edge. IAs Q⊆Tand Tis connected Q=T. IAs Tis spanning, V(Q) = V(G). IQand the second edge of Pform a Hamiltonian cycle. ISo Ghas a 3-decomposition and a tree of potential 0. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 9 / 11 Proof of the Existence III Case 2: No such vertex exists IThen the last edge incident to any vertex in Qis a path-edge. IAs Q⊆Tand Tis connected Q=T. IAs Tis spanning, V(Q) = V(G). IQand the second edge of Pform a Hamiltonian cycle. ISo Ghas a 3-decomposition and a tree of potential 0. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 9 / 11 Proof of the Existence III Case 2: No such vertex exists IThen the last edge incident to any vertex in Qis a path-edge. IAs Q⊆Tand Tis connected Q=T. IAs Tis spanning, V(Q) = V(G). IQand the second edge of Pform a Hamiltonian cycle. ISo Ghas a 3-decomposition and a tree of potential 0. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 9 / 11 Proof of the Existence III Case 2: No such vertex exists IThen the last edge incident to any vertex in Qis a path-edge. IAs Q⊆Tand Tis connected Q=T. IAs Tis spanning, V(Q) = V(G). IQand the second edge of Pform a Hamiltonian cycle. ISo Ghas a 3-decomposition and a tree of potential 0. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 9 / 11 Computing a long 3-decomposition The Proof as an Algorithm Compute a spanning tree Tof G; Determine the longest path Pin P2(T); while Phas length at least 3 do Determine Q; if Qhas a vertex as in Case 1 then Swap edges and recompute P; else Compute a 3-decomposition of G; return its tree; end end return T; The Runtime IEach step can be done in O(n)time. IWhile-loop executed only O(n2)often. ISo, cubic runtime. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 10 / 11 Computing a long 3-decomposition The Proof as an Algorithm Compute a spanning tree Tof G; Determine the longest path Pin P2(T); while Phas length at least 3 do Determine Q; if Qhas a vertex as in Case 1 then Swap edges and recompute P; else Compute a 3-decomposition of G; return its tree; end end return T; The Runtime IEach step can be done in O(n)time. IWhile-loop executed only O(n2)often. ISo, cubic runtime. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 10 / 11 Computing a long 3-decomposition The Proof as an Algorithm Compute a spanning tree Tof G; Determine the longest path Pin P2(T); while Phas length at least 3 do Determine Q; if Qhas a vertex as in Case 1 then Swap edges and recompute P; else Compute a 3-decomposition of G; return its tree; end end return T; The Runtime IEach step can be done in O(n)time. IWhile-loop executed only O(n2)often. ISo, cubic runtime. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 10 / 11 Summary In connected, cubic graphs IaHamiltonian cycle yields a 3-decomposition, Ialong 3-decompositions always exists, Iand can be computed in cubic time. Contact: [email protected] Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 11 / 11 For Further Reading S. Akbari, T. R. Jensen, M. Siggers. Decompositions of graphs into trees, forests, and regular subgraphs. Journal of Discrete Mathematics, vol. 338, no. 8, pp. 1322-1327, 2015. Oliver Bachtler Decomposing a Cubic Graph FRICO 2019 1 / 1