Spectral extrema of K_s,t-minor free graphs -- on a conjecture of M. Tait

DOI10.1016/J.JCTB.2022.07.002MaRDI QIDQ2171018zbMATH OpenOpenAlexFDO

Authors Huiqiu Lin, Mingqing Zhai

Publication date 23 September 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

\(K_{s, t}\)-minorextremal graphmajorizationspectral radius

Mathematics Subject Classification ID

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

Abstract: Minors play an important role in extremal graph theory and spectral extremal graph theory. Tait [The Colin de Verdi`{e}re parameter, excluded minors, and the spectral radius, J. Combin. Theory Ser. A 166 (2019) 42--58] determined the maximum spectral radius and characterized the unique extremal graph for $K_r$-minor free graphs of sufficiently large order $n$, he also made great progress on $K_{s,t}$-minor free graphs and posed a conjecture: Let $2leqsleqt$ and $n-s+1=pt+q$, where $n$ is sufficiently large and $1leqqleqt.$ Then $K_{s-1}abla(p{K}_{t}cup{K}_q)$ is the unique extremal graph with the maximum spectral radius over all $n$-vertex $K_{s,t}$-minor free graphs. In this paper, Tait's conjecture is completely solved. We also determine the maximum spectral radius and its extremal graphs for $n$-vertex $K_{1,t}$-minor free graphs. To prove our results, some spectral and structural tools, such as, local edge maximality, local degree sequence majorization, double eigenvectors transformation, are used to deduce structural properties of extremal graphs.

Recommendations

• Extremal spectral radius of \(K_{3,3}/K_{2,4}\)-minor free graphs
• The spectral radius of graphs with no \(k_{2,t}\) minor
• Maxima of the \(Q\)-index: graphs with no \(K_{1,t}\)-minor
• On the signless Laplacian spectral radius of \(K_{s,t}\)-minor free graphs
• Bounds of spectral radii of K_{2,3}-minor free graphs

Cites work

• A complete solution to the Cvetković–Rowlinson conjecture
• A contribution to the Zarankiewicz problem
• A spectral condition for odd cycles in graphs
• An extremal function for contractions of graphs
• Bounds on graph eigenvalues. II
• Cliques and the spectral radius
• Covering planar graphs with forests, one having bounded maximum degree
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• Extremal spectral radius of \(K_{3,3}/K_{2,4}\)-minor free graphs
• Graphs with given degree sequence and maximal spectral radius
• Homomorphiesätze für Graphen
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 3906520 (Why is no real title available?)
• Lower bound of the Hadwiger number of graphs by their average degree
• Matrix theory
• On the spectral radius and the genus of graphs
• On the spectral radius of graphs without a star forest
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Some new results and problems in spectral extremal graph theory
• Some new results in extremal graph theory
• Spanning trees with many leaves
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral extremal results with forbidding linear forests
• Spectral radius of finite and infinite planar graphs and of graphs of bounded genus
• Spectral radius of graphs with given matching number
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• The edge-density for \(K_{2,t}\) minors
• The extremal function for complete minors
• The extremal function for unbalanced bipartite minors
• The largest eigenvalue of a graph: A survey
• The maximum spectral radius of graphs without friendship subgraphs
• The spectral radius of a planar graph
• The spectral radius of graphs on surfaces
• The spectral radius of graphs with no \(k_{2,t}\) minor
• The spectral radius of graphs with no intersecting odd cycles
• The spectral radius of graphs with no odd wheels
• The spectral radius of graphs without long cycles
• The spectral radius of graphs without paths and cycles of specified length
• The spectral radius of trees on \(k\) pendant vertices
• Three conjectures in extremal spectral graph theory
• Tree-width, clique-minors, and eigenvalues.
• Upper bounds of the spectral radius of graphs in terms of genus
• Upper bounds of the spectral radius of outerplanar graphs and Halin graphs

Cited in

(43)

• Extremal spectral radius of \(K_{3,3}/K_{2,4}\)-minor free graphs
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• Maxima of the \(Q\)-index: graphs with no \(K_{1,t}\)-minor
• Spectral extrema of graphs with bounded clique number and matching number
• Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size
• An \(A_\alpha\)-spectral Erdős-Pósa theorem
• On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs
• Maximum spread of \(K_{2,t}\)-minor-free graphs
• A spectral extremal problem on non-bipartite triangle-free graphs
• An \(A_{\alpha}\)-spectral Erdős-Sós theorem
• The spectral radius of minor-free graphs
• A spectral Erdős-Rademacher theorem
• The high order spectral extremal results for graphs and their applications
• Spectral extremal graphs without intersecting triangles as a minor
• Spectral extremal problem on t copies of -cycles
• Unifying adjacency, Laplacian, and signless Laplacian theories
• The -index of graphs without intersecting triangles/quadrangles as a minor
• Spectral extremal results on edge blow-up of graphs
• A spectral generalized Alon-Frankl theorem
• On spectral radius of planar graphs with fixed size
• A spectral version of the theorem of Zykov and Erdős
• Maximum spread of graphs without paths of specified length
• A spectral Erdős-Faudree-Rousseau theorem
• On the spectral extremal problem of planar graphs
• A spectral generalized Erdős-Gallai theorem
• The largest eigenvalue of \(\mathcal{C}_k^-\)-free signed graphs
• Decomposition family and spectral extremal problems on non-bipartite graphs
• A max-min problem on spectral radius and connectedness of graphs
• On the A_-index of C₄-free graphs with given order or size
• Spectral extremal results on the \(A_\alpha\)-spectral radius of graphs without \(K_{a,b}\)-minor
• Spectral Turán problem of non-bipartite graphs: forbidden books
• On the maximum second eigenvalue of outerplanar graphs
• Maximum spread of \(K_{s,t}\)-minor-free graphs
• Spectral radius and homeomorphically irreducible spanning trees of graphs
• Maximum spread of \(K_r - E(\cup_{i = 1}^\ell P_{k_i})\)-minor-free graphs
• Some exact and asymptotic results for hypergraph Turán problems in _2-norm
• Non-bipartite graphs without theta subgraphs
• The index of unbalanced signed complete graphs whose negative-edge-induced subgraph is \(K_{2,2}\)-minor free
• Bowtie-saturated graphs and the spectral radius
• Stable structure and extremal eigenvalues of degenerate Turán problems
• Extremal eigenvalues with respect to graph minors
• The (signless) Laplacian spectral radius with a fixed induced subgraph of a graph

This page was built for publication: Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait

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