On the Maximum Order of Induced Paths and Induced Forests in Regular Graphs

Publication date: 6 November 2019

Abstract: Let

G

be a graph and

a (G)

, LIF

(G)

denote the maximum orders of an induced forest and an induced linear forest of

G

, respectively. It is well-known that if

G

is an

r

-regular graph of order

n

, then

a (G) g e q f r a c 2 r + 1 n

. In this paper, we generalize this result by showing that LIF

(G) g e q f r a c 2 r + 1 n

. It was proved that for every graph

G

,

a (G) g e q s u m_{i = 1}^{n} f r a c 2 d_{i} + 1

, where

d_{1}, l d o t s, d_{n}

is the degree sequence of

G

. Here, we conjecture that for every graph

G

with

d e l t a (G) g e q 2

, LIF

(G) g e q s u m_{i = 1}^{n} f r a c 2 d_{i} + 1

.

This page was built for publication: On the Maximum Order of Induced Paths and Induced Forests in Regular Graphs