Saturated subgraphs of the hypercube

Abstract: We say

G

is emph{

(Q_{n}, Q_{m})

-saturated} if it is a maximal

Q_{m}

-free subgraph of the

n

-dimensional hypercube

Q_{n}

. A graph,

G

, is said to be

(Q_{n}, Q_{m})

-semi-saturated if it is a subgraph of

Q_{n}

and adding any edge forms a new copy of

Q_{m}

. The minimum number of edges a

(Q_{n}, Q_{m})

-saturated graph (resp.

(Q_{n}, Q_{m})

-semi-saturated graph) can have is denoted by

s a t (Q_{n}, Q_{m})

(resp.

s e x t - s a t (Q_{n}, Q_{m})

). We prove that

l i m_{n o i n f t y} f r a c s a t (Q_{n}, Q_{m}) e (Q_{n}) = 0

, for fixed

m

, disproving a conjecture of Santolupo that, when

m = 2

, this limit is

f r a c 14

. Further, we show by a different method that

s a t (Q_{n}, Q_{2}) = O (2^{n})

, and that

s e x t - s a t (Q_{n}, Q_{m}) = O (2^{n})

, for fixed

m

. We also prove the lower bound

s - s a t (Q_{n}, Q_{2}) g e q f r a c m + 1 2 c d o t 2^{n}

, thus determining

s a t (Q_{n}, Q_{2})

to within a constant factor, and discuss some further questions.

Recommendations

Cites Work

Cited In (13)

This page was built for publication: Saturated subgraphs of the hypercube