On maximum spectral radius of {H (3, 3), H (4, 3)}-free graphs

Let 퐺 be a simple connected graph of size 푚. Let 퐴 be the adjacency matrix of 퐺 and let 휌(퐺) be the spectral radius of 퐺. A graph is said to be 퐻free if it does not contain a subgraph isomorphic to 퐻. Let 퐻(ℓ, 3) be the graph formed by taking a cycle of length ℓ and a triangle on a common vertex. Recently, Li, Lu and Peng [Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie, Discrete Math. 346(12) (2023) 113680.] showed that the unique 푚-edge 퐻(3, 3)-free spectral extremal graph is the join of 퐾2 with an independent set of 푚−1 2 vertices if 푚 ≥ 8 and the condition 푚 ≥ 8 is tight. In particular, if 퐺 does not contain 퐻(3, 3) as induced subgraph, they proved that 휌(퐺) ≤ 1+ √ 4푚−3 2 and equality holds when 퐺 is isomorphic to 푆 푚+3 2 ,2 . Note that Li et al. denoted 퐻(3, 3) by 퐹2. In this paper, we find the maximum spectral radius and identify the graph with the largest spectral radius among all {퐻(3, 3), 퐻(4, 3)}- free graphs of size odd 푚, where 푚 ≥ 259. Coincidently, we show that 휌(퐺) ≤ 1+ √ 4푚−3 2 when 퐺 forbids both 퐻(3, 3) and 퐻(4, 3). In our case, the equality holds when 퐺 is isomorphic to the same graph.

Authors

Institutions

Publication Details

Journal
Acta Universitatis Sapientiae Informatica
Published
2024-10-01
DOI
https://doi.org/10.47745/ausi-2024-0008
Citations
4
Primary Topic
Graph theory and applications
Type
article
Field-Weighted Citation Impact
4.05

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

On maximum spectral radius of {H (3, 3), H (4, 3)}-free graphs

S. Pirzada, Amir Rehman
4 citations
Acta Universitatis Sapientiae Informatica
Graph theory and applications
4.05
article

On maximum spectral radius of {H (3, 3), H (4, 3)}-free graphs

S. Pirzada, Amir Rehman
article en
4 citations

Abstract

Let 퐺 be a simple connected graph of size 푚. Let 퐴 be the adjacency matrix of 퐺 and let 휌(퐺) be the spectral radius of 퐺. A graph is said to be 퐻free if it does not contain a subgraph isomorphic to 퐻. Let 퐻(ℓ, 3) be the graph formed by taking a cycle of length ℓ and a triangle on a common vertex. Recently, Li, Lu and Peng [Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie, Discrete Math. 346(12) (2023) 113680.] showed that the unique 푚-edge 퐻(3, 3)-free spectral extremal graph is the join of 퐾2 with an independent set of 푚−1 2 vertices if 푚 ≥ 8 and the condition 푚 ≥ 8 is tight. In particular, if 퐺 does not contain 퐻(3, 3) as induced subgraph, they proved that 휌(퐺) ≤ 1+ √ 4푚−3 2 and equality holds when 퐺 is isomorphic to 푆 푚+3 2 ,2 . Note that Li et al. denoted 퐻(3, 3) by 퐹2. In this paper, we find the maximum spectral radius and identify the graph with the largest spectral radius among all {퐻(3, 3), 퐻(4, 3)}- free graphs of size odd 푚, where 푚 ≥ 259. Coincidently, we show that 휌(퐺) ≤ 1+ √ 4푚−3 2 when 퐺 forbids both 퐻(3, 3) and 퐻(4, 3). In our case, the equality holds when 퐺 is isomorphic to the same graph.

Acta Universitatis Sapientiae InformaticaVol. 16(1)
University of Kashmir (IN)
Council of Scientific and Industrial Research, India, National Board for Higher Mathematics
Openalex Percentile: Top 5%
Graph theory and applications
4.05
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

On maximum spectral radius of {H (3, 3), H (4, 3)}-free graphs — S. Pirzada, Amir Rehman · Acta Universitatis Sapientiae Informatica (2024) | TGRS Research Map | TGRS