|
|
完全二部图的强子图连通度
|
Abstract:
无向图G的广义k-连通度是在1985年由Hager引入的定义，这个概念后来又被人们推广到有向图中并提出了强子图k-连通度的定义。近年来，强子图k-连通度的研究在有向图上取得很多重要结果。在本文中，我们研究并给出了完全二部有向图上的强子图k-连通度的若干结果。
The definition of generalized connectivity of undirected graph G was introduced by Hager in 1985. This concept was extended to directed graph and the definition of strong subgraph k-connectivity was proposed. In recent years, the study of strong subgraph k-connectivity has achieved many im-portant results on directed graphs. In this paper, we study this concept and give some results on the strong subgraph k-connectivity on complete bipartite digraphs.
| [1] | Bang-Jensen, J. and Gutin, G.Z. (2009) Digraphs: Theory, Algorithms and Applications. 2nd Edition, Springer, London. https://doi.org/10.1007/978-1-84800-998-1 |
| [2] | Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory, Springer, Ber-lin. |
| [3] | Hager, M. (1985) Pendant Tree-Connectivity. Journal of Combinatorial Theory, Series B, 38, 179-189.
https://doi.org/10.1016/0095-8956(85)90083-8 |
| [4] | Li, S., Li, W. and Li, X. (2012) The Generalized Connectivity of Complete Bipartite Graphs, Ars Combinatoria, 104, 65-79. |
| [5] | Li, X. and Mao, Y. (2016) Generalized Connectivity of Graphs, Springer, Switzerland.
https://doi.org/10.1007/978-3-319-33828-6 |
| [6] | Sun, Y. and Gutin, G. (2021) Strong Subgraph Connectivity of Digraphs. Graphs and Combinatorics, 37, 951-970.
https://doi.org/10.1007/s00373-021-02294-w |
| [7] | Sun, Y.F. and Gutin, G., Yeo, A. and Zhang, X.Y. (2019) Strong Subgraph k-Connectivity. Journal of Graph Theory, 92, 5-18. https://doi.org/10.1002/jgt.22437 |
| [8] | Sun, Y.F. and Gutin, G. (2021) Strong Subgraph Connectivity of Digraphs: A Survey. Journal of Interconnection Networks, 21, Article No. 2142004. https://doi.org/10.1142/S0219265921420044 |
| [9] | Ng, L.L. (1997) Hamiltonian Decomposition of Complete Regular Multipartite Digraphs. Discrete Mathematics, 177, 279-285. https://doi.org/10.1016/S0012-365X(97)00017-4 |
| [10] | Tillson, T.W. (1980) A Hamiltonian Decomposition of , . Journal of Combinatorial Theory, Series B, 29, 68-74. https://doi.org/10.1016/0095-8956(80)90044-1 |
| [11] | Sun, Y., Gutin, G. and Zhang, X. (2021) Packing Strong Subgraph in Di-graphs. |
