On the spectral radius of bipartite graphs with given order and 4-independence number
For a positive integer k , let P k be a path of order k . For a graph G , a subset S ⊆ V ( G ) is called a k -independent set if the induced subgraph G [ S ] does not contain P k as its subgraph. The k -independence number of G , denoted by α k ( G ), is the maximum cardinality of a k -independent set in G . Let B n,αk be the set of bipartite graphs of order n with k -independence number α k . What are the corresponding extremal graphs in B n,αk with the maximum spectral radius? Lou and Guo [ Discrete Math . 345 (2022) 112778] solved the problem for k = 2, and then Huang et al . [ Discrete Appl. Math . 342 (2024) 368–380] provided the answer for k = 3. We are interested in the analogous problem for k = 4. In the paper, we determine the unique graph attaining the maximum spectral radius among all bipartite graphs in B n,α 4 .
Authors
- Dan Li (ORCID: https://orcid.org/0000-0001-6105-7279)
- Wenxiu Ding
Institutions
- Xinjiang University (CN)
Publication Details
- Journal
- RAIRO. Operations research
- Published
- 2025-06-11
- DOI
- https://doi.org/10.1051/ro/2025073
- Primary Topic
- Graph theory and applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Natural Science Foundation of Xinjiang Province
- National Natural Science Foundation of China