Induced path factors of regular graphs

Publication date 29 September 2023

Abstract: An induced path factor of a graph

G

is a set of induced paths in

G

with the property that every vertex of

G

is in exactly one of the paths. The induced path number

h o (G)

of

G

is the minimum number of paths in an induced path factor of

G

. We show that if

G

is a connected cubic graph on

n > 6

vertices, then

h o (G) l e (n - 1) / 3

. Fix an integer

k g e 3

. For each

n

, define

m a t h c a l M_{n}

to be the maximum value of

h o (G)

over all connected

k

-regular graphs

G

on

n

vertices. As

n i g h t a r r o w i n f t y

with

n k

even, we show that

c_{k} = l i m (m a t h c a l M_{n} / n)

exists. We prove that

5 / 18 l e c_{3} l e 1 / 3

and

3 / 7 l e c_{4} l e 1 / 2

and that

c_{k} = f r a c 12 - O (k^{- 1})

for

k i g h t a r r o w i n f t y

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Induced path factors of regular graphs