NDLI: Geometry and Diameter Bounds of Directed Cayley Graphs of Abelian Groups

Please wait, while we are loading the content...

Geometry and Diameter Bounds of Directed Cayley Graphs of Abelian Groups

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Fiduccia, Charles M. epsf, Jennifer S. Zito input Forcade, Rodney W.
Copyright Year	1998
Abstract	Many popular interconnection network topologies, such as hypercubes and toroidal meshes, are based on Cayley graphs of Abelian groups. The symmetry and algebraic structure of these graphs result in many nice physical properties of the network concerning layout, routing algorithms, and load balancing. There has been interest in low-diameter Abelian--Cayley graphs because of their smaller communication delay and reduced congestion. For any fixed number of nodes n, and any fixed out-degree k, we are interested in how small the diameter of directed Cayley graphs of Abelian groups can be and what these low-diameter graphs look like. We give an upper bound of $n \leq \frac{3(d + 3)^3}{25}$ for the size of directed Abelian--Cayley graphs with k = 3 and diameter d, correcting a previously published result by Hsu and Jia [SIAM J. Discrete Math., 7 (1994), pp. 57--71].Our method is based on translational tiling techniques and is a generalization of Wong and Coppersmith's method for k = 2 [J. Assoc. Comput. Mach., 21 (1974), pp. 392--402]. Moreover, our method works for all Abelian groups, not just the cyclic case. For k = 3 we give computational results for the largest Abelian--Cayley graph as a function of diameter. When n = 84 m3 , for integer m, there is a network with $n = \frac{(d + 3)^3}{11.95}$ whose diameter is approximately three-fourths of that of a three-dimensional toroidal cube.
Starting Page	157
Ending Page	167
Page Count	11
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480195286456
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	11
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	Graphs and abstract algebra Generators, relations, and presentations diameter Distance in graphs Abelian groups network topologies translational tilings Graph theory Cayley graphs degree-diameter problems
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case

On the vertex-to-edge duality between the Cayley graph and the coset geometry of von Dyck groups

Integral pentavalent Cayley graphs on abelian or dihedral groups

The planar Cayley graphs are effectively enumerable II

Which finitely generated Abelian groups admit isomorphic Cayley graphs?

The planar Cayley graphs are effectively enumerable I: consistently planar graphs

Multidimensional Manhattan Street Networks

Large vertex-transitive and cayley graphs with given degree and diameter abstract.

Integral Cayley Graphs and Groups

Geometry and Diameter Bounds of Directed Cayley Graphs of Abelian Groups

Similar Documents

The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case

On the vertex-to-edge duality between the Cayley graph and the coset geometry of von Dyck groups

Integral pentavalent Cayley graphs on abelian or dihedral groups

The planar Cayley graphs are effectively enumerable II

Which finitely generated Abelian groups admit isomorphic Cayley graphs?

The planar Cayley graphs are effectively enumerable I: consistently planar graphs

Multidimensional Manhattan Street Networks

Large vertex-transitive and cayley graphs with given degree and diameter abstract.

Integral Cayley Graphs and Groups

Geometry and Diameter Bounds of Directed Cayley Graphs of Abelian Groups