The generalized k-connectivity of equally complete bipartite graphs and their line graphs

Swadi, Suaad A.; Najim, Alaa A.

doi:10.47974/JDMSC-1939

Open Access Research Article

The generalized k-connectivity of equally complete bipartite graphs and their line graphs

^*Suaad A. SwadiCorresponding authorsuaad.swadi@uobasrah.edu.iqDepartment of Mathematics College of Science University of BasrahBasrah, IraqView full profile → , Alaa A. Najimalaa.najim@uobasrah.edu.iqDepartment of Mathematics College of Science University of BasrahBasrah, IraqView full profile →

* Corresponding author · click or hover a name for details

pp. 1567–1573Vol. 27Issue 5August 2024DOI: 10.47974/JDMSC-1939 Crossmark XML

Received:: 14 Nov 2023
Published Online:: 26 Aug 2024
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1939
Pages:: 1567–1573

Abstract

Generalized k connectivity for graphs and generic graphs is recognized as NP-complete, a parameter that measures the network’s ability to connect vertices. Suppose km,n a completely connected bipartite graph represents the maximum number of internally disjoint Steiner trees (IDSTs) joining a subset S ⸦ V(G) of k vertices in G. In this context, Steiner trees (or “S -trees”) T1, T2 are considered internally detached if and only if V(T1) ∩ V(T2) = S and E(T1) ∩ E(T2) = ϕ. We define generalized k-connectivity as κk (G). This study focuses on calculating the precise values of generalized k-connectivity for line- graph of bipartite graphs with k = 3, 4 and generalized k-connectivity for bipartite graphs with k ≥ 3.

Keywords

Completed bipartite graph Generalized k-connectivity Line graph inwardly disjoint trees Steiner trees

Subject Classifications

05C1005C25

References

[1] Chen, L., Li, X., Liu, M., and Mao, Y. A solution to a conjecture on the generalized connectivity of graphs. Journal of Combinatorial Optimization 33, 1, 275–282 (Sep 2015).
[2] Dheyaa D. Kadhimand, A. A. N. The generalized 3-connectivity.of equally complete k-partite graph and its line graph. Journal: Basrah Journal of Science (2019).
[3] G. Chartrand, S. F. Kapoor, L. Lesniak, and D. R. Lick, “Generalized connectivity in graphs,” Bull. Bombay Math. Colloq, vol. 2, pp. 1–6 (1984).
[4] H. Li, X. Li, Y. Mao, and Y. Sun, Note on the generalized connectivity, Ars Combin., 114, 193-202 (2014).
[5] Li, H., Wu, B., Meng, J., and Ma, Y. Steiner tree packing number and tree connectivity. Discrete Mathematics 341, 7, 1945–1951 (Jul 2018).
[6] Li, S., Li, X., and Zhou, W. Sharp bounds for the generalized connectivity k3(g). Discrete Mathematics 310, 15-16, 2147–2163 (Aug 2010).
[7] Li, S., Tu, J., and Yu, C. The generalized 3-connectivity of star graphs and bubble-sort graphs. Applied Mathematics and Computation 274, 41–46 (Feb 2016).
[8] Li, Y., Gu, R., and Lei, H. The generalized connectivity of the line graph and the total graph for the complete bipartite graph. Applied Mathematics and Computation 347, 645–652 (Apr 2019).
[9] Lin, S., and Zhang, Q. The generalized 4-connectivity of hypercubes. Discrete Applied Mathematics 220, 60–67 (Mar 2017).
[10] S Li, W Li, X. L. The generalized connectivity of complete equipartition 3-partite graphs. Bull. Malays. Math. Sci. Soc (2014).
[11] S Li, W Li, X. L. a. p. a. The generalized connectivity of complete bipartite graphs. Ars Comb (2012).
[12] Xu, J. Topological Structure and Analysis of Interconnection Networks. Springer US (2001).
[13] Zhao, S.-L., and Chang, J.-M. Reliability assessment of the divide-and-swap cube in terms of generalized connectivity. Theoretical Computer Science 943, 1–15 (Jan. 2023).
[14] Zhao, S.-L., and Hao, R.-X. The generalized 4-connectivity of exchanged hypercubes. Applied Mathematics and Computation 347, 342–353 (Apr 2019).
[15] Zhao, S.-L., Hao, R.-X., and Wei, C. Internally disjoint trees in the line graph and total graph of the complete bipartite graph. Applied Mathematics and Computation 422, 126990 (Jun 2022).
[16] Zhu, W.-H., Hao, R.-X., Feng, Y.-Q., and Lee, J. Path connectivity of line graphs and total graphs of complete bipartite graphs. Applied Mathematics and Computation 457, 128182 (Nova. 2023).
[17] S. A. Swadi, A. A. Najim, and K. A. R. Swadi, “Some exact values for p(t,d),” Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, pp. 1399–1407 (Jun. 2020).
[18] S. A. Swadi and S. A. Abdul-Ghani, “Minimum diameter and tf(f,q),” Journal of Discrete Mathematical Sciences and Cryptography, vol. 24, pp. 1637–1644 (Mar. 2021).

Views: 203Downloads: 8Citations: 1