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

DOI10.1016/J.LAA.2023.07.024MaRDI QIDQ6178786zbMATH OpenOpenAlexFDO

Authors William Linz, Linyuan Lu, Zhiyu Wang

Publication date 5 September 2023

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.05540

zbMATH Keywords

spreadminor-free graphsspectral Turán-type problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Graph minors (05C83)

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 $tgeq2$, 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 $lfloorfrac2n+x{i}_{t}3tfloor$ copies of $K_t$ and $n-1-tlfloorfrac2n+x{i}_{t}3tfloor$ isolated vertices. The extremal graph is unique, except when $tequiv4mod12$ and $frac2n+x{i}_{t}3t$ is an integer, in which case the other extremal graph is the graph obtained by joining a vertex to the disjoint union of $lfloorfrac2n+x{i}_{t}3tfloor-1$ copies of $K_t$ and $n-1-t(lfloorfrac2n+x{i}_{t}3tfloor-1)$ isolated vertices. Furthermore, we give an explicit formula for $x{i}_t$.

Recommendations

• The spectral radius of graphs with no \(k_{2,t}\) minor
• On the spread of outerplanar graphs
• The spread of the spectrum of a graph
• Maxima of the \(Q\)-index: graphs with no \(K_{1,t}\)-minor
• The spread of tetracyclic graphs

Cites work

• Bicyclic graphs for which the least eigenvalue is minimum
• Cacti whose spread is maximal
• Inequalities for Graph Eigenvalues
• Maximum spread of graphs and bipartite graphs
• Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread
• On the spectral spread of bicyclic graphs with given girth
• On the spread of outerplanar graphs
• On the spread of the spectrum of a graph
• Spectra of graphs
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• The edge-density for \(K_{2,t}\) minors
• The extremal function for unbalanced bipartite minors
• The largest eigenvalue of a graph: A survey
• The spectral radius of a planar graph
• The spectral radius of graphs with no \(k_{2,t}\) minor
• The spread of the spectrum of a graph
• The spread of the unicyclic graphs
• The spread of unicyclic graphs with given size of maximum matchings
• Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

Cited in

(1)

• On the spread of outerplanar graphs

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

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