Solution to a conjecture on a Nordhaus–Gaddum type result for the Kirchhoff index

Yujun Yang, Yuliang Cao, Haiyuan Yao and Jing Li

Applied Mathematics and Computation, 2018, vol. 332, issue C, 241-249

Abstract: Let G be a connected graph. The resistance distance between any two vertices of G is defined as the net effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index of G, denoted by Kf(G), is the sum of resistance distances between all pairs of vertices in G. In [28], it was conjectured that for a connected n-vertex graph G with a connected complement G¯,Kf(G)+Kf(G¯)≤n3−n6+n∑k=1n−11n−4sin2kπ2n,with equality if and only if G or G¯ is the path graph Pn. In this paper, by employing combinatorial and electrical techniques, we show that the conjecture is true except for a complementary pair of small graphs on five vertices.

Keywords: Resistance distance; Kirchhoff index; Nordhaus–Gaddum type result (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318302431
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:332:y:2018:i:c:p:241-249

DOI: 10.1016/j.amc.2018.03.070

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().