On the ordering of the Kirchhoff indices of the complements of trees and unicyclic graphs
- PDF / 330,767 Bytes
- 13 Pages / 595.28 x 841.89 pts (A4) Page_size
- 59 Downloads / 168 Views
On the ordering of the Kirchhoff indices of the complements of trees and unicyclic graphs CHEN Xiao-dan∗
HAO Guo-liang
JIN De-quan
Abstract. The Kirchhoff index Kf (G) of a graph G is defined to be the sum of the resistance distances between all pairs of vertices of G. In this paper, we develop a novel method for ordering the Kirchhoff indices of the complements of trees and unicyclic graphs. With this method, we determine the first five maximum values of Kf (T ) and the first four maximum values of Kf (U ), where T and U are the complements of a tree T and unicyclic graph U , respectively.
§1
Introduction
The concept of the resistance distance of a graph was conceived by Klein and Randi´c [17] in 1993 based on the electrical network theory and graph theory. A (connected) graph G is regarded as an electrical network N by replacing each edge of G with a unit resistor and then, the resistance distance between a pair of vertices in G is defined to be the effective resistance between them in N , which is computed by the Ohm’s and Kirchhoff’s laws. As the common shortest-path distance, the resistance distance is a distance function on graphs, which not only has some nice purely mathematical and physical interpretations, but also has a substantial potential for chemical applications [17, 18]. All graphs considered throughout this paper are finite, undirected, and simple graphs. Let G be a graph with vertex set V (G) = {v1 , v2 , . . . , vn }. Denote by rG (vi , vj ) the resistance distance between the vertices vi and vj in G. The Kirchhoff index of G [3, 17] is defined as n n 1 ∑∑ Kf (G) = rG (vi , vj ). 2 i=1 j=1 Here G is allowed to be disconnected; in this case, we have rG (vi , vj ) = +∞ for the vertices vi and vj in different components of G and Kf (G) = +∞. Up to now, this resistancedistance-based graph invariant, as a molecular structure descriptor, has been found noteworthy Received: 2018-03-15. Revised: 2019-09-11 MR Subject Classification: 05C35, 05C50, 05C12. Keywords: Kirchhoff index, tree, unicyclic graph, complement, ordering. Digital Object Identifier(DOI): https://doi.org/10.1007/s11766-020-3605-5. Supported by the National Natural Science Foundation of China (11861011, 11501133, 11661010). ∗ Corresponding author.
CHEN Xiao-dan, et al.
On the ordering of the Kirchhoff indices of the complements...
309
applications in chemistry [2, 3, 9], and many of its mathematical properties have also been established [5–8, 10–12, 16, 19, 20, 24–32, 35, 36, 38, 39]. Recall that the Laplacian matrix of a graph G is defined to be L(G) = D(G) − A(G), where A(G) is the adjacency matrix of G and D(G) is the diagonal matrix of vertex degrees of G. The eigenvalues of L(G), usually known as the Laplacian eigenvalues of the graph G, are arranged (in non-increasing order) as µ1 (G) ≥ µ2 (G) ≥ · · · ≥ µn (G). It is well known that µn (G) = 0 and, µn−1 (G) > 0 if and only if G is connected. For more details concerning the Laplacian eigenvalues of a graph one may refer to [23]. One of the most beautiful and important mathematical properties
Data Loading...
