Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs

Abstract: Let

e t a (G)

be the number of connected induced subgraphs in a graph

G

, and

o v e r l i n e G

the complement of

G

. We prove that

e t a (G) + e t a (o v e r l i n e G)

is minimum, among all

n

-vertex graphs, if and only if

G

has no induced path on four vertices. Since the

n

-vertex star

S_{n}

with maximum degree

n - 1

is the unique tree of diameter

2

,

e t a (S_{n}) + e t a (o v e r l i n e S_{n})

is minimum among all

n

-vertex trees, while the maximum is shown to be achieved only by the tree whose degree sequence is

(l c e i l n / 2 c e i l, l f l o o r n / 2 f l o o r, 1, d o t s, 1)

. Furthermore, we prove that every graph

G

of order

n g e q 5

and with maximum

e t a (G) + e t a (o v e r l i n e G)

must have diameter at most

3

, no cut vertex and the property that

o v e r l i n e G

is also connected. In both cases of trees and graphs that have the same order, we find that if

e t a (G)

is maximum then

e t a (G) + e t a (o v e r l i n e G)

is minimum. As corollaries to our results, we characterise the unique connected graph

G

of given order and number of vertices of degree

1

, and the unique unicyclic (connected and has only one cycle) graphs

G

of a given order that minimises

e t a (G) + e t a (o v e r l i n e G)

.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs