×

Orienting Cayley graphs generated by transposition trees. (English) Zbl 1142.05327

Summary: K. Day and A. Tripathi [Inf. Process. Lett. 45, 123-129 (1993; Zbl 0768.68135)] proposed an assignment of directions on the star graphs and derived attractive properties for the resulting directed graphs. E. Cheng and M. J. Lipman [On the Day-Tripathi orientation of the star graphs: Connectivity, Inform. Proc. Lett. 73, 5-10 (2000); Congr. Numerantium 150, 33–42 (2001; Zbl 0994.05084)] studied the connectivity properties of these unidirectional star graphs. The class of star graphs is a special case of Cayley graphs generated by transposition trees. In this paper, we give directions on these graphs and study the connectivity properties of the resulting unidirectional graphs.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Day, K.; Tripathi, A., Unidirectional star graphs, Inform. Process. Lett., 45, 123-129 (1993) · Zbl 0768.68135
[2] Cheng, E.; Lipman, M. J., On the Day-Tripathi orientation of the star graphs: Connectivity, Inform. Process. Lett., 73, 5-10 (2000) · Zbl 1339.68202
[3] Cheng, E.; Lipman, M. J., Connectivity properties of unidirectional star graphs, Congr. Numer., 150, 33-42 (2001) · Zbl 0994.05084
[4] Cheng, E.; Lipman, M. J., Orienting split-stars and alternating group graphs, Networks, 35, 139-144 (2000) · Zbl 0957.90012
[5] Chern, S. C.; Jwo, J. S.; Tuan, T. C., Uni-directional alternating group graphs, (Lecture Notes in Comput. Sci., 959 (1995), Springer: Springer Berlin), 490-495
[6] C.H. Chou, D.H.C. Du, Unidirectional hypercubes, in: Proc. Supercomputing’90, 1990, pp. 254-263; C.H. Chou, D.H.C. Du, Unidirectional hypercubes, in: Proc. Supercomputing’90, 1990, pp. 254-263
[7] Comellas, F.; Fiol, M. A., Vertex-symmetric digraphs with small diameter, Discrete Appl. Math., 58, 1-11 (1995) · Zbl 0822.05033
[8] Jwo, J. S.; Tuan, T. C., On container length and connectivity in unidirectional hypercubes, Networks, 32, 307-317 (1998) · Zbl 1015.68010
[9] Cheng, E.; Lipman, M. J., Orienting the arrangement graphs, Congr. Numer., 142, 97-112 (2000) · Zbl 0980.68083
[10] Cheng, E.; Lipman, M. J., Unidirectional \((n, k)\)-star graphs, J. Interconnection Networks, 3, 19-34 (2002)
[11] Cheng, E.; Lindsey, W. A.; Steffy, D. E., Maximal vertex-connectivity of \(\overset{\vec{}}{S_{n, k}} \), Networks, 46, 154-162 (2005) · Zbl 1081.05057
[12] S.B. Akers, D. Harel, B. Krishnamurthy, The star graph: An attractive alternative to the \(n\)-cube, in: Proc. Int’l Conf. Parallel Processing, 1987, pp. 393-400; S.B. Akers, D. Harel, B. Krishnamurthy, The star graph: An attractive alternative to the \(n\)-cube, in: Proc. Int’l Conf. Parallel Processing, 1987, pp. 393-400
[13] S.B. Akers, B. Krishnamurthy, A group theoretic model for symmetric interconnection networks, in: Pro. Int’l. Conf. Parallel Proc., 1986, pp. 216-223; S.B. Akers, B. Krishnamurthy, A group theoretic model for symmetric interconnection networks, in: Pro. Int’l. Conf. Parallel Proc., 1986, pp. 216-223
[14] Tchuente, M., Generation of permutations by graphical exchanges, Ars Combin., 14, 115-122 (1982) · Zbl 0508.05041
[15] Araki, T., Hyper hamiltonian laceability of Cayley graphs generated by transpositions, Networks, 48, 121-124 (2006) · Zbl 1117.05068
[16] West, D. B., Introduction to Graph Theory (1996), Prentice Hall · Zbl 0845.05001
[17] Lovász, L., Combinatorial Problems and Exercises (1993), Akadémiai Kiadó: Akadémiai Kiadó Budapest · Zbl 0785.05001
[18] Godsil, C. D., GRR’s for non-solvable groups, Coll. Math. Soc. János Bolyai, 25, 221-239 (1981) · Zbl 0476.05041
[19] Cheng, E.; Lipták, L., Structural properties of Cayley graphs generated by transposition trees, Congr. Numer., 180, 81-96 (2006) · Zbl 1117.05050
[20] E. Cheng, L. Lipták, A supplement to the paper “Structural properties of Cayley graphs generated a by transposition trees”, Technical Report 2007-6, Oakland University, 2007; E. Cheng, L. Lipták, A supplement to the paper “Structural properties of Cayley graphs generated a by transposition trees”, Technical Report 2007-6, Oakland University, 2007
[21] Cheng, E.; Lipták, L., Fault resiliency of Cayley graphs generated by transpositions, Internat. J. Found. Comput. Sci., 18, 1005-1022 (2007) · Zbl 1202.68275
[22] Cheng, E.; Lipták, L., Linearly many faults in Cayley graphs generated by transposition trees, Inform. Sci., 177, 4877-4882 (2007) · Zbl 1129.68050
[23] Bauer, D.; Boesch, F.; Suffel, C.; Tindell, R., Connectivity extremal problems and the design of reliable probabilistic networks, (The Theory and Application of Graphs (1981), Wiley: Wiley New York), 89-98 · Zbl 0469.05044
[24] Nash-Williams, C. St. J.A., On orientations, connectivity and odd-vertex pairings in finite graph, Canad. J. Math., 12, 555-567 (1960) · Zbl 0096.38002
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.