Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected
Let G be a connected graph with minimum degree δG and vertex-connectivity κG. The graph G is k-connected if κG≥k, maximally connected if κG=δG, and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/5588146 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547627715002368 |
|---|---|
| author | Zhen-Mu Hong Zheng-Jiang Xia Fuyuan Chen Lutz Volkmann |
| author_facet | Zhen-Mu Hong Zheng-Jiang Xia Fuyuan Chen Lutz Volkmann |
| author_sort | Zhen-Mu Hong |
| collection | DOAJ |
| description | Let G be a connected graph with minimum degree δG and vertex-connectivity κG. The graph G is k-connected if κG≥k, maximally connected if κG=δG, and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given minimum degree to be k-connected, maximally connected, or super-connected in terms of the number of edges, the spectral radius of the graph, and its complement, respectively. Analogous results for triangle-free graphs with given minimum degree to be k-connected, maximally connected, or super-connected are also presented. |
| format | Article |
| id | doaj-art-3b8afb12f25143c29b1c5549ca8c33a5 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-3b8afb12f25143c29b1c5549ca8c33a52025-02-03T06:43:55ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/55881465588146Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-ConnectedZhen-Mu Hong0Zheng-Jiang Xia1Fuyuan Chen2Lutz Volkmann3School of Finance, Anhui University of Finance & Economics, Bengbu 233030, ChinaSchool of Finance, Anhui University of Finance & Economics, Bengbu 233030, ChinaInstitute of Statistics and Applied Mathematics, Anhui University of Finance & Economics, Bengbu 233030, ChinaLehrstuhl II für Mathematik, RWTH Aachen University, Aachen 52056, GermanyLet G be a connected graph with minimum degree δG and vertex-connectivity κG. The graph G is k-connected if κG≥k, maximally connected if κG=δG, and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given minimum degree to be k-connected, maximally connected, or super-connected in terms of the number of edges, the spectral radius of the graph, and its complement, respectively. Analogous results for triangle-free graphs with given minimum degree to be k-connected, maximally connected, or super-connected are also presented.http://dx.doi.org/10.1155/2021/5588146 |
| spellingShingle | Zhen-Mu Hong Zheng-Jiang Xia Fuyuan Chen Lutz Volkmann Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected Complexity |
| title | Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected |
| title_full | Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected |
| title_fullStr | Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected |
| title_full_unstemmed | Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected |
| title_short | Sufficient Conditions for Graphs to Be k-Connected, Maximally Connected, and Super-Connected |
| title_sort | sufficient conditions for graphs to be k connected maximally connected and super connected |
| url | http://dx.doi.org/10.1155/2021/5588146 |
| work_keys_str_mv | AT zhenmuhong sufficientconditionsforgraphstobekconnectedmaximallyconnectedandsuperconnected AT zhengjiangxia sufficientconditionsforgraphstobekconnectedmaximallyconnectedandsuperconnected AT fuyuanchen sufficientconditionsforgraphstobekconnectedmaximallyconnectedandsuperconnected AT lutzvolkmann sufficientconditionsforgraphstobekconnectedmaximallyconnectedandsuperconnected |