Search

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]

The resistance distance R [ u , v ] between two vertices u and v of a graph G is defined as the net effective resistance between them in the electric network constructed from G by replacing each edge with a unit resistor. The resistance diameter D r (G) of G is the maximum resistance distance among all pairs of vertices of G. Given two path graphs P n = a 1 a 2 ... a n and P m = b 1 b 2 ... b m , let P n [ P m ] be the lexicographic product of P n and P m with vertex set { (a i , b j) | i = 1 , ... , n ; j = 1 , ... , m }. In [J. Appl. Math. Comput. 68 (2022) 1743–1755], Li et al. proved that for n > 10 , D r (P n [ P m ]) = R [ (a 1 , b 1) , (a n , b m) ] = R [ (a 1 , b 1) , (a n , b 1) ] = R [ (a 1 , b m) , (a n , b 1) ] = R [ (a 1 , b m) , (a n , b m) ]. In addition, they found that the result is not true for n = 2. For 3 ≤ n ≤ 10 and enough small m , they checked by computer that the result is still true. Based on their observation, they conjectured that the result is true for 3 ≤ n ≤ 10. In this paper, by combinatorial and electrical network approaches, we confirm the conjecture. [ABSTRACT FROM AUTHOR]

Two decades ago, resistance distance was introduced to characterize “chemical distance” in (molecular) graphs. In this paper, we consider three resistance distance-based graph invariants, namely, the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index. Some Nordhaus-Gaddum-type results for these three molecular structure descriptors are obtained. In addition, a relation between these Kirchhoffian indices is established.

A balanced blowup graph G H of G with respect to a fixed graph H is the graph obtained from G by replacing each vertex v i ∈ V (G) with a disjoint copy H v i of H , and connecting each vertex of V (H v i ) to each vertex of V (H v j ) if there is an edge between v i and v j in G. In particular, if H is a complete graph (resp. an empty graph), then G H is called the clique-blowup (resp. independent-blowup) of G. In (Azimi et al. (2021) [1]), A. Azimi et al. presented combinatorial interpretations of Moore-Penrose inverses of incidence matrices of independent-blowups and clique-blowups of trees, and applied these results to obtain formulas for resistance distances between vertices of the corresponding blowup graphs as well as their Kirchhoff index. In this paper, we extend their results to unbalanced blowup graphs of G via combinatorial and electrical network approaches. In addition, our results contain the main results of (Pan et al. (2021) [17]), (Li et al. (2020) [14]) and (Yan et al. (2023) [26]) as special cases. [ABSTRACT FROM AUTHOR]

Given two graphs, G 1 with vertices { v 1 , v 2 , … , v n } and G 2 , the neighborhood corona , G 1 ⋆ G 2 , is the graph obtained by taking n copies of G 2 and joining by an edge each neighbor of v i , in G 1 , to every vertex of the i th copy of G 2 . A special instance G 1 ⋆ K 1 of the neighborhood corona is called the splitting graph of G 1 and has a property that its spectrum consists of all eigenvalues ϕ λ and − ϕ − 1 λ , where ϕ = ( 1 + 5 ) ∕ 2 is the golden ratio and λ is an arbitrary eigenvalue of G 1 . In this paper, various spectra invariants of the neighborhood corona of graphs are studied. First, the condition number, the inertia, and the HOMO–LUMO gap of the s -fold splitting graphs are investigated, some of which turn out to have the golden-ratio scaling with the corresponding invariants of the original graph. Then, resistance distances and the Kirchhoff index of the neighborhood corona graph G 1 ⋆ G 2 are computed, with explicit expressions being obtained, which extends the previously known result. [ABSTRACT FROM AUTHOR]

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 ¯ , K f ( G ) + K f ( G ¯ ) ≤ n 3 − n 6 + n ∑ k = 1 n − 1 1 n − 4 sin 2 k π 2 n , with equality if and only if G or G ¯ is the path graph P n . 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. [ABSTRACT FROM AUTHOR]

