On path decompositions of 2k-regular graphs

Abstract: Tibor Gallai conjectured that the edge set of every connected graph

G

on

n

vertices can be partitioned into

l c e i l n / 2 c e i l

paths. Let

m a t h c a l G_{k}

be the class of all

2 k

-regular graphs of girth at least

2 k - 2

that admit a pair of disjoint perfect matchings. In this work, we show that Gallai's conjecture holds in

m a t h c a l G_{k}

, for every

k g e q 3

. Further, we prove that for every graph

G

in

m a t h c a l G_{k}

on

n

vertices, there exists a partition of its edge set into

n / 2

paths of lengths in

2 k - 1, 2 k, 2 k + 1

.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: On path decompositions of \(2k\)-regular graphs