On the problem of determining which \((n, k)\)-star graphs are Cayley graphs. (English) Zbl 1365.05121
Summary: In this paper we work to classify which of the \((n, k)\)-star graphs, denoted by \(S_{n,k}\), are Cayley graphs. Although the complete classification is left open, we derive infinite and non-trivial classes of both Cayley and non-Cayley graphs. We give a complete classification of the case when \(k=2\), showing that \(S_{n,2}\) is Cayley if and only if \(n\) is a prime power. We also give a sufficient condition for \(S_{n,3}\) to be Cayley and study other structural properties, such as demonstrating that \(S_{n,k}\) always has a uniform shortest path routing.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
References:
| [1] | Araki, T.: Hyper Hamiltonian laceability of Cayley graphs generated by transpositions. Networks 48, 121-124 (2006) · Zbl 1117.05068 · doi:10.1002/net.20126 |
| [2] | Cheng, E., Grossman, J., Qiu, K., Shen, Z.: Distance formula and shortest paths of the \[(n, k)\](n,k)-star graphs. Inf. Sci. 180, 1671-1680 (2010) · Zbl 1203.05042 · doi:10.1016/j.ins.2010.01.016 |
| [3] | Cheng, E., Lipman, M.J.: Vulnerability issues of star graphs, alternating group graphs and split-stars: strength and toughness. Discret. Appl. Math. 118, 163-179 (2002) · Zbl 0999.05063 · doi:10.1016/S0166-218X(01)00234-7 |
| [4] | Cheng, E., Lipman, M.J.: Increasing the connectivity of the star graphs. Networks 40, 165-169 (2002) · Zbl 1018.05055 · doi:10.1002/net.10045 |
| [5] | Cheng, E., Lipták, L., Shawash, N.: Orienting Cayley graphs generated by transposition trees. Comput. Math. Appl. 55, 2662-2672 (2008) · Zbl 1142.05327 · doi:10.1016/j.camwa.2007.10.016 |
| [6] | Cheng, E., Lipták, L., Steffy, D.E.: Strong local diagnosability of \[(n, k)\](n,k)-star graphs and Cayley graphs generated by 2-trees with missing edges. Inf. Process. Lett. 113, 452-456 (2013) · Zbl 1358.05291 · doi:10.1016/j.ipl.2013.03.002 |
| [7] | Cheng, E., Qiu, K., Shen, Z.: A short note on the surface area of star graphs. Parallel Process. Lett. 19, 19-22 (2009) · Zbl 1520.05082 · doi:10.1142/S0129626409000031 |
| [8] | Cheng, E., Qiu, K., Shen, Z.: A generating function approach to the surface area of some interconnection networks. J. Interconnect. Netw. 10, 189-204 (2009) · doi:10.1142/S0219265909002510 |
| [9] | Cheng, E., Qiu, K., Shen, Z.: A note on the alternating group network. J. Supercomput. 59, 246-248 (2012) · doi:10.1007/s11227-010-0434-y |
| [10] | Cheng, E., Qiu, K., Shen, Z.: The number of shortest paths in the \[(n, k)\](n,k)-star graphs. Discret. Math. Algorithms Appl. 1450051 (2014). doi:10.1142/S1793830914500517 · Zbl 1303.05087 |
| [11] | Chiang, W.-K., Chen, R.-J.: The \[(n, k)\](n,k)-star graph: a generalized star graph. Inf. Process. Lett. 56, 259-264 (1995) · Zbl 1027.68645 · doi:10.1016/0020-0190(95)00162-1 |
| [12] | Chung Jr., F.R.K., Coffman, E.G., Reiman, M.I., Simon, B.: The forwarding index of communication networks. IEEE Trans. Inf. Theory 33, 224-232 (1987) · Zbl 0626.94019 · doi:10.1109/TIT.1987.1057290 |
| [13] | Duh, D.-R., Chen, T.-L., Wang, Y.-L.: \[(n-3)\](n-3)-edge-fault-tolerant weak-pancyclicity of \[(n, k)\](n,k)-star graphs. Theor. Comput. Sci. 516, 28-39 (2014) · Zbl 1277.68221 · doi:10.1016/j.tcs.2013.11.013 |
| [14] | Gargano, L., Vaccaro, U., Vozella, A.: Fault tolerant routing in the star and pancake interconnection networks. Inf. Process. Lett. 45, 315-320 (1993) · Zbl 0777.68026 · doi:10.1016/0020-0190(93)90043-9 |
| [15] | Gauyacq, G.: Edge-forwarding index of star graphs and other Cayley graphs. Discr. Appl. Math. 80, 149-160 (1997) · Zbl 0897.05043 · doi:10.1016/S0166-218X(97)00052-8 |
| [16] | Gu, Q., Peng, S.: An efficient algorithm for \[k\] k-pairwise disjoint paths in star graphs. Inf. Process. Lett. 67, 283-287 (1998) · Zbl 1339.68205 · doi:10.1016/S0020-0190(98)00121-5 |
| [17] | Gu, Q., Peng, S.: Cluster fault tolerant routing in star graphs. Networks 35, 83-90 (2000) · Zbl 0938.90068 · doi:10.1002/(SICI)1097-0037(200001)35:1<83::AID-NET7>3.0.CO;2-D |
| [18] | Hungerford, T.: Algebra, Graduate Texts in Mathematics, vol. 73. Springer, New York (1980) · Zbl 0442.00002 |
| [19] | Heydemann, M.-C., Meyer, J.-C., Sotteau, D.: On the-forwarding index of networks. Discret. Appl. Math. 23, 103-123 (1989) · Zbl 0681.90077 · doi:10.1016/0166-218X(89)90022-X |
| [20] | Hoelzeman, D.A., Bettayeb, S.: On the genus of the star graphs. IEEE Trans. Comput. 43, 755-759 (1994) · Zbl 1042.68636 · doi:10.1109/12.286309 |
| [21] | Hsu, H.-C., Hsieh, Y.-L., Tan, J.J.M., Hsu, L.H.: Fault Hamiltonicity and fault Hamiltonian connectivity of the \[(n, k)\](n,k)-star graphs. Networks 42, 189-201 (2003) · Zbl 1031.05079 · doi:10.1002/net.10096 |
| [22] | Irving, J., Ratton, A.: Minimal factorizations of permutations into star transpositions. Discret. Math. 309, 1549-1554 (2009) · Zbl 1181.05004 · doi:10.1016/j.disc.2008.02.018 |
| [23] | Ji, Y.: A new class of Cayley networks based on the alternating groups. Appl. Math. A J. Chin. Univ. 14, 235-239 (1999) · Zbl 0948.94025 |
| [24] | Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings, San Francisco (1994) · Zbl 0861.68040 |
| [25] | Latifi, S.: A study of fault tolerance in star graph. Inf. Process. Lett. 102, 196-200 (2007) · Zbl 1184.68115 · doi:10.1016/j.ipl.2006.12.013 |
| [26] | Li, T.-K., Tan, J.J.M., Hsu, L.-H.: Hyper hamiltonian laceability on edge fault star graph. Inf. Sci. 165, 59-71 (2004) · Zbl 1057.05054 · doi:10.1016/j.ins.2003.09.023 |
| [27] | Mendia, V.E., Sarkar, D.: Optimal broadcasting on the star graphs. IEEE Trans. Parallel Distrib. Syst. 3, 389-396 (1992) · doi:10.1109/71.149958 |
| [28] | Sabidussi, G.: On a class of fixed-point-free graphs. Proc. Am. Math. Soc. 5, 800-804 (1958) · Zbl 0091.37701 · doi:10.1090/S0002-9939-1958-0097068-7 |
| [29] | Sheu, J.P., Wu, C.Y., Chen, T.S.: An optimal broadcasting algorithm without message redundancy in star graphs. Trans. Parallel Distrib. Syst. 6, 653-658 (1995) · doi:10.1109/71.388046 |
| [30] | Shen, X., Hu, Q., Cong, B., Sudborough, H., Girou, M., Bettayeb, S.: The 4-star graph is not a subgraph of any hypercube. Inf. Process. Lett. 37, 199-203 (1993) · Zbl 0768.68179 · doi:10.1016/0020-0190(93)90119-T |
| [31] | Shen, Z., Qiu, K., Cheng, E.: On the surface area of the \[(n, k)\](n,k)-star graph. Theor. Comput. Sci. 410, 5481-5490 (2009) · Zbl 1192.68492 · doi:10.1016/j.tcs.2009.05.007 |
| [32] | Shim, S., Siran, J., Zerovnik, J.: Counterexamples to the uniform shortest path routing conjecture for vertex-transitive graphs. Discret. Appl. Math. 119, 281-286 (2002) · Zbl 1019.90013 · doi:10.1016/S0166-218X(01)00310-9 |
| [33] | Tanaka, Y., Kikuchi, Y., Araki, T., Shibata, Y.: Bipancyclic properties of Cayley graphs generated by transpositions. Discret. Math. 310, 748-754 (2010) · Zbl 1214.05051 · doi:10.1016/j.disc.2009.09.002 |
| [34] | Tseng, Y.C., Chen, Y.S., Juang, T.Y., Chang, C.J.: Congestion-free, dilation-2 embedding of complex binary trees into star graphs. Networks 33, 221-231 (1999) · Zbl 0923.05020 · doi:10.1002/(SICI)1097-0037(199905)33:3<221::AID-NET8>3.0.CO;2-K |
| [35] | Tseng, Y.C., Sheu, J.P.: Toward optimal broadcast in a star graph using multiple spanning tree. IEEE Trans. Comput. 46, 593-599 (1997) · doi:10.1109/12.589231 |
| [36] | Wei, Y., Chen, F.: Generalized connectivity of \[(n, k)\](n,k)-star graphs. Int. J. Found. Comput. Sci. 24, 1235-1241 (2013) · Zbl 1298.05186 · doi:10.1142/S0129054113500317 |
| [37] | Xiang, Y., Stewart, I.A.: One-to-many node-disjoint paths in \[(n, k)\](n,k)-star graphs. Discret. Appl. Math. 158, 62-70 (2010) · Zbl 1226.05239 · doi:10.1016/j.dam.2009.08.013 |
| [38] | Yeh, C.H., Parhami, B.: VLSI layouts of complete graphs and star graphs. Inf. Process. Lett. 68, 39-45 (1998) · Zbl 1339.68216 · doi:10.1016/S0020-0190(98)00133-1 |
| [39] | Yuan, A., Cheng, E., Lipták, L.: Linearly many faults in \[(n, k)\](n,k)-star graphs. Int. J. Found. Comput. Sci. 22, 1729-1745 (2011) · Zbl 1251.68172 · doi:10.1142/S0129054111008994 |
| [40] | Zhou, S.M., Xiao, W.J., Parhami, B.: Construction of vertex-disjoint paths in alternating group networks. J. Supercomput. 54, 206-228 (2010) · doi:10.1007/s11227-009-0304-7 |
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.
