Circulant Graphs And Tessellations On Flat Tori

Circulant graphs are characterized here as quotient lattices, which are realized as vertices connected by a knot on a k-dimensional flat torus tessellated by hypercubes or hyperparallelotopes. Via this approach we present geometric interpretations for a bound on the diameter of a circulant graph, derive new bounds for the genus of a class of circulant graphs and establish connections with spherical codes and perfect codes in Lee spaces. © 2010 Elsevier Inc. All rights reserved.434818111823Heuberger, C., On planarity and colorability of circulant graphs (2003) Discrete Math., 268, pp. 153-169Muga II, F.P., Undirected circulant graphs (1994) International Symposium on Parallel Architectures, Algorithms and Networks, pp. 113-118Dougherty, R., Faber, V., The degree-diameter problem for several varieties of Cayley graphs. I: The Abelian Case (2004) SIAM J. Discrete Math., 17 (3), pp. 478-519C. Martínez, On the perfect t-dominating set problem in circulant graphs and codes over Gaussian integers (2005) Proceedings ISIT - IEEE International Symposium on Information Theory, pp. 1-5Parkson, T.D., Circulant graph imbeddings (1980) J. Combin. Theory (B), 29, pp. 310-320Golomb, S.W., Welch, L.R., Algebraic coding and the Lee metric (1968) Proc. Sympos. Math. Res. Center, pp. 175-194. , Madison, Wis., John Wiley, New YorkHorak, P., On perfect Lee codes (2008) Discrete Mathematics, , doi:10.1016/j.disc.2008.03.019Ádám, A., Research problem 2-10 (1967) J. Combin. Theory, 2, p. 393Elspas, B., Turner, J., Graphs with circulant adjacency matrices (1970) J. Combin. Theory, 9, pp. 229-240Liskovets, V., Pöschel, R., Counting circulant graphs of prime-power order by decomposing into orbit enumeration problems (2000) Discrete Math., 214, pp. 173-191Muzychuk, M., Ádám's conjecture is true in the square-free case (1995) J. Combin. Theory A, 72 (1), pp. 118-134Boesch, F., Tindell, R., Circulants and their connectivities (1984) J. Graph Theory, 8, pp. 487-499Stillwell, J., (1992) Geometry of Surfaces, , Springer-Verlag New YorkCosta, S.I.R., Muniz, M., Agustini, E., Palazzo, R., Graphs, tessellations, and perfect codes on flat tori (2004) IEEE Trans. Inform. Theory, 50 (10), pp. 2363-2378Conway, J.H., Sloane, N.J.A., (1999) Sphere Packings, Lattices and Groups, , Springer-Verlag New YorkCosta, S.I.R., Strapasson, J.E., Muniz, M., Siqueira, R.M., Circulant graphs, lattices and spherical codes (2007) Internat. J. Appl. Math., 20 (5), pp. 581-594Kirschenhofer, P., Pethõ, A., Tichy, R., On analytical and Diophantine properties of a family of counting functions (1999) Acta Sci. Math. (Szeged), 65 (12), pp. 47-59Albdaiwi, B.F., Bose, B., Quasi-perfect Lee distance codes (2003) IEEE Trans. Inform. Theory, 49, pp. 1535-1539Gross, J.L., Tucker, T.W., (2001) Topological Graph Theory, , Dover NYTrudeau, R.J., (1976) Introduction to Graph Theory, , Dover New YorkMolitierno, J.J., On the algebraic connectivity of graphs as a function of genus (2006) Linear Algebra and Its Applications, 419 (2-3), pp. 519-531. , DOI 10.1016/j.laa.2006.05.014, PII S002437950600266