Some existence theorems on path-factor critical avoidable graphs

Abstract: A spanning subgraph

F

of

G

is called a path factor if every component of

F

is a path of order at least 2. Let

k g e q 2

be an integer. A

P_{g e q k}

-factor of

G

means a path factor in which every component has at least

k

vertices. A graph

G

is called a

P_{g e q k}

-factor avoidable graph if for any

e i n E (G)

,

G

has a

P_{g e q k}

-factor avoiding

e

. A graph

G

is called a

(P_{g e q k}, n)

-factor critical avoidable graph if for any

W s u b s e t e q V (G)

with

| W | = n

,

G - W

is a

P_{g e q k}

-factor avoidable graph. In other words,

G

is

(P_{g e q k}, n)

-factor critical avoidable if for any

W s u b s e t e q V (G)

with

| W | = n

and any

e i n E (G - W)

,

G - W - e

admits a

P_{g e q k}

-factor. In this article, we verify that ( omannumeral1) an

(n + r + 2)

-connected graph

G

is

(P_{g e q 2}, n)

-factor critical avoidable if

I (G) > f r a c n + r + 3 2 (r + 2)

; ( omannumeral2) an

(n + r + 2)

-connected graph

G

is

(P_{g e q 3}, n)

-factor critical avoidable if

t (G) > f r a c n + r + 2 2 (r + 2)

; ( omannumeral3) an

(n + r + 2)

-connected graph

G

is

(P_{g e q 3}, n)

-factor critical avoidable if

I (G) > f r a c n + 3 (r + 2) 2 (r + 2)

; where

n

and

r

are two nonnegative integers.

Recommendations

Cited in

(1)

This page was built for publication: Some existence theorems on path-factor critical avoidable graphs