Minimizing Kirchhoff index among graphs with a given vertex bipartiteness

详细信息    查看全文

• 作者：Jia-Bao Liu^a ; ^b ; ^{liujiabaoad@163.com" class="auth_mail" title="E-mail the corresponding author} ; Xiang-Feng Pan ; ^b ; ^{xfpan@ahu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; ^{xfpan@ustc.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Kirchhoff index ; Vertex bipartiteness ; Resistance distance ; Generalized join ; Laplacian eigenvalues
• 刊名：Applied Mathematics and Computation
• 出版年：2016
• 出版时间：1 December 2016
• 年：2016
• 卷：291
• 期：Complete
• 页码：84-88
• 全文大小：300 K

文摘

The resistance distance between any two vertices of a graph G is defined as the effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index Kf(G) is the sum of the resistance distances between all the pairs of vertices in G. The vertex bipartiteness v_b of a graph G is the minimum number of vertices whose deletion from G results in a bipartite graph. In this paper, we characterize the graph having the minimum Kf(G) values among graphs with a fixed number n   of vertices and fixed vertex bipartiteness, le="Click to view the MathML source">1&le;v_b&le;n−3.$1\&<font\; color="red">le</font>;v_b\&<font\; color="red">le</font>;n-3.$