Maximum spread of K₂,t-minor-free graphs

Abstract: The spread of a graph

G

is the difference between the largest and smallest eigenvalues of the adjacency matrix of

G

. In this paper, we consider the family of graphs which contain no

K_{2, t}

-minor. We show that for any

t g e q 2

, there is an integer

x i_{t}

such that the maximum spread of an

n

-vertex

K_{2, t}

-minor-free graph is achieved by the graph obtained by joining a vertex to the disjoint union of

l f l o o r f r a c 2 n + x i_{t} 3 t f l o o r

copies of

K_{t}

and

n - 1 - t l f l o o r f r a c 2 n + x i_{t} 3 t f l o o r

isolated vertices. The extremal graph is unique, except when

t e q u i v 4 m o d 12

and

f r a c 2 n + x i_{t} 3 t

is an integer, in which case the other extremal graph is the graph obtained by joining a vertex to the disjoint union of

l f l o o r f r a c 2 n + x i_{t} 3 t f l o o r - 1

copies of

K_{t}

and

n - 1 - t (l f l o o r f r a c 2 n + x i_{t} 3 t f l o o r - 1)

isolated vertices. Furthermore, we give an explicit formula for

x i_{t}

.

Recommendations

Cites Work

Cited In (1)

This page was built for publication: Maximum spread of \(K_{2,t}\)-minor-free graphs