×

Maximal vertex-connectivity of \(\overset\longrightarrow{S_{n,k}}\). (English) Zbl 1081.05057

A class of generalized star graphs called \((n,k)\)-star graphs (first introduced by Chiang and Chen) is considered. The vertex-connectivity of the directed \((n,k)\)-star graphs is studied and it is shown that these graphs are maximally connected.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bagherzadeh, IEEE Trans Parallel Dist Syst 6 pp 531– (1995)
[2] Bai, J Graph Algorithms Appl 2 (1998) · Zbl 0895.68063 · doi:10.7155/jgaa.00005
[3] Chen, IEEE Trans Parallel Dist Syst 7 pp 717– (1996)
[4] Cheng, Inform Proc Lett 73 pp 5– (2000)
[5] Cheng, Networks 35 pp 139– (2000)
[6] Cheng, Congressus Numer 150 pp 33– (2001)
[7] Cheng, Electronic Notes Dis Math 11 (2002)
[8] Cheng, J Interconnect Networks 3 pp 19– (2002)
[9] Cheng, Discrete App Math 118 pp 163– (2002)
[10] Cheng, Ars Combinat 59 pp 107– (2001)
[11] , , ” Uni-directional alternating group graphs,” Computing and combinatorics (Xi’an, 1995), Lecture Notes in Computer Science, 959, 1995, pp. 490-495.
[12] Chiang, Inform Proc Lett 56 pp 259– (1995)
[13] Chiang, Inform Proc Lett 66 pp 215– (1998)
[14] Chiang, Int J Found Comp Sci 9 pp 235– (1998)
[15] , Unidirectional hypercubes, Proc. Supercomputing’90, 1990, pp. 254-263.
[16] Comellas, Discrete Appl Math 58 pp 1– (1995)
[17] Day, Inform Proc Lett 42 pp 235– (1992)
[18] Day, IEEE Trans Comput 12 pp 1002– (1992)
[19] Day, Proc Int Con Parallel Processing, pp iii– (1993)
[20] Day, Inform Proc Lett 45 pp 123– (1993)
[21] Day, Kuwait J Sci Eng 25 pp 35– (1998)
[22] , , ” The star graph: An attractive alternative to the n-cube”, Proc Intl Conf Parallel Processing, 1987, pp. 393-400.
[23] Jwo, Networks 32 pp 307– (1998)
[24] Mendia, IEEE Trans Parallel Dist Sys 3 pp 389– (1992)
[25] , , , ” The unique ninimum dominating set of directed split-stars”, Proceedings of National Computer Symposium (NCS’01), Taipei, Taiwan, 2001, pp. A147-A152.
[26] , , , ” Distributed algorithms of finding the unique ninimum dominating set of directed split-stars,” The 19th Workshop on Combinatorial Mathematics and Computation Theory, National Sun Yat-Sen University, Kaohsiung, 2002.
[27] Introduction to graph theory, Prentice Hall, Englewood Cliffs, NJ, 1996. · Zbl 0891.05001
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.