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