Two problems on independent sets in graphs

) is unimodal. We provide evidence for this conjecture by showing that is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph

G (n, n, p)

, and show that for any fixed

p i n (0, 1]

its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for

p = i l d e O m e g a (n^{- 1 / 2})

. We also consider the problem of estimating

i (G) = s u m_{t g e q 0} i_{t} (G)

for

G

in various families. We give a sharp upper bound on the number of independent sets in an

n

-vertex graph with minimum degree

d e l t a

, for all fixed

d e l t a

and sufficiently large

n

. Specifically, we show that the maximum is achieved uniquely by

K_{d e l t a, n - d e l t a}

, the complete bipartite graph with

d e l t a

vertices in one partition class and

n - d e l t a

in the other. We also present a weighted generalization: for all fixed

x > 0

and

d e l t a > 0

, as long as

n = n (x, d e l t a)

is large enough, if

G

is a graph on

n

vertices with minimum degree

d e l t a

then

s u m_{t g e q 0} i_{t} (G) x^{t} l e q s u m_{t g e q 0} i_{t} (K_{d e l t a, n - d e l t a}) x^{t}

with equality if and only if

G = K_{d e l t a, n - d e l t a}

.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Two problems on independent sets in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q641174)