Super spanning connectivity of the cartesian product of complete graphs

Articles in Press

Document Type : Original paper

Authors

College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, P. R. China

Abstract

Let $G$ be a graph and $s$ be an integer. {\textit{A $s$-container $C(x,y)$} of $G$ between two vertices $x$ and $y$ is a set of $s$ internally vertex disjoint $x,y$-paths. A $s$-container $C(x,y)$ is \textit{a $s^{*}$-container} if $V(C(x,y))=V(G)$, where $V(C(x, y))$ is the set of vertices incident with some paths in $C(x,y)$. Then $G$ is \textit{$s^{*}$-connected} if there exists a $s^{*}$-container between any two distinct vertices of $G$. \textit{The spanning connectivity $\kappa^{*}(G)$} of $G$ is the largest integer $k$ such that $G$ is $s^{*}$-connected for any $s$ with $1 \leq s \leq k$. Further, $G$ is \textit{super spanning connected} if $\kappa^{*}(G)=\kappa(G)$, where $\kappa(G)$ is the connectivity of $G$. In this paper, we show that the $n$-th cartesian product of complete graph $K_{t}$ $(t\ge 3)$ is super spanning connected. Our results, in some sense, extended a previous result in \textit{[Shih et al., One-to-one disjoint path covers on $k$-ary $n$-cubes, Theoret. Comput. Sci. (2011)]}.

Keywords

Main Subjects

References

[1] A. Bondy and U.S.R. Murty, Graph Theory, Springer London, 2009.
[2] C.H. Chang, C.K. Lin, H.M. Huang, and L.H. Hsu, The super laceability of the hypercubes, Inform. Process. Lett. 92 (2004), no. 1, 15–21. https://doi.org/10.1016/j.ipl.2004.06.006
[3] C.H. Chang, C.K. Lin, J.J.M. Tan, H.M. Huang, and L.H. Hsu, The super spanning connectivity and super spanning laceability of the enhanced hypercubes, J. Supercomput. 48 (2009), no. 1, 66–87. https://doi.org/10.1007/s11227-008-0206-0
[4] X.B. Chen, Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs, Inform. Process. Lett. 110 (2010), no. 6, 203–205.  https://doi.org/10.1016/j.ipl.2009.12.004
[5] Y. Chen, Z.H. Chen, H.J. Lai, P. Li, and E. Wei, On spanning disjoint paths in line graphs, Graphs Combin. 29 (2013), no. 6, 1721–1731.  https://doi.org/10.1007/s00373-012-1237-0
[6] C. Chin, T.H. Weng, L.H. Hsu, and S.C. Chiou, The spanning connectivity of the burnt pancake graphs, IEICE Trans. Inf. Syst. E92-D (2009), no. 3, 389–400.  https://doi.org/10.1587/transinf.E92.D.389
7] K. Day and A.E. Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Trans. Parallel Distrib. Syst. 8 (2002), no. 9, 903–907. https://doi.org/10.1109/71.615436
[8] T. Gomes, J. Craveirinha, and L. Jorge, An effective algorithm for obtaining the minimal cost pair of disjoint paths with dual arc costs, Comput. Oper. Res. 36 (2009), no. 5, 1670–1682. https://doi.org/10.1016/j.cor.2008.04.002
[9] H.C. Hsu, C.K. Lin, H.M. Hung, and L.H. Hsu, The spanning connectivity of the $(n, k)$-star graphs, Internat. J. Found. Comput. Sci. 17 (2006), no. 02, 415–434. https://doi.org/10.1142/S0129054106003905
[10] J. Li, X. Li, and E. Cheng, Super spanning connectivity of split-star networks, Inform. Process. Lett. 166 (2021), Article ID: 106037. https://doi.org/10.1016/j.ipl.2020.106037
[11] J. Li, D. Liu, Y. Yang, and J. Yuan, One-to-one disjoint path covers on multidimensional tori, Int. J. Comput. Math. 92 (2015), no. 6, 1114–1123. https://doi.org/10.1080/00207160.2014.940334
[12] P. Li and M. Xu, The super spanning connectivity of arrangement graphs, Int. J. Found. Comput. Sci. 28 (2017), no. 08, 1047–1072. https://doi.org/10.1016/j.ipl.2020.106037
[13] C.K. Lin, H.M. Huang, and L.H. Hsu, The super connectivity of the pancake graphs and the super laceability of the star graphs, Theor. Comput. Sci. 339 (2005), no. 2-3, 257–271. https://doi.org/10.1016/j.tcs.2005.02.007
[14] C.K. Lin, H.M. Huang, J.J.M. Tan, and L.H. Hsu, On spanning connected graphs, Discrete Math. 308 (2008), no. 7, 1330–1333.  https://doi.org/10.1016/j.disc.2007.03.072
[15] C.K. Lin, J.J.M. Tan, D.F. Hsu, and L.H. Hsu, On the spanning connectivity and spanning laceability of hypercube-like networks, Theor. Comput. Sci. 381 (2007), no. 1-3, 218–229. https://doi.org/10.1016/j.tcs.2007.05.002
[16] C. Liu, M. Yarvis, W.S. Conner, and X. Guo, Guaranteed on-demand discovery of node-disjoint paths in ad hoc networks, Comput. Commun. 30 (2007), no. 14-15, 2917–2930. https://doi.org/10.1016/j.disc.2007.03.072
[17] J.H. Park, H.C. Kim, and H.S. Lim, Many-to-many disjoint path covers in the presence of faulty elements, IEEE Trans. Comput. 58 (2008), no. 4, 528–540. https://doi.org/10.1109/TC.2008.160
[18] Y.K. Shih and S.S. Kao, One-to-one disjoint path covers on k-ary n-cubes, Theor. Comput. Sci. 412 (2011), no. 35, 4513–4530 https://doi.org/10.1016/j.tcs.2011.04.035
[19] F. Wang and W. Zhao, One-to-one disjoint path covers in hypercubes with faulty edges, J. Supercomput. 75 (2019), no. 8, 5583–5595.  https://doi.org/10.1007/s11227-019-02817-6
[20] X. Wang, J. Fan, X. Jia, and C.K. Lin, An efficient algorithm to construct disjoint path covers of DCell networks, Theor. Comput. Sci. 609 (2016), no. 1, 197–210.  https://doi.org/10.1016/j.tcs.2015.09.022
[21] J.M. Xu, Combinatorial theory in networks, Academic Press, Beijing, 2013.
[22] M.C. Yang, J.J.M. Tan, and L.H. Hsu, Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes, J. Parallel Distrib. Comput. 67 (2007), no. 4, 362–368.  https://doi.org/10.1016/j.jpdc.2005.10.004
[23] L. You, J. Fan, and Y. Han, Super spanning connectivity on WK-recursive networks, Theor. Comput. Sci. 713 (2018), 42–55.  https://doi.org/10.1016/j.tcs.2017.12.023
[24] L. You, J. Fan, Y. Han, and X. Jia, One-to-one disjoint path covers on alternating group graphs, Theor. Comput. Sci. 562 (2015), 146–164.  https://doi.org/10.1016/j.tcs.2014.09.041
[25] L. You, J. Jiang, and Y. Han, Super spanning connectivity of the folded divideand-swapcube, Mathematics 11 (2023), no. 11, Article ID: 2581 https://doi.org/10.3390/math11112581
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 20 July 2025

Files

Share

How to cite

Statistics