New families of multiplicative circulant networks

E. A. Monakhova

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 76-84.

Résumé

For circulant networks, the problem of the maximal attainable number of nodes under given degree and diameter of their graphs is considered. A research of multiplicative circulant networks with generators in the form of $(1,t,t^2,\dots, t^{k-1})$ for odd $t\ge5$ is presented. On the base of this research, two new families of multiplicative circulant networks of orders $n=(t+1)(1+t+\ldots+t^{k-1})/2+t^{k-1}$ for odd dimensions $k\ge3$ and diameters $d\equiv0\bmod k$ and even dimensions $k\ge4$ and diameters $d\equiv0\bmod k$ and $d\equiv0\bmod k/2$ are constructed. The orders of these graphs are larger than orders of graphs of all known families of multiplicative circulant networks under the same dimensions and diameters.

Détail

Keywords: multiplicative circulant networks, diameter, maximum order of a graph.

Bibliographie

[1] Monakhova E. A., “Structural and communicative properties of circulant networks”, Prikladnaya Diskretnaya Matematika, 2011, no. 3, 92–115 (in Russian)

[2] Monakhova E. A., “A survey on undirected circulant graphs”, Discr. Math. Algorithms and Appl., 4:1 (2012), 17–47 | MR

[3] Perez-Roses H., “Algebraic and computer-based methods in the undirected degree/diameter problem – a bief survey”, Electronic J. Graph Theory and Appl., 2:2 (2014), 166–190 | MR | Zbl

[4] Erickson A., Stewart I. A., Navaridas J., Kiasari A. E., “The stellar transformation: From interconnection networks to datacenter networks”, Comput. Networks, 113 (2017), 29–45 | DOI

[5] Wong C. K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21 (1974), 392–402 | DOI | MR | Zbl

[6] Monakhova E., “Optimal triple loop networks with given transmission delay: Topological design and routing”, Intern. Network Optimization Conf. (INOC'2003), Evry–Paris, France, 2003, 410–415

[7] Dougherty R., Faber V., “The degree-diameter problem for several varieties of Cayley graphs, 1: The Abelian case”, SIAM J. Discrete Math., 17:3 (2004), 478–519 | DOI | MR | Zbl

[8] Lewis R., The degree-diameter problem for circulant graphs of degree 8 and 9, 2014, arXiv: 1404.3948v1 | MR

[9] Feria-Puron R., Ryan J., Perez-Roses H., “Searching for large multi-loop networks”, Elec. Notes Disc. Math., 46 (2014), 233–240 | DOI | MR | Zbl

[10] Feria-Puron R., Perez-Roses H., Ryan J., Searching for large circulant graphs, 25 Mar 2015, 31 pp., arXiv: 1503.07357v1[math.CO]

[11] The Degree/Diameter Problem For Circulant Graphs, http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs

[12] Chen S., Jia X.-D., “Undirected loop networks”, Networks, 23 (1993), 257–260 | DOI | MR | Zbl

[13] Parhami B., “Chordal rings based on symmetric odd-radix number systems”, Proc. Intern. Conf. on Communications in Computing (Las Vegas, NV, June 27–30, 2005), IEEE Press, Los Alamitos, 2005, 196–199

[14] Parhami B., “A class of odd-radix chordal ring networks”, The CS'J J. Comput. Sci. Eng., 4:2–4 (2006), 1–9

[15] Stojmenovic I., “Multiplicative circulant networks. Topological properties and communication algorithms”, Discr. Appl. Math., 77 (1997), 281–305 | DOI | MR | Zbl

[16] Monakhova E. A., “On an extremal family of circulant networks”, J. Appl. Industr. Math., 5:4 (2011), 1–7 | DOI | MR