## Spectral Turán theorems and related problems

##### Date

2022

##### Authors

##### Journal Title

##### Journal ISSN

##### Volume Title

##### Publisher

University of Delaware

##### Abstract

This thesis investigates some graph theoretic problems on the spectral radii and Perron vectors of graphs with certain structural constraints. ☐ For k ≥ 2, the odd wheel, W2k+1, is the graph formed by joining a vertex to an even cycle, C2k. In Chapter 2, we study the maximum value of the spectral radius of adjacency matrices of graphs on n vertices that do not contain an odd wheel W2k+1. For n sufficiently large, we determine the structure of the spectral extremal graphs when k ≥ 2 and k∉ {4, 5}. We show that when k = 2, the spectral extremal graphs are among the Turán extremal graphs on n vertices that do not contain W2k+1 and have the maximum number of edges. However, when k ≥ 9, we show that the family of spectral extremal graphs and the family of Turán-extremal graphs are disjoint. Chapter 2 comes from the paper, “The spectral radius of graphs with no odd wheels”, with coauthors Sebastian Cioabă and Michael Tait. ☐ For k ≥ 2 and r ≥ 3, a (k, r)-fan Fk,r is a graph on (r − 1)k + 1 vertices consisting of k copies of the complete graph Kr, that intersect at exactly one common vertex. When r = 3, this is the friendship graph with 2k + 1 vertices and k triangles. In Chapter 3, we study the maximum value of the spectral radius of adjacency matrices of graphs on n vertices that do not contain Fk,r. For given r > 3 and n sufficiently large, we show that the family of spectral extremal graphs are among the Turán extremal graphs on n vertices that do not contain Fk,r and have maximum number of edges. This extends a result of Cioabă, Feng, Tait, and Zhang for r = 3. Chapter 3 comes from the paper, “Spectral extremal graphs for intersecting cliques”, with coauthors Liying Kang, Yongtao Li, Zhenyu Ni, Michael Tait and Jing Wang. ☐ For k ≥ 2, let Sn,k denote the graph on n vertices formed by joining a clique on k vertices Kk, to an independent set Kn−k on n − k vertices. Let S+n,k denote the graph obtained from Sn,k by adding exactly one more edge in the independent set on n−k vertices. In Chapter 4, for k ≥ 2, we study the maximum value of the spectral radius of adjacency matrices of graphs on n vertices that do not contain any C2k+2. For n sufficiently large we prove that the spectral extremal graphs are isomorphic to S+n,k. This extends a result of Zhai and Lin for k = 2. Along with results of Nikiforov and Zhai and Wang, this covers all even cycles. When k ≥ 2, we also investigate the maximum value of the spectral radius of adjacency matrices of graphs on n vertices that contain neither any C2k+1 nor C2k+2. For n sufficiently large we prove that the spectral extremal graphs are isomorphic to Sn,k. These results settle a conjecture of Nikiforov (Conjecture 15). ☐ For any graph G, we call the graph obtained by joining a new vertex with G as the cone of G, and denote it by G∗. In Chapter 5 we investigate the Perron vector of graphs and determine the minimum value of λ(G∗) − λ(G) among all simple graphs on n-vertices. We show that only the complete graph Kn attains this minimal increase, thus proving a conjecture of Akbari. We generalize the result to obtain a similar result for loopless multigraphs with a bounded number of edges between any pair of vertices in G. We end with a generalization of cones to simple regular graphs, where we only join pn vertices of a regular graph, G, to a new vertex, for some 0 ≤ p ≤ 1. We call this the p-cone of G, and denote it by G∗p. We obtain a lower bound for λ(G∗p)−λ(G) which is tight for p = 0, 1 and reduces to our first result in this chapter.

##### Description

##### Keywords

Algebraic graph theory, Combinatorics, Discrete mathematics, Extremal graph theory, Linear algebra, Spectral graph theory