Search

We study the general Randic index R a ( G ) = ∑ u v ∈ E ( G ) [ d e g G ( u ) d e g G ( v ) ] a , where a ∈ R , E ( G ) is the edge set of a graph G , and d e g G ( u ) and d e g G ( v ) are the degrees of vertices u and v , respectively. For a set of unicyclic graphs of given order and diameter, we present the unique graph having the minimum general Randic index, where − 0 . 64 ≤ a 0 . Since R − 1 2 ( G ) is the Randic index of a graph G , our result holds also for the classical Randic index.

The n -vertex unicyclic graphs with extreme values of arithmetic–geometric index or AG index are determined for all values of n . The case regarding the extremal values of the AG index in the class of bicyclic graphs has been stated as open problem.

A k -cone c -cyclic graph is the join of the complete graph K k and a c -cyclic graph (if k = 0 , we get the usual connected graph). A k -apex tree (resp., k -apex unicyclic graph) is defined as a connected graph G with a k -subset V k ⊆ V ( G ) such that G − V k is a tree (resp., unicylic graph), but G − X is not a tree (resp., unicylic graph) for any X ⊆ V ( G ) with | X | k . In this paper, we extend those extremal results and majorization theorems concerning connected graphs of Liu et al. (2019) to k -cone c -cyclic graphs. We also use a unified method to characterize the extremal maximum and minimum results of many topological indices in the class of k -apex trees and k -apex unicyclic graphs, respectively. The later results extend the main results of Javaid et al. (2019); Liu et al. (2020) and partially answer the open problem of Javaid et al. (2019). Except for the new majorization theorem, some new techniques are also established to deal with the minimum extremal results of this paper.

Let G be a connected graph with vertex set V ( G ) . The degree Kirchhoff index of G is defined as K f ∗ ( G ) = ∑ { u , v } ⊆ V ( G ) d G ( u ) d G ( v ) R G ( u , v ) , where d G ( u ) denotes the degree of the vertex u in G , and R G ( u , v ) denotes the resistance distance between vertices u and v in G . In this paper, we determine maximum degree Kirchhoff index of n -vertex unicyclic graphs with fixed maximum degree, the first seven maximum degree Kirchhoff indices of n -vertex unicyclic graphs, and the corresponding graphs whose degree Kirchhoff indices achieve these values.

The edge-Szeged index of a graph G is defined as S z e ( G ) = ∑ u v ∈ E ( G ) m u ( u v | G ) m v ( u v | G ) , where m u ( u v | G ) (resp., m v ( u v | G ) ) is the number of edges whose distance to vertex u (resp., v ) is smaller than the distance to vertex v (resp., u ), respectively. In this paper, we characterize the graphs with minimum edge-Szeged index among all the unicyclic graphs with given order and perfect matchings.

We introduce the general eccentric connectivity index of a graph G , E C I α ( G ) = ∑ v ∈ V ( G ) e c c G ( v ) d G α ( v ) for α ∈ R , where V ( G ) is the vertex set of G , e c c G ( v ) is the eccentricity of a vertex v and d G ( v ) is the degree of v in G . We present lower and upper bounds on the general eccentric connectivity index for trees of given order, trees of given order and diameter, and trees of given order and number of pendant vertices. Then we give lower and upper bounds on the general eccentric connectivity index for unicyclic graphs of given order, and unicyclic graphs of given order and girth. The upper bounds for trees of given order and diameter, and trees of given order and number of pendant vertices hold for α > 1 . All the other bounds are valid for 0 α ≤ 1 or 0 α 1 . We present all the extremal graphs, which means that our bounds are best possible.

In this note, we point out some problems in the proofs and the main results of Javaid, Jamil and Tomescu (2019), and we also give the correct versions of them.

The first and second Zagreb indices of a graph G are defined as: M 1 ( G ) = ∑ v ∈ V ( G ) d ( v ) 2 and M 2 ( G ) = ∑ u v ∈ E ( G ) d ( u ) d ( v ) , where d ( v ) is the degree of the vertex v . A graph G is said to be a quasi unicyclic graph, if there exists a vertex z ∈ V ( G ) , such that G − z is a unicyclic graph and z is called a quasi vertex. For any integer k ≥ 1 a graph G is called a k -generalized quasi unicyclic graph, if there exists a subset V k ⊆ V ( G ) with cardinality k such that G − V k is a unicyclic graph but for every subset V k − 1 of cardinality k − 1 of V ( G ) , the graph G − V k − 1 is not unicyclic graph. In this paper, we investigate the upper and lower bounds on first and second Zagreb indices for k -generalized quasi unicyclic graphs. Moreover, we characterize the extremal graphs with maximum and minimum Zagreb indices.

In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph G is defined as the sum of the absolute values of the zeros of the matching polynomial of G . In this paper, we first present some new techniques of comparing the matching energies of two graphs. As the applications of these techniques, we can determine the unicyclic graphs of order n with the first to the eighth smallest matching energies for all n ≥ 42 .

