K_r+1-saturated graphs with small spectral radius

2020/06/08 by Jaehoon Kim, Seog Jin Kim, Kim, Jaehoon +5 · 1 citation
Mathematics · #Graph theory and applications #Limits and Structures in Graph Theory #Finite Group Theory Research

paper · pdf · doi:10.48550/arxiv.2006.04355

Abstract

For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e ∈ E(G), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex K_r+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n→∞.

Cited by

• Minimizing the number of complete bipartite graphs in a K_s-saturated\n graph

Related

• Remarks on the spectral radius of K_r+1-saturated graphs
• K_r-saturated Graphs and the Two Families Theorem
• Cycle-saturated graphs with minimum number of edges
• A lower bound on the saturation number, and graphs for which it is sharp
• Extremal problems on saturation for the family of k-edge-connected graphs