Search

The construction of vertex-decorated graphs can be used to produce derived graphs with specific eigenvalues from undecorated graphs, which themselves do not have such eigenvalues. An instance of a decorated graph is the rooted product G(H) of graphs G and H. Let $$F = (V, E)$$ be a molecular graph with the vertex set V and the edge set E $$(|V|=n; |E|=m)$$ , and let $$n_{+}=n_{-}$$ $$(n_{+}+n_{-}=n)$$ , where $$n_{+}$$ and $$n_{-}$$ are the numbers of positive and negative eigenvalues, respectively. Then, in the spectrum of the eigenvalues of F, two minimum-modulus eigenvalues, positive $$\lambda _{+}$$ and negative $$\lambda _{-}$$ , are of special interest because the value $$\delta =\lambda _{+}-\lambda _{-}$$ determines the energy gap. In quantum chemistry, the energy gap $$\delta $$ is associated with the energy of an electron transfer from the highest occupied molecular orbital to the lowest unoccupied molecular orbital of a molecule. As an example, we consider obtaining a (molecular) graph $$F=G(H)$$ whose median eigenvalues $$\lambda _{+}$$ and $$\lambda _{-}$$ are predictably close to 0.

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.

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 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.

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$G=(V, E)$\end{document}G=(V,E) be a simple graph. The resistance distance between \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$i,j\in V$\end{document}i,j∈V, denoted by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$r_{ij}$\end{document}rij, is defined as the net effective resistance between nodes i and j in the corresponding electrical network constructed from G by replacing each edge of G with a resistor of 1 Ohm. The resistance-distance matrix of G, denoted by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$R(G)$\end{document}R(G), is a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\vert V \vert \times \vert V \vert $\end{document}|V|×|V| matrix whose diagonal entries are 0 and for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$i\neq j$\end{document}i≠j, whose ij-entry is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$r_{ij}$\end{document}rij. In this paper, we determine the eigenvalues of the resistance-distance matrix of complete multipartite graphs. Also, we give some lower and upper bounds on the largest eigenvalue of the resistance-distance matrix of complete multipartite graphs. Moreover, we obtain a lower bound on the second largest eigenvalue of the resistance-distance matrix of complete multipartite graphs.

We study three resistance distance-based graph invariants: the Kirchhoff index, and two modifications, namely, the multiplicative degree-Kirchhoff index and the additive degree-Kirchhoff index. In work in press, one of the present authors (2014) and Sun et al. (2014) independently obtained (different) formulas for the Kirchhoff index of subdivisions of graphs. Huang et al. (2014) obtained a formula for the Kirchhoff index of triangulations of graphs. In our paper, first we derive formulae for the additive degree-Kirchhoff index and the multiplicative degree-Kirchhoff index of subdivisions and triangulations, as well as a new formula for the Kirchhoff index of triangulations, in terms of invariants of $G$. Then comparisons are made between each of our Kirchhoffian graph invariants for subdivision and triangulation. Finally, formulae for these graph invariants of iterated subdivisions and triangulations of graphs are obtained., Comment: 22 pages, 1 figure

Comparison theorems on resistance distances and Kirchhoff indices of the so-calledS- &T-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.

Let G be a connected graph. The Kirchhoff index (or total effective resistance, effective graph resistance) of G is defined as the sum of resistance distances between all pairs of vertices. Let S ( G ) be the subdivision graph of G . In this note, a formula and bounds for the Kirchhoff index of S ( G ) are obtained. It turns out that the Kirchhoff index of S ( G ) 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 G . Our result generalizes the previous result on the Kirchhoff index of subdivisions of regular graphs obtained by Gao et al. (2012).

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 C ( G ) and the cyclomatic number μ ( G ) of a connected graph G with n vertices and m edges: m n − 1 μ ( G ) ≤ C ( G ) ≤ n 2 μ ( G ) .

A recursion formula for resistance distances is obtained, and some of its applications are illustrated.

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 is the sum of resistance distances between all pairs of vertices in G. Zhou and Trinajstic (Chem Phys Lett 455(1–3):120–123, 2008) obtained a Nordhaus-Gaddum-type result for the Kirchhoff index by obtaining lower and upper bounds for the sum of the Kirchhoff index of a graph and its complement. In this paper, by making use of the Cauchy-Schwarz inequality, spectral graph theory and Foster’s formula, we give better lower and upper bounds. In particular, the lower bound turns out to be tight. Furthermore, we establish lower and upper bounds on the product of the Kirchhoff index of a graph and its complement.

Let G"1+G"2, G"1@?G"2 and G"1{G"2} be the join, corona and cluster of graphs G"1 and G"2, respectively. In this paper, Kirchhoff index formulae of these composite graphs are given.

The resistance distance between two vertices of a connected graphGis defined as the effective resistance between them in the corresponding electrical network constructed fromGby replacing each edge ofGwith a unit resistor. The Kirchhoff index ofGis the sum of resistance distances between all pairs of vertices. In this paper, general bounds for the Kirchhoff index are given via the independence number and the clique number, respectively. Moreover, lower and upper bounds for the Kirchhoff index of planar graphs and fullerene graphs are investigated.

Combining a bifurcation theorem with a local Leray–Schauder degree theorem of Krasnoselskii and Zabreiko in the case of a simple singular point, we obtain an existence result on the number of small solutions for a class of functional bifurcation equations. Since this result contains the information of local Leray–Schauder degree, we obtain new multiplicity results for the perturbations of second-order linear elliptic problems by unbounded nonlinearities as applications here, by a priori bounds essentially due to Gupta and by a Leray–Schauder degree computation.

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 $(m,n)$ -bipartite graph is a bipartite graph such that one bipartition has m vertices and the other bipartition has n vertices. The tree dumbbell $D(n,a,b)$ consists of the path ${P}_{n-a-b}$ together with a independent vertices adjacent to one pendent vertex of ${P}_{n-a-b}$ and b independent vertices adjacent to the other pendent vertex of ${P}_{n-a-b}$ . In this paper, firstly, we show that, among $(m,n)$ -bipartite graphs $(m\le n)$ , the complete bipartite graph ${K}_{m,n}$ has minimal Kirchhoff index and the tree dumbbell $D(m+n,{\lfloor}n-\mathrm{(m}+1)/2{\rfloor},{\lceil}n-\mathrm{(m}+1)/2{\rceil})$ has maximal Kirchhoff index. Then, we show that, among all bipartite graphs of order $l$ , the complete bipartite graph ${K}_{{\lfloor}l/2{\rfloor},l-{\lfloor}l/2{\rfloor}}$ has minimal Kirchhoff index and the path ${P}_{l}$ has maximal Kirchhoff index, respectively. Finally, bonds for the Kirchhoff index of $(m,n)$ -bipartite graphs and bipartite graphs of order $l$ are obtained by computing the Kirchhoff index of these extremal graphs.