Let D denote the distance matrix of a connected graph. The inertia of D is the triple of integers ( n + ( D ) , n 0 ( D ) , n − ( D ) ) , where n + ( D ) , n 0 ( D ) , n − ( D ) denote the number of positive, 0, and negative eigenvalues of D , respectively. The D -energy is the sum of the absolute eigenvalues of D . In this paper, we first obtain the inertia and a formula for the determinant of the distance matrices of the line graphs of unicyclic graphs; Then, as applications, we obtain the graphs with maximum (resp. minimum) D -energy among all these graphs.

Let Γ n be the symmetric group on { 1 , 2 , … , n } and S be the generating set of Γ n . The corresponding Cayley graph is denoted by Γ n ( S ) . If all elements of S are transpositions, a simple way to depict S is via a graph, called the transposition generating graph of S , denoted by A ( S ) (or say simply A ), where the vertex set of A is { 1 , 2 , … , n } , there is an edge in A between i and j if and only if the transposition ( i j ) ∈ S , and Γ n ( S ) is called a Cayley graph obtained from a transposition generating graph A . In this paper, by exploring and utilizing the structural properties of these Cayley graphs, we obtain that the pessimistic diagnosability of Γ n ( S ) is equal to 2 | E ( A ) | − 2 if A has no triangles or 2 | E ( A ) | − 3 if A has a triangle. As corollaries, the pessimistic diagnosability of many kinds of graphs such as Cayley graphs generated by unicyclic graphs, wheel graphs, complete graphs, and tree graphs is obtained.

The Szeged index of a connected graph G is defined as Sz(G)=e=uvE(G)nu(e|G)nv(e|G),where E(G) is the edge set of G, and for any e=uvE(G), nu(e|G) is the number of vertices of G lying closer to vert...

Zero forcing is an iterative graph coloring process whereby a colored vertex with a single uncolored neighbor forces that neighbor to be colored. It is NP-hard to find a minimum zero forcing set – a smallest set of initially colored vertices which forces the entire graph to be colored. We show that the problem remains NP-hard when the initially colored set induces a connected subgraph. We also give structural results about the connected zero forcing sets of a graph related to the graph’s density, separating sets, and certain induced subgraphs. Finally, we give efficient algorithms to find minimum connected zero forcing sets of unicyclic graphs and variants of cactus and block graphs.

In this paper it is shown that the characterizations of trees and unicyclic graphs having a given matching number and minimum connectivity index 12, proposed by Du et al. (2010) remain valid for general connectivity index if 1

We study the Laplacian and the signless Laplacian energy of connected unicyclic graphs, obtaining a tight upper bound for this class of graphs. We also find the connected unicyclic graph on n vertices having largest (signless) Laplacian energy for 3n13. For n11, we conjecture that the graph consisting of a triangle together with n3 balanced distributed pendent vertices is the candidate having the maximum (signless) Laplacian energy among connected unicyclic graphs on n vertices. We prove this conjecture for many classes of graphs, depending on , the number of (signless) Laplacian eigenvalues bigger than or equal to 2.

Let G be a graph of order n . A dominating set of G is a subset of vertices of G , say S , such that every vertex in V ( G ) ? S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ? i = 1 n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i . A root of D ( G , x ) is called a domination root of G . Let ? = ? ( G ) be the minimum degree of vertices of G . We prove that all roots of D ( G , x ) lies in the set { z : | z + 1 | ? 2 n - 1 ? + 1 } . We show that D ( G , x ) has at least ? - 1 non-real roots. In particular, we prove that if all roots of D ( G , x ) are real, then ? = 1 . We construct an infinite family of graphs such that all roots of their polynomials are real. Motivated by a conjecture (Akbari, et?al. 2010) which states that every integer root of D ( G , x ) is - 2 or 0, we prove that if ? ? 2 n 3 - 1 , then every integer root of D ( G , x ) is - 2 or 0. Also we prove that the conjecture is valid for trees and unicyclic graphs. Finally we characterize all graphs that their domination roots are integer.

