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
- S. Pirzada (ORCID: https://orcid.org/0000-0002-1137-517X)
- Amir Rehman
Institutions
- University of Kashmir (IN)
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
- Council of Scientific and Industrial Research, India
- National Board for Higher Mathematics