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.

Let G be a graph with set of vertices $$V\left( G\right)$$ and set of edges $$E\left( G\right)$$ . The Sombor index is a recently introduced vertex-degree-based-topological index, defined as $$SO(G) = \sum\limits_{uv \in E(G)} {\sqrt {{{({d_u})}^2} + {{({d_v})}^2}} } ,$$ where $$d_{u}$$ denotes the degree of the vertex u. In this paper we study the extremal values of SO over the set of unicyclic graphs and over the set of bicyclic graphs.

The max–min rodeg ( $${M\!m_{sde}}$$ ) index is a useful topological index in mathematical chemistry. Damir Vuki $$\check{\text {c}}$$ evi $$\acute{\text {c}}$$ studied the mathematical properties of the max–min rodeg index. In this paper, we determine the n-vertex trees with the second, the third and the fourth for $$n\ge 7$$ , and the fifth for $$n\ge 10$$ minimum $$M\!m_{sde}$$ indices, unicyclic graphs with the second and the third for $$n\ge 5$$ , the fourth, the fifth and the sixth for $$n\ge 7$$ , and the seventh for $$n\ge 9$$ minimum $$M\!m_{sde}$$ indices, and bicyclic graphs with the first for $$n\ge 4$$ , the second and the third for $$n\ge 6$$ , and the fourth for $$n\ge 8$$ minimum $$M\!m_{sde}$$ indices.

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.