The energy of a graph $G$, denoted by $E(G)$, is defined as the sum of the absolute values of all eigenvalues of $G$. Let $n$ be an even number and $\mathbb{U}_{n}$ be the set of all conjugated unicyclic graphs of order $n$ with maximum degree at most $3$. Let $S_n^{\frac{n}{2}}$ be the radialene graph obtained by attaching a pendant edge to each vertex of the cycle $C_{\frac{n}{2}}$. In [Y. Cao et al., On the minimal energy of unicyclic H\"{u}ckel molecular graphs possessing Kekul\'{e} structures, Discrete Appl. Math. 157 (5) (2009), 913--919], Cao et al. showed that if $n\geq 8$, $S_n^{\frac{n}{2}}\ncong G\in \mathbb{U}_{n}$ and the girth of $G$ is not divisible by $4$, then $E(G)>E(S_n^{\frac{n}{2}})$. Let $A_n$ be the unicyclic graph obtained by attaching a $4$-cycle to one of the two leaf vertices of the path $P_{\frac{n}{2}-1}$ and a pendent edge to each other vertices of $P_{\frac{n}{2}-1}$. In this paper, we prove that $A_n$ is the unique unicyclic graph in $\mathbb{U}_{n}$ with minimal energy., Comment: 20 pages

In this paper, we show that in the class of connected unicyclic graphs G of order n ? 3 having 0 ? k ? n - 3 pendant vertices, the unique graph G having minimum general sum-connectivity index ? α ( G ) consists of C n - k and k pendant vertices adjacent to a unique vertex of C n - k , if - 1 ? α < 0 . This property does not hold for zeroth-order general Randic index 0 R α ( G ) .

Let @p=(d"1,d"2,...,d"n) and @p^'=(d"1^',d"2^',...,d"n^') be two different non-increasing degree sequences. We write @[email protected][email protected]^', if and only if @?"i"="1^nd"[email protected]?"i"="1^nd"i^', and @?"i"="1^jd"[email protected][email protected]?"i"="1^jd"i^' for all j=1,2,...,n. Let @C(@p) be the class of connected graphs with degree sequence @p. The second Zagreb index of a graph G is denoted by M"2(G)[email protected]?"u"v"@?"E"("G")d(u)d(v). In this paper, we characterize an extremal unicyclic graph that achieves the maximum second Zagreb index in the class of unicyclic graphs with given degree sequence, and we also prove that if @[email protected][email protected]^', @p and @p^' are unicyclic degree sequences and U^* and U^*^* have the maximum second Zagreb indices in @C(@p) and @C(@p^'), respectively, then M"2(U^*)=17 vertices.

The general sum-connectivity index of a graph G is defined as @g"@a(G)=@?"u"v"@?"E"("G")(d(u)+d(v))^@a, where d(u) denotes the degree of vertex u in G, and @a is a real number. In this paper, we characterize n-vertex connected unicyclic graphs with girth k>=4, having the minimum, the second and the third minimum general sum-connectivity indices for n>=8 and -1@?@a

We give bounds for the revised Szeged index, and determine the n-vertex unicyclic graphs with the smallest, the second-smallest and the third-smallest revised Szeged indices for n≥5, and the n-vertex unicyclic graphs with the kth-largest revised Szeged indices for all k up to 3 for n=5, to 5 for n=6, to 6 for n=7, to 7 for n=8, and to ⌊n2⌋+4 for n≥9. We also determine the n-vertex unicyclic graphs of cycle length r, 3≤r≤n, with the smallest and the largest revised Szeged indices.

A unicyclic graph is a graph whose number of edges is equal to the number of vertices. Guo Shu-Guang [S.G. Guo, The largest Laplacian spectral radius of unicyclic graph, Appl. Math. J. Chinese Univ. Ser. A. 16 (2) (2001) 131–135] determined the first four largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. In this paper, we extend this ordering by determining the fifth to the ninth largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices.

Connected graphs in which the number of edges equals the number of vertices are called unicyclic graphs. In this paper, all unicyclic graphs whose second largest eigenvalue does not exceed 1 have been determined.

The Hosoya index z(G) of a graph G is defined as the number of matchings of G and the Merrifield-Simmons index i(G) of G is defined as the number of independent sets of G. Let U(n,m) be the set of all unicyclic graphs on n vertices with @a^'(G)=m. Denote by U^1(n,m) the graph on n vertices obtained from C"3 by attaching n-2m+1 pendant edges and m-2 paths of length 2 at one vertex of C"3. Let U^2(n,m) denote the n-vertex graph obtained from C"3 by attaching n-2m+1 pendant edges and m-3 paths of length 2 at one vertex of C"3, and one pendant edge at each of the other two vertices of C"3. In this paper, we show that U^1(n,m) and U^2(n,m) have minimal, second minimal Hosoya index, and maximal, second maximal Merrifield-Simmons index among all graphs in U(n,m)@?{C"n}, respectively.

Let Un,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in Un,d with the maximum number of independent sets, is characterized.

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as D^'(G)[email protected]?"{"u","v"}"@?"V"("G")(deg"G(u)+deg"G(v))d(u,v), where deg"G(u) is the degree of vertex u, and d(u,v) denotes the distance between u and v. Here we characterize n-vertex unicyclic graphs with girth k, having minimum and maximum degree distance, respectively. Furthermore, we prove that the graph B"n, obtained from two triangles linked by a path, is the unique graph having the maximum degree distance among bicyclic graphs, which resolves a recent conjecture of Tomescu.

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M2(G)/m≥M1(G)/n, where M1 and M2 are the first and second Zagreb indices. Hansen and Vukičević proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M2/(m−1)>M1/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.