We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

math.CO

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Mathematics > Combinatorics

Title: Eigenvalues and graph minors

Abstract: Let $spex(n,H_{minor})$ denote the maximum spectral radius of $n$-vertex $H$-minor free graphs. The problem on determining this extremal value can be dated back to the early 1990s. Up to now, it has been solved for $n$ sufficiently large and some special minors, such as $\{K_{2,3},K_4\}$, $\{K_{3,3},K_5\}$, $K_r$ and $K_{s,t}$. In this paper, we find some unified phenomena on general minors. Every graph $G$ on $n$ vertices with spectral radius $\rho\geq spex(n,H_{minor})$ contains either an $H$ minor or a spanning book $K_{\gamma_H}\nabla(n-\gamma_H)K_1$, where $\gamma_H=|H|-\alpha(H)-1$. Furthermore, assume that $G$ is $H$-minor free and $\Gamma^*_s(H)$ is the family of $s$-vertex irreducible induced subgraphs of $H$, then $G$ minus its $\gamma_H$ dominating vertices is $\Gamma^*_{\alpha(H)+1}(H)$-minor saturate, and it is further edge-maximal if $\Gamma^*_{\alpha(H)+1}(H)$ is a connected family. As applications, we obtain some known results on minors mentioned above. We also determine the extremal values for some other minors, such as flowers, wheels, generalized books and complete multi-partite graphs. Our results extend some conjectures on planar graphs, outer-planar graphs and $K_{s,t}$-minor free graphs. To obtain the results, we combine stability method, spectral techniques and structural analyses. Especially, we give an exploration of using absorbing method in spectral extremal problems.
Subjects: Combinatorics (math.CO)
Cite as: arXiv:2404.13389 [math.CO]
  (or arXiv:2404.13389v1 [math.CO] for this version)

Submission history

From: Longfei Fang [view email]
[v1] Sat, 20 Apr 2024 14:16:11 GMT (33kb)

Link back to: arXiv, form interface, contact.