Resistance distances and the Kirchhoff index in Cayley graphs. (English) Zbl 1237.05096
Summary: Closed-form formulae for the Kirchhoff index and resistance distances of the Cayley graphs over finite abelian groups are derived in terms of Laplacian eigenvalues and eigenvectors, respectively. In particular, formulae for the Kirchhoff index of the hexagonal torus network, the multidimensional torus and the t-dimensional cube are given, respectively. Formulae for the Kirchhoff index and resistance distances of the complete multipartite graph are obtained.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
References:
| [1] | Akers, S. B.; Krishnamurthy, B., A group theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Barth, D.; Fragopoulou, P.; Heydemann, M.-C., Uniform emulations of Cartesian-product and Cayley graphs, Discrete Appl. Math., 116, 37-54 (2002) · Zbl 0991.05053 |
| [3] | Biggs, N. L., Algebraic Graph Theorey (1993), Cambridge University Press: Cambridge University Press Cambridge |
| [4] | Désérable, D., A family of Cayley graphs on the hexavalent grid, Discrete Appl. Math., 93, 169-189 (1999) · Zbl 0931.68075 |
| [5] | Gao, S. H.; Hsub, D. F., Short containers in Cayley graphs, Discrete Appl. Math., 157, 1354-1363 (2009) · Zbl 1204.05052 |
| [6] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer: Springer Berlin · Zbl 0968.05002 |
| [7] | Gutman, I.; Mohar, B., The quasi-Wiener and the Kirchhoff indices coincide, J. Chem. Inf. Comput. Sci., 36, 982-985 (1996) |
| [8] | Heydemann, M., Cayley graphs and interconnection networks, (Hahn, G.; Sabidussi, G., Graph Symmetry: Algebraic Methods and Applications. Graph Symmetry: Algebraic Methods and Applications, NATO ASI Series C, vol. 497 (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 167-226 |
| [9] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0576.15001 |
| [10] | Klein, D. J.; Randić, M., Resistance distance, J. Math. Chem., 12, 81-95 (1993) |
| [11] | Lukovits, I.; Nikolić, S.; Trinajstić, N., Risistance distance in regular graphs, Int. J. Quantum Chem., 71, 217-225 (1999) |
| [12] | Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197-198, 143-176 (1994) · Zbl 0802.05053 |
| [13] | Nocetti, F. G.; Stojmenovic, I.; Zhang, J. Y., Addressing and routing in hexagonal networks with applications for tracking mobile users and connection rerouting in cellular networks, IEEE Trans. Parallel Distrib. Syst., 13, 963-971 (2002) |
| [14] | Stojmenovic, I., Honeycomb networks: topological properties and communication algorithms, IEEE Trans. Parallel Distrib. Syst., 8, 1036-1042 (1997) |
| [15] | Xiao, W. J.; Gutman, I., On resistance matrices, MATCH Commun. Math. Comput. Chem., 49, 67-81 (2003) · Zbl 1049.05053 |
| [16] | Xiao, W. J.; Parhami, B., Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes, Discrete Appl. Math., 155, 1752-1760 (2007) · Zbl 1127.68072 |
| [17] | Y. Xu, The spectra of Cayley graphs on Abel groups, The Master Thesis, Xinjiang University, 2007.; Y. Xu, The spectra of Cayley graphs on Abel groups, The Master Thesis, Xinjiang University, 2007. |
| [18] | Zhang, H. P.; Yang, Y. J., Resistance Distance and Kirchhoff Index in Circulant Graphs, Int. J. Quantum Chem., 107, 330-339 (2007) |
| [19] | Zhu, H. Y.; Klein, D. J.; Lukovits, I., Extensions of the Wiener number, J. Chem. Inf. Comput. Sci., 36, 420-428 (1996) |
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.