• Properties on resistance distances in pentagonal chains are established. • Comparison results on Kirchhoff indices of pentagonal chain S,T-isomers are obtained. • Pentagonal chains with minimal and maximal Kirchhoff indices are characterized. The resistance distance between any two vertices of a connected graph G is defined as the effective resistance between them in the electrical network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index is a resistance distance-based topological index which plays an essential role in the study of quantitative structure-activity relationship (QSAR) and quantitative structure-property relationship (QSPR). In this paper, using techniques from electric network theory and graph theory, we characterize pentagonal chains with extermal Kirchhoff indices. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. The resistance distance between any two vertices of G is equal to the effective resistance between them in the corresponding electrical network constructed from G by replacing each edge with a unit resistor. The Kirchhoff index of G is defined as the sum of resistance distances between all pairs of vertices. Hexagonal chains are graph representations of unbranched catacondensed benzenoid hydrocarbons. It was shown in Yang and Klein (2014) [30] that among all hexagonal chains with n hexagons, the linear chain L n is the unique chain with maximum Kirchhoff index. However, for hexagonal chains with minimum Kirchhoff index, it was only claimed that the minimum Kirchhoff index is attained only when the hexagonal chain is an "all–kink" chain. In this paper, by standard techniques of electrical networks and comparison results on Kirchhoff indices of S , T -isomers, "all-kink" chains with maximum and minimum Kirchhoff indices are characterized. As a consequence, hexagonal chains with minimum Kirchhoff indices are singled out. [ABSTRACT FROM AUTHOR]

Two resistance-distance-based graph invariants, namely, the Kirchhoff index and the additive degree-Kirchhoff index, are studied. A relation between them is established, with inequalities for the additive degree-Kirchhoff index arising via the Kirchhoff index along with minimum, maximum, and average degrees. Bounds for the Kirchhoff and additive degree-Kirchhoff indices are also determined, and extremal graphs are characterised. In addition, an upper bound for the additive degree-Kirchhoff index is established to improve a previously known result. [ABSTRACT FROM AUTHOR]

Abstract: Comparison theorems on resistance distances and Kirchhoff indices of the so-called - & -isomer graphs are established. Then these results are applied to compare Kirchhoff indices of hexagonal chains, showing that the straight chain is the unique chain with maximum Kirchhoff index, whereas the minimum Kirchhoff index is achieved only when the hexagonal chain is an “all-kink” chain. [Copyright &y& Elsevier]

Abstract: Being motivated in terms of mathematical concepts from the theory of electrical networks, Klein and Ivanciuc introduced and studied a new graph-theoretic cyclicity index—the global cyclicity index (Klein, Ivanciuc, 2001). In this paper, by utilizing techniques from graph theory, electrical network theory and real analysis, we obtain some further results on this new cyclicity measure, including the strictly monotone increasing property, some lower and upper bounds, and some Nordhaus–Gaddum-type results. In particular, we establish a relationship between the global cyclicity index and the cyclomatic number of a connected graph with vertices and edges: [Copyright &y& Elsevier]

Abstract: Let be a connected graph. The Kirchhoff index (or total effective resistance, effective graph resistance) of is defined as the sum of resistance distances between all pairs of vertices. Let be the subdivision graph of . In this note, a formula and bounds for the Kirchhoff index of are obtained. It turns out that the Kirchhoff index of could be expressed in terms of the Kirchhoff index, the multiplicative degree-Kirchhoff index, the additive degree-Kirchhoff index, the number of vertices, and the number of edges of . Our result generalizes the previous result on the Kirchhoff index of subdivisions of regular graphs obtained by Gao et al. (2012). [Copyright &y& Elsevier]

Abstract: A recursion formula for resistance distances is obtained, and some of its applications are illustrated. [Copyright &y& Elsevier]

Abstract: Let , and be the join, corona and cluster of graphs and , respectively. In this paper, Kirchhoff index formulae of these composite graphs are given. [Copyright &y& Elsevier]

The resistance distance rij between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices. In this work, according to the decomposition theorem of Laplacian polynomial, we obtain that the Laplacian spectrum of linear hexagonal chain Ln consists of the Laplacian spectrum of path P2n+1 and eigenvalues of a symmetric tridiagonal matrix of order 2n + 1. By applying the relationship between roots and coefficients of the characteristic polynomial of the above matrix, explicit closed-form formula for Kirchhoff index of Ln is derived in terms of Laplacian spectrum. To our surprise, the Krichhoff index of Ln is approximately to one half of its Wiener index. Finally, we show that ${Kf(G)\over W(G)}>{1\over 5}$ holds for all graphs G in a class of graphs including Ln. © 2007 Wiley Periodicals, Inc. Int J Quantum Chem, 2008 [ABSTRACT FROM AUTHOR]

The resistance distance rij between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices. In this work, closed-form formulae for Kirchhoff index and resistance distances of circulant graphs are derived in terms of Laplacian spectrum and eigenvectors. Special formulae are also given for four classes of circulant graphs (complete graphs, complete graphs minus a perfect matching, cycles, Möbius ladders Mp). In particular, the asymptotic behavior of Kf(Mp) as p → ∞ is obtained, that is, Kf(Mp) grows as 1/6p3 as p → ∞. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2007 [ABSTRACT FROM AUTHOR]