Decomposing a Cubic G aph
Oli e Bach le
Depa men o Ma hema ics
TU Kaise slau e n
Fu u e Resea ch in Combina o ial Op imiza ion, 2019
Ou line
Mo i a ion
3-Decomposi ions
Exis ence o Hamil onian G aphs
Ou Resul
Exis ence o Long 3-Decomposi ions
An Algo i hm o Compu e Them
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 1 / 11
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
A
long
3-decomposi ion o a connec ed, cubic g aph Gconsis s o
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1
o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 2 / 11
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
A
long
3-decomposi ion o a connec ed, cubic g aph Gconsis s o
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1
o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 2 / 11
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
A
long
3-decomposi ion o a connec ed, cubic g aph Gconsis s o
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1
o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 2 / 11
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
Along 3-decomposi ion o a connec ed, cubic g aph Gconsis s o
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1 o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 2 / 11
An Example G aph
IGi en a connec ed, cubic
g aph.
ITake a spanning ee.
IThe emaining edges o m
cycles and pa hs.
IWan pa hs o leng h 1 o 2.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 3 / 11
An Example G aph
IGi en a connec ed, cubic
g aph.
ITake a spanning ee.
IThe emaining edges o m
cycles and pa hs.
IWan pa hs o leng h 1 o 2.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 3 / 11
An Example G aph
IGi en a connec ed, cubic
g aph.
ITake a spanning ee.
IThe emaining edges o m
cycles and pa hs.
IWan pa hs o leng h 1 o 2.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 3 / 11
The 3-Decomposi ion Conjec u e
De ini ion (3-Decomposi ion)
Along 3-decomposi ion o a connec ed, cubic g aph Gis
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1 o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Conjec u e (3-Decomposi ion Conjec u e)
E e y connec ed, cubic g aph has a 3-decomposi ion.
Theo em (Main Resul )
E e y connec ed, cubic g aph has a long 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 4 / 11
The 3-Decomposi ion Conjec u e
De ini ion (3-Decomposi ion)
Along 3-decomposi ion o a connec ed, cubic g aph Gis
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1 o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Conjec u e (3-Decomposi ion Conjec u e)
E e y connec ed, cubic g aph has a 3-decomposi ion.
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 4 / 11
The 3-Decomposi ion Conjec u e
De ini ion (3-Decomposi ion)
Along 3-decomposi ion o a connec ed, cubic g aph Gis
Ia spanning ee T,
Ia 2- egula subg aph C, and
Ia union o disjoin pa hs Po leng h 1 o 2
such ha E(G)is he disjoin union E(T)∪E(C)∪E(P).
Conjec u e (3-Decomposi ion Conjec u e)
E e y connec ed, cubic g aph has a 3-decomposi ion.
Theo em (Main Resul )
E e y connec ed, cubic g aph has a long 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 4 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed, cubic, Hamil onian g aph has a 3-decomposi ion.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 5 / 11
Exis ence o Long 3-Decomposi ions
Theo em
E e y connec ed, cubic g aph has a long 3-decomposi ion.
P elimina ies
ILe Gbe connec ed and cubic wi h spanning ee T.
IG−E(T)consis s o disjoin cycles and pa hs.
IP2(T)is he se o hose pa hs o leng h a leas 2.
IThe po en ial o Tis
X
P∈P2(T)
|E(P)|2
.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 6 / 11
Exis ence o Long 3-Decomposi ions
Theo em
E e y connec ed, cubic g aph has a long 3-decomposi ion.
P elimina ies
ILe Gbe connec ed and cubic wi h spanning ee T.
IG−E(T)consis s o disjoin cycles and pa hs.
IP2(T)is he se o hose pa hs o leng h a leas 2.
IThe po en ial o Tis
X
P∈P2(T)
|E(P)|2
.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 6 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge?
Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge?
Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge?
Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge?
Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge? Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge?
Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence
Idea
ITake a spanning ee To minimal po en ial.
IAssume Tdoes no yield a long 3-decomposi ion.
ITake a pa h P om P2(T)o maximal leng h k≥3.
IUsing P, ind a ans o ma ion o T ha dec eases he po en ial.
P oo .
ILe Tand Pas in he idea.
ILe Qbe he pa h om he
second o he hi d e ex o P.
IDoes Qha e a e ex no
inciden o a pa h-edge? Q
P
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 7 / 11
P oo o he Exis ence II
Case 1: Such a e ex exis s
ISwap he edge o i s p edecesso
wi h he second edge o P.
IThis yields a new ee T0.
IP2(T0)loses Pbu gains a pa h o leng h k−2.
ILe he p edecesso be he end o a pa h o leng h l≤k.
IThe leng h o he second pa h inc eases om l o l+1.
IThe po en ial dec eases.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 8 / 11
P oo o he Exis ence II
Case 1: Such a e ex exis s
ISwap he edge o i s p edecesso wi h he second edge o P.
IThis yields a new ee T0.
IP2(T0)loses Pbu gains a pa h o leng h k−2.
ILe he p edecesso be he end o a pa h o leng h l≤k.
IThe leng h o he second pa h inc eases om l o l+1.
IThe po en ial dec eases.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 8 / 11
P oo o he Exis ence III
Case 2: No such e ex exis s
IThen he las edge inciden o any e ex in Qis a pa h-edge.
IAs Q⊆Tand Tis connec ed Q=T.
IAs Tis spanning, V(Q) = V(G).
IQand he second edge o P o m a Hamil onian cycle.
ISo Ghas a 3-decomposi ion and a ee o po en ial 0.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 9 / 11
P oo o he Exis ence III
Case 2: No such e ex exis s
IThen he las edge inciden o any e ex in Qis a pa h-edge.
IAs Q⊆Tand Tis connec ed Q=T.
IAs Tis spanning, V(Q) = V(G).
IQand he second edge o P o m a Hamil onian cycle.
ISo Ghas a 3-decomposi ion and a ee o po en ial 0.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 9 / 11
P oo o he Exis ence III
Case 2: No such e ex exis s
IThen he las edge inciden o any e ex in Qis a pa h-edge.
IAs Q⊆Tand Tis connec ed Q=T.
IAs Tis spanning, V(Q) = V(G).
IQand he second edge o P o m a Hamil onian cycle.
ISo Ghas a 3-decomposi ion and a ee o po en ial 0.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 9 / 11
P oo o he Exis ence III
Case 2: No such e ex exis s
IThen he las edge inciden o any e ex in Qis a pa h-edge.
IAs Q⊆Tand Tis connec ed Q=T.
IAs Tis spanning, V(Q) = V(G).
IQand he second edge o P o m a Hamil onian cycle.
ISo Ghas a 3-decomposi ion and a ee o po en ial 0.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 9 / 11
P oo o he Exis ence III
Case 2: No such e ex exis s
IThen he las edge inciden o any e ex in Qis a pa h-edge.
IAs Q⊆Tand Tis connec ed Q=T.
IAs Tis spanning, V(Q) = V(G).
IQand he second edge o P o m a Hamil onian cycle.
ISo Ghas a 3-decomposi ion and a ee o po en ial 0.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 9 / 11
P oo o he Exis ence III
Case 2: No such e ex exis s
IThen he las edge inciden o any e ex in Qis a pa h-edge.
IAs Q⊆Tand Tis connec ed Q=T.
IAs Tis spanning, V(Q) = V(G).
IQand he second edge o P o m a Hamil onian cycle.
ISo Ghas a 3-decomposi ion and a ee o po en ial 0.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 9 / 11
Compu ing a long 3-decomposi ion
The P oo as an Algo i hm
Compu e a spanning ee To G;
De e mine he longes pa h Pin P2(T);
while Phas leng h a leas 3 do
De e mine Q;
i Qhas a e ex as in Case 1 hen
Swap edges and ecompu e P;
else
Compu e a 3-decomposi ion o G;
e u n i s ee;
end
end
e u n T;
The Run ime
IEach s ep can be
done in O(n) ime.
IWhile-loop execu ed
only O(n2)o en.
ISo, cubic un ime.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 10 / 11
Compu ing a long 3-decomposi ion
The P oo as an Algo i hm
Compu e a spanning ee To G;
De e mine he longes pa h Pin P2(T);
while Phas leng h a leas 3 do
De e mine Q;
i Qhas a e ex as in Case 1 hen
Swap edges and ecompu e P;
else
Compu e a 3-decomposi ion o G;
e u n i s ee;
end
end
e u n T;
The Run ime
IEach s ep can be
done in O(n) ime.
IWhile-loop execu ed
only O(n2)o en.
ISo, cubic un ime.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 10 / 11
Compu ing a long 3-decomposi ion
The P oo as an Algo i hm
Compu e a spanning ee To G;
De e mine he longes pa h Pin P2(T);
while Phas leng h a leas 3 do
De e mine Q;
i Qhas a e ex as in Case 1 hen
Swap edges and ecompu e P;
else
Compu e a 3-decomposi ion o G;
e u n i s ee;
end
end
e u n T;
The Run ime
IEach s ep can be
done in O(n) ime.
IWhile-loop execu ed
only O(n2)o en.
ISo, cubic un ime.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 10 / 11
Summa y
In connec ed, cubic g aphs
IaHamil onian cycle yields a 3-decomposi ion,
Ialong 3-decomposi ions always exis s,
Iand can be compu ed in cubic ime.
Con ac : bach le @ma hema ik.uni-kl.de
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 11 / 11
Fo Fu he Reading
S. Akba i, T. R. Jensen, M. Sigge s.
Decomposi ions o g aphs in o ees, o es s, and egula subg aphs.
Jou nal o Disc e e Ma hema ics, ol. 338, no. 8, pp. 1322-1327, 2015.
Oli e Bach le Decomposing a Cubic G aph FRICO 2019 1 / 1
