Search

In a graph G, the cardinality of the smallest ordered set of vertices that distinguishes every element of V (G) (resp. E(G)) is called the vertex (resp. edge) metric dimension of G. In [16] it was shown that both vertex and edge metric dimension of a unicyclic graph G always take values from just two explicitly given consecutive integers that are derived from the structure of the graph. A natural problem that arises is to determine under what conditions these dimensions take each of the two possible values. In this paper for each of these two metric dimensions we characterize three graph configurations and prove that it takes the greater of the two possible values if and only if the graph contains at least one of these configurations. One of these configurations is the same for both dimensions, while the other two are specific for each of them. This enables us to establish the exact value of the metric dimensions for a unicyclic graph and also to characterize when each of these two dimensions is greater than the other one., Comment: 19 pages, 6 figures

In this paper the problem of maximizing vertex-degree function index H f ( G ) for trees and unicyclic graphs G of order n and independence number s is solved for strictly convex functions f ( x ) . In the case of unicyclic graphs f ( x ) must also satisfy strict inequality f ( 4 ) + 3 f ( 2 ) > 3 f ( 3 ) + f ( 1 ) . These conditions are fulfilled by general first Zagreb index 0 R α ( G ) for α > 2 , second multiplicative Zagreb index ∏ 2 ( G ) and sum lordeg index S L ( G ) . The extremal graphs are unique and they are stars or have diameter equal to three or to four. The same results are valid for the corresponding minimization problem when f ( x ) is strictly concave and the inequality is reversed.

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.

For α ∈ R , the general sum-connectivity index of a graph G is defined as χ α ( G ) = ∑ u v ∈ E ( G ) [ d e g G ( u ) + d e g G ( v ) ] α , where E ( G ) is the edge set of G and d e g G ( v ) is the degree of a vertex v in G . Let U n , d be the set of unicyclic graphs with n vertices and diameter d .We present the graph with the smallest general sum-connectivity index among the graphs in U n , d for − 1 ≤ α 0 and the graph with the largest general sum-connectivity index among the graphs in U n , d for 0 α 1 . Sharp lower bounds on the classical sum-connectivity index and the harmonic index for graphs in U n , d follow from the lower bound on the general sum-connectivity index.

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.

We find a basis for the null space of the adjacency matrix of unicyclic graphs. Based on the support of such a basis, we determine a null decomposition of these graphs. As an application, we obtain closed formulas for the independence and matching numbers of unicyclic graphs that solely rely on the support of the graph.

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

The P I index of a graph G is defined by P I ( G ) = ∑ e = ( u , v ) ∈ E [ m u ( e | G ) + m v ( e | G ) ] where m u ( e | G ) be the number of edges in G lying closer to vertex u than to vertex v and m v ( e | G ) be the number of edges in G lying closer to vertex v than to vertex u . In this paper, we give the upper and lower bounds on the P I index of connected unicyclic and bicyclic graphs with given girth and completely characterize the corresponding extremal graphs. From our results, it is easy to get the bounds and extremal graphs of the unicyclic and bicyclic graphs.

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

Let G be a simple connected graph with vertex set V ( G ) . The matching polynomial of G is defined as M G ( x ) = ∑ k = 0 n ∕ 2 ( − 1 ) k m ( G , k ) x n − 2 k , where m ( G , k ) denotes the number of ways in which k independent edges can be selected in G . Let λ 1 ( G ) be the largest root of M G ( x ) . We determine the unicyclic graphs with the four largest and the two smallest λ 1 ( G ) -values.

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

The chemical energy of an n-vertex graph G is defined as CE(G)={2@?i=1n2@l"i(G)if n is even ,2@?i=1n-12@l"i(G)+@l"n"+"1"2(G)if n is odd . Here @l"1(G),@l"2(G),...,@l"n(G) are the eigenvalues of G arranged in non-increasing order. We give lower and upper bounds for the chemical energy of graphs, and determine the extremal unicyclic graphs with minimal and maximal chemical energies.

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.

The reciprocal complementary Wiener number of a connected graph G is defined as RCW(G)=∑{u,v}⊆V(G)1d+1−d(u,v|G) where V(G) is the vertex set, d(u,v|G) is the distance between vertices u and v, d is the diameter of G. We determine the trees with the smallest, the second smallest and the third smallest reciprocal complementary Wiener numbers, and the unicyclic and bicyclic graphs with the smallest and the second smallest reciprocal complementary Wiener numbers.

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.