A unified approach to the spectral radius, connectivity and edge-connectivity of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929407568904192 |
|---|---|
| author | Wang, Yu Li, Dan Lin, Huiqiu |
| author_facet | Wang, Yu Li, Dan Lin, Huiqiu |
| contents | For two integers $r\geq 2$ and $h\geq 0$, the \emph{$h$-extra $r$-component connectivity} $κ^h_r(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 $\mathcal{G}_{n,δ}^{κ_r^h}$ the set of graphs with $h$-extra $r$-component connectivity $κ^h_r(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 $\mathscr{S}$, find an upper bound for the spectral radius of graphs in $\mathscr{S}$ and characterize the graphs in which the maximal spectral radius is attained. We study this question for $\mathscr{S}=\mathcal{G}_{n,δ}^{κ_r^h}$ where $r\geq 2$ and $h\geq 0$. Fan, Gu and Lin [$l$-connectivity, $l$-edge-connectivity and spectral radius of graphs, \emph{arXiv}:2309.05247] give the answer to $r\geq 2$ and $h=0$. In this paper, we solve this problem completely for $r\geq 2$ and $h\geq1$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20056 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A unified approach to the spectral radius, connectivity and edge-connectivity of graphs Wang, Yu Li, Dan Lin, Huiqiu Combinatorics For two integers $r\geq 2$ and $h\geq 0$, the \emph{$h$-extra $r$-component connectivity} $κ^h_r(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 $\mathcal{G}_{n,δ}^{κ_r^h}$ the set of graphs with $h$-extra $r$-component connectivity $κ^h_r(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 $\mathscr{S}$, find an upper bound for the spectral radius of graphs in $\mathscr{S}$ and characterize the graphs in which the maximal spectral radius is attained. We study this question for $\mathscr{S}=\mathcal{G}_{n,δ}^{κ_r^h}$ where $r\geq 2$ and $h\geq 0$. Fan, Gu and Lin [$l$-connectivity, $l$-edge-connectivity and spectral radius of graphs, \emph{arXiv}:2309.05247] give the answer to $r\geq 2$ and $h=0$. In this paper, we solve this problem completely for $r\geq 2$ and $h\geq1$. 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. |
| title | A unified approach to the spectral radius, connectivity and edge-connectivity of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.20056 |