1. Maximum spread of K2,t-minor-free graphs.
- Author
-
Linz, William, Lu, Linyuan, and Wang, Zhiyu
- Subjects
- *
INTEGERS , *EIGENVALUES , *MATRICES (Mathematics) , *MATROIDS - 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 ≥ 2 , there is an integer ξ 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 ⌊ 2 n + ξ t 3 t ⌋ copies of K t and n − 1 − t ⌊ 2 n + ξ t 3 t ⌋ isolated vertices. The extremal graph is unique, except when t ≡ 4 (mod 12) and 2 n + ξ 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 ⌊ 2 n + ξ t 3 t ⌋ − 1 copies of K t and n − 1 − t (⌊ 2 n + ξ t 3 t ⌋ − 1) isolated vertices. Furthermore, we give an explicit formula for ξ t. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF