×

Bounds for the Kirchhoff index of bipartite graphs. (English) Zbl 1245.05107

Summary: A \((m, n)\)-bipartite graph is a bipartite graph such that one bipartition has \(m\) vertices and the other bipartition has \(n\) vertices. The tree dumbbell \(D(n, a, b)\) consists of the path \(P_{n-a-b}\) together with \(a\) independent vertices adjacent to one independent vertex of \(P_{n-a-b}\) and \(b\) independent vertices adjacent to the other pendent vertex of \(P_{n-a-b}\).
In this paper, firstly, we show that, among \((m, n)\)-bipartite graphs \((m \leq n)\), the complete bipartite graph \(K_{m,n}\) has minimal Kirchhoff index and the tree dumbbell \(D(m + n, \lfloor n - (m + 1)/2\rfloor, \lceil n - (m + 1)/2 \rceil)\) has maximal Kirchhoff index.
Then, we show that, among all bipartite graphs of order \(l\), the complete bipartite graph \(K_{\lfloor l/2 \rfloor, l - \lfloor l/2 \rfloor}\) has minimal Kirchhoff index and the path \(P_l\) has maximal Kirchhoff index, respectively. Finally, bonds for the Kirchhoff index of \((m, n)\)-bipartite graphs and bipartite graphs of order \(l\) are obtained by computing the Kirchhoff index of these extremal graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
05C12 Distance in graphs

Keywords:

tree dumbbell
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Wiener, “Structural determination of paraffin boiling points,” Journal of the American Chemical Society, vol. 69, pp. 17-20, 1947.
[2] D. J. Klein and M. Randić, “Resistance distance,” Journal of Mathematical Chemistry, vol. 12, no. 1-4, pp. 81-95, 1993. · doi:10.1007/BF01164627
[3] D. Bonchev, A. T. Balaban, X. Liu, and D. J. Klein, “Molecular cyclicity and centricity of polycyclic graphs-I. Cyclicity based on resistance distances or reciprocal distances,” International Journal of Quantum Chemistry, vol. 50, pp. 1-20, 1994.
[4] W. Xiao and I. Gutman, “Resistance distance and Laplacian spectrum,” Theoretical Chemistry Accounts, vol. 110, no. 4, pp. 284-289, 2003. · doi:10.1007/s00214-003-0460-4
[5] W. Zhang and H. Deng, “The second maximal and minimal Kirchhoff indices of unicyclic graphs,” Communications in Mathematical and in Computer Chemistry, vol. 61, no. 3, pp. 683-695, 2009. · Zbl 1199.05253
[6] H. Zhang, Y. Yang, and C. Li, “Kirchhoff index of composite graphs,” Discrete Applied Mathematics, vol. 157, no. 13, pp. 2918-2927, 2009. · Zbl 1209.05149 · doi:10.1016/j.dam.2009.03.007
[7] E. Bendito, A. Carmona, A. M. Encinas, J. M. Gesto, and M. Mitjana, “Kirchoff indexes of a network,” Linear Algebra and its Applications, vol. 432, no. 9, pp. 2278-2292, 2010. · Zbl 1195.94100 · doi:10.1016/j.laa.2009.05.032
[8] Y. Wang and W. Zhang, “Kirchhoff index of linear pentagonal chains,” International Journal of Quantum Chemistry, vol. 110, no. 9, pp. 1594-1604, 2010. · doi:10.1002/qua.22318
[9] Y. Wang and W. Zhang, “Kirchhoff index of cyclopolyacenes,” Zeitschrift fur Naturforschung, vol. 65, no. 10, pp. 865-870, 2010.
[10] X. Gao, Y. Luo, and W. Liu, “Resistance distances and the Kirchhoff index in Cayley graphs,” Discrete Applied Mathematics, vol. 159, no. 17, pp. 2050-2057, 2011. · Zbl 1237.05096 · doi:10.1016/j.dam.2011.06.027
[11] X. Gao, Y. Luo, and W. Liu, “Kirchhoff index in line, subdivision and total graphs of a regular graph,” Discrete Applied Mathematics, vol. 160, no. 4-5, pp. 560-565, 2012. · Zbl 1239.05053 · doi:10.1016/j.dam.2011.11.011
[12] Y. Yang, H. Zhang, and D. J. Klein, “New Nordhaus-Gaddum-type results for the Kirchhoff index,” Journal of Mathematical Chemistry, vol. 49, no. 8, pp. 1587-1598, 2011. · Zbl 1227.92054 · doi:10.1007/s10910-011-9845-0
[13] L. Ye, “On the Kirchhoff index of some toroidal lattices,” Linear and Multilinear Algebra, vol. 59, no. 6, pp. 645-650, 2011. · Zbl 1223.05059 · doi:10.1080/03081081003794233
[14] B. Zhou and N. Trinajstić, “A note on Kirchhoff index,” Chemical Physics Letters, vol. 455, no. 1-3, pp. 120-123, 2008. · doi:10.1016/j.cplett.2008.02.060
[15] B. Zhou and N. Trinajstić, “On resistance-distance and Kirchhoff index,” Journal of Mathematical Chemistry, vol. 46, no. 1, pp. 283-289, 2009. · Zbl 1187.92092 · doi:10.1007/s10910-008-9459-3
[16] B. Zhou and N. Trinajstić, “The kirchhoff index and the matching number,” International Journal of Quantum Chemistry, vol. 109, no. 13, pp. 2978-2981, 2009. · doi:10.1002/qua.21915
[17] I. Lukovits, S. Nikolić, and N. Trinajstić, “Resistance distance in regular graphs,” International Journal of Quantum Chemistry, vol. 71, no. 3, pp. 217-225, 1999.
[18] J. L. Palacios, “Resistance distance in graphs and random walks,” International Journal of Quantum Chemistry, vol. 81, no. 1, pp. 29-33, 2001.
[19] H. Zhang and Y. Yang, “Resistance distance and kirchhoff index in circulant graphs,” International Journal of Quantum Chemistry, vol. 107, no. 2, pp. 330-339, 2007. · doi:10.1002/qua.21068
[20] Q. Guo, H. Deng, and D. Chen, “The extremal Kirchhoff index of a class of unicyclic graphs,” Communications in Mathematical and in Computer Chemistry, vol. 61, no. 3, pp. 713-722, 2009. · Zbl 1224.05142
[21] H. Zhang, X. Jiang, and Y. Yang, “Bicyclic graphs with extremal Kirchhoff index,” Communications in Mathematical and in Computer Chemistry, vol. 61, no. 3, pp. 697-712, 2009. · Zbl 1199.05251
[22] L. Feng, G. Yu, K. Xu, and Z. Jiang, “A note on the Kirchhoff index of bicyclic graphs,” Ars Combinatoria. In press. · Zbl 1340.05058
[23] H. Wang, H. Hua, and D. Wang, “Cacti with minimum, second-minimum, and third-minimum Kirchhoff indices,” Mathematical Communications, vol. 15, no. 2, pp. 347-358, 2010. · Zbl 1206.05038
[24] D. J. Klein, “Resistance-distance sum rules,” Croatica Chemica Acta, vol. 75, no. 2, pp. 633-649, 2002.
[25] R. C. Entringer, D. E. Jackson, and D. A. Snyder, “Distance in graphs,” Czechoslovak Mathematical Journal, vol. 26, no. 2, pp. 283-296, 1976. · Zbl 0329.05112
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.