A sharp upper bound on the spectral radius of C5-free /C6-free graphs with given size

被引:24
作者
Min, Gao [1 ]
Lou, Zhenzhen [1 ,2 ]
Huang, Qiongxiang [1 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
[2] East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China
基金
中国博士后科学基金; 中国国家自然科学基金;
关键词
Cycle; Forbidden subgraph; Spectral radius; Adjacency matrix; NUMBERS; CLIQUE;
D O I
10.1016/j.laa.2022.01.016
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let S-n,S-2 be the graph obtained by joining each vertex of K-2 to n - 2 isolated vertices, and let S-n,2(-) be the graph obtained from S-n,S-2 by deleting an edge incident to a vertex of degree two. Recently, Zhai, Lin and Shu [20] showed that rho(G) <= 1+root 4m-3/2 for any C-5-free graph of size m >= 8 or C-6-free graph of size m >= 22, with equality if and only if G congruent to S-m+3/2,S-2 (possibly, with some isolated vertices). However, this bound is sharp only for odd m. Motivated by this, we want to obtain a sharp upper bound of rho(G) for C-5-free or C-6-free graphs with medges. In this paper, we prove that if Gis a C-5-free graph of even size m >= 14 or C-6-free graph of even size m >= 74, and G contains no isolated vertices, then rho(G) <= (rho) over tilde (m), with equality if and only if G congruent to S-m+4/2,2(-), where (rho) over tilde (m) is the largest root of x(4) - mx(2) - (m - 2)x + ( m/2 - 1) = 0. (c) 2022 Elsevier Inc. All rights reserved.
引用
收藏
页码:162 / 178
页数:17
相关论文
共 20 条
[1]  
Babai L, 2009, ELECTRON J COMB, V16
[2]   Cliques and the spectral radius [J].
Bollobas, Bela ;
Nikiforov, Vladimir .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (05) :859-865
[3]   ON THE SPECTRAL-RADIUS OF (0,1)-MATRICES [J].
BRUALDI, RA ;
HOFFMAN, AJ .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1985, 65 (FEB) :133-146
[4]  
Cvetkovic D., 2010, An Introduction to the Theory of Graph Spectra, DOI DOI 10.1017/CBO9780511801518
[5]   LOWER BOUNDS FOR THE CLIQUE AND THE CHROMATIC-NUMBERS OF A GRAPH [J].
EDWARDS, CS ;
ELPHICK, CH .
DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :51-64
[6]  
Elphick C., 2021, GENERALISING CONJECT
[7]   Adjacency eigenvalues of graphs without short odd cycles [J].
Li, Shuchao ;
Sun, Wanting ;
Yu, Yuantian .
DISCRETE MATHEMATICS, 2022, 345 (01)
[8]   Eigenvalues and triangles in graphs [J].
Lin, Huiqiu ;
Ning, Bo ;
Wu, Baoyindureng .
COMBINATORICS PROBABILITY & COMPUTING, 2021, 30 (02) :258-270
[9]   Some inequalities for the largest eigenvalue of a graph [J].
Nikiforov, V .
COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (02) :179-189
[10]   A spectral condition for odd cycles in graphs [J].
Nikiforov, Vladimir .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) :1492-1498