Graceful labelings are an effective tool to find cyclic decompositions of complete graphs and complete bipartite graphs. The strongest kind of graceful labeling, the α-labeling, is in the center of the research field of graph labelings, the existence of an α-labeling of a graph implies the existence of several, apparently non-related, other labelings for that graph. Furthermore, graphs with α-labelings can be combined to form new graphs that also admit this type of labeling. The standard way to combine these graphs is to identify every vertex of a base graph with a vertex of another graph. These methods have in common that all the graphs involved, except perhaps the base, have the same size. In this work, we do something different, we prove the existence of an α-labeling of a tree obtained by attaching paths of different lengths to the vertices of a base path, in such a way that the lengths of the pendent paths form an arithmetic sequence with difference one, where consecutive vertices of the base path are identified with paths which lengths are consecutive elements of the sequence. These α-trees are combined in several ways to generate new families of α-trees. We also prove that these trees can be used to create unicyclic graphs with an α-labeling. In addition, we show that the pendent paths can be substituted by equivalent α-trees to produce new α-trees, obtaining in this manner a quite robust category of α-trees.

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 Kirchhoff index K f (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 K f ( $$\overline{T}$$ ) and the first four maximum values of K f (Ū), where $$\overline{T}$$ and Ū are the complements of a tree T and unicyclic graph U, respectively.

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.

The first general multiplicative Zagreb index of a graph G is defined as $$P_1^a (G) = \prod _{v \in V(G)} (deg_G (v))^a$$ and the second general multiplicative Zagreb index is $$P_2^a (G) = \prod _{v \in V(G)} (deg_G (v))^{a \, deg_G (v)}$$ , where V(G) is the vertex set of G, $$deg_{G} (v)$$ is the degree of v in G and $$a \ne 0$$ is a real number. We present lower and upper bounds on the general multiplicative Zagreb indices for trees and unicyclic graphs of given order with a perfect matching. We also obtain lower and upper bounds for trees and unicyclic graphs of given order and matching number. All the trees and unicyclic graphs which achieve the bounds are presented, thus our bounds are sharp. Bounds for the classical multiplicative Zagreb indices are special cases of our theorems and those bounds are new results as well.

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 reduced second Zagreb index $$RM_2$$ of a graph G is defined as $$RM_2(G)=\sum _{uv\in E(G)}(d_G(u)-1)(d_G(v)-1)$$, where $$d_G(u)$$ is the degree of the vertex u of graph G. Furtula et al. (Discrete Appl Math 178: 83–88, 2014) studied the difference between the classical Zagreb indices of graphs and showed that it is closely related to $$RM_2$$. In this paper, we obtain an upper bound in terms of order n and size m on $$RM_2$$ of $$K_{r+1}$$-free graphs. Also we prove that among all graphs of order n with chromatic number $$\chi $$, the Turan graph $$T_{n,\,\chi }$$ is the unique graph having the maximum $$RM_2$$. Furthermore, we completely characterize the extremal graphs with respect to $$RM_2$$ among all unicyclic graphs of order n with girth g.

The non-self-centrality number and the total irregularity of a connected graph G are defined as N ( G ) = ∑ | e G ( v i ) − e G ( v j ) | and i r r t ( G ) = ∑ | d e g G ( v j ) − d e g G ( v i ) | , with summations embracing all pairs of vertices, degG(vi) and ɛG(vi) denoting the degree and eccentricity of the vertex vi. In this paper, we show that there exists a graph G with diameter d such that irrt(G) > N(G) for any integer d ≥ 2. This gives a complete proof of Theorem 10 in Xu et al. (2018), where Xu et al. did not prove it really for d ≥ 4. Moreover, we prove that N(T) > irrt(T) for any tree T of order n ≥ 10 with diameter d ≥ 2 + 26 11 n and maximum degree 4 avoiding degree 3, determine all trees(unicyclic graphs) and with diameter 3 and irrt(T) > N(T) and give a sufficient condition for trees with diameter 4 and irrt(T) > N(T). These partially solve Problems 26 and 27 in the above-mentioned literature.

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.

We prove that each of the 34 non-isomorphic connected unicyclic bipartite graphs with eight edges decomposes the complete graph K n whenever the necesary conditions are satisfied.

Graph energy and domination in graphs are most studied areas of graph theory. In this paper we try to connect these two areas of graph theory by introducing c-dominating energy of a graph G. First, we show the chemical applications of c-dominating energy with the help of well known statistical tools. Next, we obtain mathematical properties of c-dominating energy. Finally, we characterize trees, unicyclic graphs, cubic and block graphs with equal dominating and c-dominating energy.

Let G be a graph. A set D ⊆ V(G) is a global dominating set of G if D is a dominating set of G and $\overline G$. γg(G) denotes global domination number of G. A set D ⊆ V(G) is an outer independent global dominating set (OIGDS) of G if D is a global dominating set of G and V(G) − D is an independent set of G. The cardinality of the smallest OIGDS of G, denoted by γgoi(G), is called the outer independent global domination number of G. An outer independent global dominating set of cardinality γgoi(G) is called a γgoi-set of G. In this paper we characterize trees T for which γgoi(T) = γ(T) and trees T for which γgoi(T) = γg(T) and trees T for which γgoi(T) = γoi(T) and the unicyclic graphs G for which γgoi(G) = γ(G), and the unicyclic graphs G for which γgoi(G) = γg(G).

The first and the second Zagreb indices of a graph G are defined as $$M_1(G)= \sum _{v\in V_G}d_v^2 $$ and $$ M_2(G)= \sum _{uv\in E_G}d_ud_v$$ , where $$d_v,\, d_u$$ are the degrees of vertices $$v,\, u$$ in G. The difference of Zagreb indices of G is defined as $$\Delta M(G)=M_2(G)-M_1(G)$$ . A cactus is a connected graph in which every block is either an edge or a cycle. Let $$\mathscr {C}_{n,k}$$ be the set of all n-vertex cacti with k pendant vertices and let $$\mathscr {C}_n^r$$ be the set of all n-vertex cacti with r cycles. In this paper, the sharp upper bound on $$\Delta M(G)$$ of graph G among $$\mathscr {C}_{n,k}$$ (resp. $$\mathscr {C}_n^r$$ ) is established. Combining the results in Furtula et al. (Discrete Appl Math 178:83–88, 2014) and our results obtained in the current paper, sharp upper bounds on $$\Delta M(G)$$ of n-vertex cacti and n-vertex unicyclic graphs are determined, respectively. All the extremal graphs are characterized.

Let G be a connected graph. The Szeged index of G is defined as $$Sz(G)=\sum \nolimits _{e=uv\in E(G)}n_{u}(e|G)n_{v}(e|G)$$ , where $$n_{u}(e|G)$$ (resp., $$n_{v}(e|G)$$ ) is the number of vertices whose distance to vertex u (resp., v) is smaller than the distance to vertex v (resp., u), and $$n_{0}(e|G)$$ is the number of vertices equidistant from both ends of e. Let $$\mathcal {M}(2\beta )$$ be the set of unicyclic graphs with order $$2\beta $$ and a perfect matching. In this paper, we determine the minimum value of Szeged index and characterize the extremal graph with the minimum Szeged index among all unicyclic graphs with perfect matchings.

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.

For a connected graph, the first Zagreb eccentricity index $\xi _{1}$ ξ 1 is defined as the sum of the squares of the eccentricities of all vertices, and the second Zagreb eccentricity index $\xi _{2}$ ξ 2 is defined as the sum of the products of the eccentricities of pairs of adjacent vertices. In this paper, we mainly present a different and universal approach to determine the upper bounds respectively on the Zagreb eccentricity indices of trees, unicyclic graphs and bicyclic graphs, and characterize these corresponding extremal graphs, which extend the ordering results of trees, unicyclic graphs and bicyclic graphs in (Du et al. in Croat. Chem. Acta 85:359–362, 2012; Qi et al. in Discrete Appl. Math. 233:166–174, 2017; Li and Zhang in Appl. Math. Comput. 352:180–187, 2019). Specifically, we determine the n-vertex trees with the i-th largest indices $\xi _{1}$ ξ 1 and $\xi _{2}$ ξ 2 for i up to $\lfloor n/2+1 \rfloor $ ⌊ n / 2 + 1 ⌋ compared with the first three largest results of $\xi _{1}$ ξ 1 and $\xi _{2}$ ξ 2 in (Du et al. in Croat. Chem. Acta 85:359–362, 2012), the n-vertex unicyclic graphs with respectively the i-th and the j-th largest indices $\xi _{1}$ ξ 1 and $\xi _{2}$ ξ 2 for i up to $\lfloor n/2-1 \rfloor $ ⌊ n / 2 − 1 ⌋ and j up to $\lfloor 2n/5+1 \rfloor $ ⌊ 2 n / 5 + 1 ⌋ compared with respectively the first two and the first three largest results of $\xi _{1}$ ξ 1 and $\xi _{2}$ ξ 2 in (Qi et al. in Discrete Appl. Math. 233:166–174, 2017), and the n-vertex bicyclic graphs with respectively the i-th and the j-th largest indices $\xi _{1}$ ξ 1 and $\xi _{2}$ ξ 2 for i up to $\lfloor n/2-2\rfloor $ ⌊ n / 2 − 2 ⌋ and j up to $\lfloor 2n/15+1\rfloor $ ⌊ 2 n / 15 + 1 ⌋ compared with the first two largest results of $\xi _{2}$ ξ 2 in (Li and Zhang in Appl. Math. Comput. 352:180–187, 2019), where $n\ge 6$ n ≥ 6 . More importantly, we propose two kinds of index functions for the eccentricity-based topological indices, which can yield more general extremal results simultaneously for some classes of indices. As applications, we obtain and extend some ordering results about the average eccentricity of bicyclic graphs, and the eccentric connectivity index of trees, unicyclic graphs and bicyclic graphs.

In a graph G, the cardinality of the smallest ordered set of vertices that distinguishes every element of V(G)U E(G) is called the mixed metric dimension of G, and it is denoted by mdim(G). In [12] it was conjectured that for a graph G with cyclomatic number c(G) it holds that mdim(G) = 3. In this paper we determine that for every Theta graph G, the mixed metric dimension mdim(G) equals 3 or 4, with 4 being attained if and only if G is a balanced Theta graph. Thus, for balanced Theta graphs the above inequality is also tight. We conclude the paper by further conjecturing that there are no other graphs, besides the ones mentioned here, for which the equality mdim(G) = L1(G) + 2c(G) holds., 14 pages, 3 figures

In a graph G, the cardinality of the smallest ordered set of vertices that distinguishes every element of V (G)[E(G) is called the mixed metric dimension of G. In this paper we first establish the exact value of the mixed metric dimension of a unicycic graph G which is derived from the structure of G. We further consider graphs G with edge disjoint cycles in which a unicyclic restriction Gi is introduced for each cycle Ci: Applying the result for unicyclic graph to each Gi then yields the exact value of the mixed metric dimension of such a graph G. The obtained formulas for the exact value of the mixed metric dimension yield a simple sharp upper bound on the mixed metric dimension, and we conclude the paper conjecturing that the analogous bound holds for general graphs with prescribed cyclomatic number., 11 pages, 3 figures

Denote by Lg, l the lollipop graph obtained by attaching a pendant path P = v g v g + 1 ⋯ v g + l (l ≥ 1) to a cycle C = v 1 v 2 ⋯ v g v 1 (g ≥ 3). A F g , l − g r a p h of order n ≥ g + 1 is defined to be the graph obtained by attaching n − g − l pendent vertices to some of the nonpendant vertices of Lg, l in which each vertex other than v g + l − 1 is attached at most one pendant vertex. A F g , l ∘ -graph is a F g , l − g r a p h in which vg is attached with pendant vertex. Denote by qmin the least Q − e i g e n v a l u e of a graph. In this paper, we proceed on considering the domination number, the least Q-eigenvalue of a graph as well as their relation. Further results obtained are as follows: (i) some results about the changing of the domination number under the structural perturbation of a graph are represented; (ii) among all nonbipartite unicyclic graphs of order n, with both domination number γ and girth g ( g ≤ n − 1 ), the minimum qmin attains at a F g , l -graph for some l; (iii) among the nonbipartite graphs of order n and with given domination number which contain a F g , l ∘ -graph as a subgraph, some lower bounds for qmin are represented; (iv) among the nonbipartite graphs of order n and with given domination number n 2 .

Given a connected graph G, the edge-Szeged index Sze(G) is defined as S z e ( G ) = ∑ e = u v ∈ E m u ( e ) m v ( e ) , where mu(e) and mv(e) are, respectively, the number of edges of G lying closer to vertex u than to vertex v and the number of edges of G lying closer to vertex v than to vertex u. In this paper, some extremal problems on the edge-Szeged index of unicyclic graphs are considered. All the n-vertex unicyclic graphs with a given diameter having the minimum edge-Szeged index are identified. Using a unified approach we identify the n-vertex unicyclic graphs with the minimum, second minimum, third minimum and fourth minimum edge-Szeged indices.

The augmented Zagreb index of a graph G, which is proven to be a valuable predictive index in the study of the heat of formation of octanes and heptanes, is defined as A Z I ( G ) = ∑ u v ∈ E ( G ) ( d ( u ) d ( v ) d ( u ) + d ( v ) − 2 ) 3 , where E(G) is the edge set of G, d(u) and d(v) are the degrees of the terminal vertices u and v of edge uv. In this paper, the lower bounds on augmented Zagreb index of trees and unicyclic graphs with perfect matchings are presented, and the corresponding extremal trees and uinicyclic graphs with perfect matchings are characterized.

Let G be a graph with edge set E(G). The Randic and sum-connectivity indices of G are defined as R ( G ) = ∑ u v ∈ E ( G ) 1 d e g G ( u ) d e g G ( v ) and S C I ( G ) = ∑ u v ∈ E ( G ) 1 d e g G ( u ) + d e g G ( v ) , respectively, where degG(u) denotes the vertex degree of u in G. In this paper, the extremal Randic and sum-connectivity index among all n-vertex chemical trees, n ≥ 13, connected chemical unicyclic graphs, n ≥ 7, connected chemical bicyclic graphs, n ≥ 6 and connected chemical tricyclic graphs, n ≥ 8, were presented.

Let G be a graph and A(G) the adjacency matrix of G. The polynomial π ( G , x ) = per ( x I − A ( G ) ) is called the permanental polynomial of G, and the permanental sum of G is the summation of the absolute values of the coefficients of π(G, x). In this paper, we investigate properties of permanental sum of a graph, prove recursive formulas to compute the permanental sum of a graph, and show that the ordering of graphs with respect to permanental sum. Furthermore, we determine the upper and lower bounds of permanental sum of unicyclic graphs, and the corresponding extremal unicyclic graphs are also determined.

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.

We investigate the average range of 1-Lipschitz mappings (graph-indexed random walks) of a given connected graph. This parameter originated in statistical physics, it is connected to the study of random graph homomorphisms and generalizes standard random walks on Z . Our first goal is to prove a closed-form formula for this parameter for cycle graphs. The second one is to prove two conjectures, the first by Benjamini, Haggstrom and Mossel and the second by Loebl, Nesetřil and Reed, for unicyclic graphs. This extends a result of Wu, Xu, and Zhu [5] who proved the aforementioned conjectures for trees.

Let G be a simple graph on n vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial I(G,x)=∑k=0ns(G,k)xk$I(G,x) = \sum\nolimits_{k = 0}^n {s\left({G,k} \right)x^k }$, where s(G, k) is the number of independent sets of G with size k and s(G, 0) = 1. A unicyclic graph is a graph containing exactly one cycle. Let Cn be the cycle on n vertices. In this paper we study the independence polynomial of unicyclic graphs. We show that among all connected unicyclic graphs G on n vertices (except two of them), I(G, t) > I(Cn, t) for sufficiently large t. Finally for every n ≥ 3 we find all connected graphs H such that I(H, x) = I(Cn, x).

The harmonic index of a graph G is defined as the sum of the weights 2d(u)+d(v)${2 \over {d(u) + d(v)}}$ of all edges uv of G, where d(u) denotes the degree of a vertex u in G. In this paper, we present the minimum harmonic index for unicyclic graphs with given diameter and characterize the corresponding extremal graphs. This answers an unsolved problem of Zhu and Chang [26].

Let G be a connected graph with vertex set V G . The eccentric resistance-distance sum of G is defined as ξ R ( G ) = ∑ { u , v } ⊆ V G ( e G ( u ) + e G ( v ) ) R u v , where e G ( ⋅ ) is the eccentricity of the corresponding vertex and R u v is the resistance-distance between u and v in G. In this paper, among the bipartite graphs of diameter 2, the graphs having the smallest and the largest eccentric resistance-distance sums are characterized, respectively. Among the bipartite graphs of diameter 3, the graphs having the smallest and second smallest eccentric resistance-distance sums are characterized, respectively. As well the graphs of diameter 3 having the smallest eccentric resistance-distance sum are identified. Furthermore, the n-vertex unicyclic graphs with given girth having the smallest and second smallest eccentric resistance-distance sums are identified, respectively. Consequently, n-vertex unicyclic graphs having the smallest and second smallest eccentric resistance-distance sums are characterized, respectively.

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.

Let S n c be the set of all connected graph each of which is a complement of an n -vertex unicyclic graph. Li and Wang (2012) determined the graphs with the least signless Laplacian eignvalue among all the graphs of the complements of n -vertex trees. In this paper, as a continuance of it, the unique graph among S n c which minimizes the least signless Laplacian eigenvalue is identified.

The unique graphs with maximum spectral radius and signless Laplacian spectral radius are determined among trees, unicyclic graphs and bicyclic graphs respectively with fixed numbers of vertices and branch vertices (vertices of degree at least 3) using a unified approach.

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.

We characterize unicyclic graphs that are singular using the support of the null space of their pendant trees. From this, we obtain closed formulas for the independence and matching numbers of a unicyclic graph, based on the support of its subtrees. These formulas allows one to compute independence and matching numbers of unicyclic graphs using linear algebra methods.

The Wiener index is the sum of distances between all pairs of distinct vertices in a connected graph, which is the oldest topological index related to molecular branching. In the article we characterize the graphs having the minimum Wiener index among all n-vertex unicyclic graphs with a fixed diameter.