Spectral Turán theorems and related problems

Author(s)Noal, Dheer
Date Accessioned2022-10-25T12:51:16Z
Date Available2022-10-25T12:51:16Z
Publication Date2022
SWORD Update2022-08-10T19:09:09Z
AbstractThis 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
AdvisorCioabă, Sebastian M.
AdvisorTait, Michael
DegreePh.D.
DepartmentUniversity of Delaware, Department of Mathematical Sciences
DOIhttps://doi.org/10.58088/0v5y-ce36
Unique Identifier1348645019
URLhttps://udspace.udel.edu/handle/19716/31523
Languageen
PublisherUniversity of Delawareen_US
URIhttps://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
KeywordsAlgebraic graph theory
KeywordsCombinatorics
KeywordsDiscrete mathematics
KeywordsExtremal graph theory
KeywordsLinear algebra
KeywordsSpectral graph theory
TitleSpectral Turán theorems and related problemsen_US
TypeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Desai_udel_0060D_14971.pdf
Size:
615.18 KB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.22 KB
Format:
Item-specific license agreed upon to submission
Description: