Spectral Turán theorems and related problems
Author(s) | Noal, Dheer | |
Date Accessioned | 2022-10-25T12:51:16Z | |
Date Available | 2022-10-25T12:51:16Z | |
Publication Date | 2022 | |
SWORD Update | 2022-08-10T19:09:09Z | |
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. | en_US |
Advisor | Cioabă, Sebastian M. | |
Advisor | Tait, Michael | |
Degree | Ph.D. | |
Department | University of Delaware, Department of Mathematical Sciences | |
DOI | https://doi.org/10.58088/0v5y-ce36 | |
Unique Identifier | 1348645019 | |
URL | https://udspace.udel.edu/handle/19716/31523 | |
Language | en | |
Publisher | University of Delaware | en_US |
URI | https://login.udel.idm.oclc.org/login?url=https://www.proquest.com/dissertations-theses/spectral-turán-theorems-related-problems/docview/2703452508/se-2?accountid=10457 | |
Keywords | Algebraic graph theory | |
Keywords | Combinatorics | |
Keywords | Discrete mathematics | |
Keywords | Extremal graph theory | |
Keywords | Linear algebra | |
Keywords | Spectral graph theory | |
Title | Spectral Turán theorems and related problems | en_US |
Type | Thesis | en_US |