×
Thomson, Alison; Zhou, Sanming

Frobenius circulant graphs of valency four. (English) Zbl 1167.05036

J. Aust. Math. Soc. 85, No. 2, 269-282 (2008).
Summary: A first kind Frobenius graph is a Cayley graph Cay\((K,S)\) on the Frobenius kernel of a Frobenius group \(K \rtimes H\) such that \(S=a^H\) for some \(a\in K\) with \(\langle a^H \rangle =K\), where \(H\) is of even order or \(a\) is an involution. It is known that such graphs admit ‘perfect’ routing and gossiping schemes. A circulant graph is a Cayley graph on a cyclic group of order at least three. Since circulant graphs are widely used as models for interconnection networks, it is thus highly desirable to characterize those which are Frobenius of the first kind. In this paper we first give such a characterization for connected 4-valent circulant graphs, and then describe optimal routing and gossiping schemes for those which are first kind Frobenius graphs. Examples of such graphs include the 4-valent circulant graph with a given diameter and maximum possible order.

Cited in 1 Review
Cited in 12 Documents

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
68M10 Network design and communication in computer systems
90B18 Communication networks in operations research

Keywords:

Cayley graph; circulant graph; multi-loop network; double-loop network; Frobenius group; Frobenius graph; complete rotation; gossiping; minimum gossip time; routing; edge-forwarding index; arc-forwarding index
Cite Review PDF
Full Text: DOI

References:

[1] DOI: 10.1016/0012-365X(92)00528-Y · Zbl 0807.05037 · doi:10.1016/0012-365X(92)00528-Y
[2] Wong, J. Assoc. Comp. Mach. 21 pp 392– (1974) · Zbl 0353.68039 · doi:10.1145/321832.321838
[3] Rose, A Course on Group Theory (1978)
[4] Niven, An Introduction to the Theory of Numbers (1980) · Zbl 0431.10001
[5] Narayanan, Algorithmica 31 pp 155– (2001) · Zbl 0980.68010 · doi:10.1007/s00453-001-0043-5
[6] Heydemann, European J. Combin. 22 pp 179– (2001)
[7] Lim, European J. Combin. 23 pp 1033– (2002)
[8] Heydemann, Graph Symmetry pp 167– (1997) · doi:10.1007/978-94-015-8937-6_5
[9] DOI: 10.1016/S0012-365X(01)00438-1 · Zbl 1018.05044 · doi:10.1016/S0012-365X(01)00438-1
[10] DOI: 10.1016/S0012-365X(97)00148-9 · Zbl 0904.05038 · doi:10.1016/S0012-365X(97)00148-9
[11] Ireland, A Classical Introduction to Modern Number Theory (1982) · Zbl 0482.10001 · doi:10.1007/978-1-4757-1779-2
[12] Dixon, Permutation Groups (1996) · doi:10.1007/978-1-4612-0731-3
[13] DOI: 10.1016/S0304-3975(01)00341-3 · Zbl 1038.68004 · doi:10.1016/S0304-3975(01)00341-3
[14] DOI: 10.1109/TCS.1985.1085667 · Zbl 0583.94018 · doi:10.1109/TCS.1985.1085667
[15] DOI: 10.1016/0166-218X(89)90022-X · Zbl 0681.90077 · doi:10.1016/0166-218X(89)90022-X
[16] Biggs, Algebraic Graph Theory (1993) · Zbl 0284.05101
[17] Bermond, Gossiping in Cayley Graphs by Packets pp 301– (1996)
[18] DOI: 10.1137/0219037 · Zbl 0698.68064 · doi:10.1137/0219037
[19] DOI: 10.1109/12.21148 · Zbl 0678.94026 · doi:10.1109/12.21148
[20] DOI: 10.1006/jagm.1993.1011 · Zbl 0764.68137 · doi:10.1006/jagm.1993.1011
[21] DOI: 10.1142/S0129054198000076 · Zbl 0967.68009 · doi:10.1142/S0129054198000076
[22] Yebra, Ars Combin. 20-B pp 159– (1985)
[23] Scott, Group Theory (1964)
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.