2024/05/30 by Yu Wang, Dan Li, Wang, Yu +3 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Matrix Theory and Algorithms #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2405.20056
For two integers r≥ 2 and h≥ 0, the h-extra r-component connectivity κhr(G) of a graph G is defined to be the minimum size of a subset of vertices whose removal disconnects G, and there are at least r connected components in G - S and each component has at least h+1 vertices. Denote by Gn,δκrh the set of graphs with h-extra r-component connectivity κhr(G) and minimum degree δ. The following problem concerning spectral radius was proposed by Brualdi and Solheid [On the spectral radius of complementary acyclic matrices of zeros and one, SIAM J. Algebra Discrete Methods 7 (1986) 265-272]: Given a set of graphs \mathscrS, find an upper bound for the spectral radius of graphs in \mathscrS and characterize the graphs in which the maximal spectral radius is attained. We study this question for \mathscrS=Gn,δκrh where r≥ 2 and h≥ 0. Fan, Gu and Lin [l-connectivity, l-edge-connectivity and spectral radius of graphs, arXiv:2309.05247] give the answer to r≥ 2 and h=0. In this paper, we solve this problem completely for r≥ 2 and h≥1. Moreover, we also investigate analogous problems for the edge version. Our results can break the restriction of the extremum structure of the conditional connectivity. This implies some previous results in connectivity and edge-connectivity.