×

The super spanning connectivity of arrangement graphs. (English) Zbl 1390.05114

Summary: A \(k\)-container \(C(u, v)\) of a graph \(G\) is a set of \(k\) internally disjoint paths between \(u\) and \(v\). A \(k\)-container \(C(u, v)\) of \(G\) is a \(k^\ast\)-container if it is a spanning subgraph of \(G\). A graph \(G\) is \(k^\ast\)-connected if there exists a \(k^\ast\)-container between any two different vertices of G. A \(k\)-regular graph \(G\) is super spanning connected if \(G\) is \(i^\ast\)-container for all \(1 \leq i \leq k\). In this paper, we prove that the arrangement graph \(A_{n, k}\) is super spanning connected if \(n \geq 4\) and \(n - k \geq 2\).

MSC:

05C40 Connectivity
05C45 Eulerian and Hamiltonian graphs

References:

[1] Akers, S. B. and Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput.38(4) (1989) 555-566. · Zbl 0678.94026
[2] Akers, S. B., Harel, D. and Krishnamurthy, B., The star graph: An attractive alternative to the \(n\)-cube, Proceedings of International Conference on Parallel Processing (1987), 393-400.
[3] Albert, M., Aldred, R. E. L. and Holton, D., On \(3^\ast \)-connected graphs, Australas. J. Combin.24(1) (2001) 193-207. · Zbl 0982.05062
[4] Bondy, J. A. and Murty, U. S. R., Graph theory with applications, North Holland, New York, 1980. · Zbl 1226.05083
[5] Chiang, W. K. and Chen, R. J., On arrangement graph, Inform. Process. Lett.66 (1998) 215-219. · Zbl 1078.68674
[6] Day, K. and Tripathi, A., A class of generalized star graphs, Inform. Process. Lett.42(5) (1992) 235-241. · Zbl 0772.68005
[7] Day, K. and Tripathi, A., Embedding of cycles in arrangement graphs, IEEE Trans. Comput.42(8) (1993) 1002-1006. · Zbl 1395.05090
[8] Hsu, H. C., Li, T. K., Tan, J. J. M. and Hsu, L. H., Fault Hamiltonicity and fault Hamiltonian connectivy of the arrangement graphs, IEEE Trans. Comput.53(1) (2004) 39-53.
[9] Hsu, H. C., Lin, C. K., Huang, H. M. and Hsu, L. H., The spanning connectity of the \((n, k)\)-star graphs, Int. J. Fundations Comput. Sci.17 (2006) 415-434. · Zbl 1103.68097
[10] Lin, C. K., Huang, H. M. and Hsu, L. H., The super connectivity of the pancake graphs and the super laceability of the star graphs, Theoret. Comput. Sci.339 (2005) 257-271. · Zbl 1074.05054
[11] Li, J., Liu, D., Yang, Y. and Yuan, J., One-to-one disjoint path covers on multi-dimensional tori, Int. J. Fundations Comput. Sci.92(6) (2015) 257-271. · Zbl 1310.05190
[12] Lin, C. K., Tan, J. J. M., Hsu, D. F. and Hsu, L. H., On the spanning connectivity and spanning laceability of hypercube-like networks, Theoret. Comput. Sci.381 (2007) 218-229. · Zbl 1206.05060
[13] Lo, R. S. and Chen, G. H., Embedding Hamiltonian paths in faulty arrangement graphs with the backtracing method, IEEE Trans. Parallel Distrib. Syst.12(2) (2001) 209-222.
[14] Menger, K., Zur allgemeinen Kurventheorie, Fund. Math.10 (1927) 95-115. · JFM 53.0561.01
[15] Shih, Y. K. and Kao, S. S., One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theoret. Comput. Sci.412 (2011) 4513-4530. · Zbl 1223.68086
[16] Sun, S. N., Xu, M. and Wang, K. S., Edge-fault-tolerant pancyclicity of arrangement graphs, Inform. Sci.285 (2014) 50-62. · Zbl 1355.68026
[17] Tsai, C. H., Tan, J. J. M. and Hsu, L. H., The super connected property of recursive circulant graphs, Information Processing Lett.91 (2004) 293-298. · Zbl 1177.68031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.