Complete characterization of bicyclic graphs with minimal Kirchhoff index

被引：82

作者：

Liu, Jia-Bao ^{[1
,2
]}

Pan, Xiang-Feng ^{[1
]}

Yu, Lei ^{[1
,3
]}

Li, Dong ^{[1
]}

机构：

[1] Anhui Univ, Sch Math Sci, Hefei 230601, Peoples R China

[2] Anhui Xinhua Univ, Dept Publ Courses, Hefei 230088, Peoples R China

[3] Univ Sci & Technol China, Sch Math Sci, 96 Jinzhai Rd, Hefei 230026, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 200卷

基金：

中国国家自然科学基金;

关键词：

Resistance distance; Kirchhoff index; Bicyclic graphs; Extremal graphs; Theta-type graphs; Wiener index; RESISTANCE-DISTANCE; FORMULA; BOUNDS; ENERGY;

D O I：

10.1016/j.dam.2015.07.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The resistance distance between any two vertices of a graph G is defined as the network effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index K (G) is the sum of the resistance distances between all the pairs of vertices in G. A bicyclic graph is a connected graph whose number of edges is exactly one more than its number of vertices. In this paper, we completely characterize the bicyclic graphs of order n >= 4 with minimal Kirchhoff index and determine bounds on the Kirchhoff index of bicyclic graphs. This improves and extends some earlier results. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：95 / 107

页数：13

共 41 条

[1] Resistance-distance matrix: A computational algorithm and its application [J].

Babic, D ;

Klein, DJ ;

Lukovits, I ;

Nikolic, S ;

Trinajstic, N .

INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2002, 90 (01) :166-176

[2]

Bapat RB, 2003, Z NATURFORSCH A, V58, P494

[3] A formula for the Kirchhoff index [J].

Bendito, Enrique ;

Carmona, Angeles ;

Encinas, Andres M. ;

Gesto, Jose M. .

INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, 2008, 108 (06) :1200-1206

[4] Bounds for the Kirchhoff index via majorization techniques [J].

Bianchi, Monica ;

Cornaro, Alessandra ;

Luis Palacios, Jose ;

Torriero, Anna .

JOURNAL OF MATHEMATICAL CHEMISTRY, 2013, 51 (02) :569-587

[5]

Bondy J., 2008, GRADUATE TEXTS MATH

[6] Resistance distance in subdivision-vertex join and subdivision-edge join of graphs [J].

Bu, Changjiang ;

Yan, Bo ;

Zhou, Xiuqing ;

Zhou, Jiang .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 458 :454-462

[7]

Deng HY, 2010, MATCH-COMMUN MATH CO, V63, P171

[8] On extremal bipartite unicyclic graphs [J].

Deng, Qingying ;

Chen, Haiyan .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 444 :89-99

[9] On the Kirchhoff index of the complement of a bipartite graph [J].

Deng, Qingying ;

Chen, Haiyan .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 439 (01) :167-173

[10]

Feng LH, 2014, ARS COMBINATORIA, V114, P33

← 1 2 3 4 5 →