Search

The well-studied eccentric connectivity index directly consider the contribution of all edges in a graph. By considering the total eccentricity sum of all non-adjacent vertex, Hua et al. proposed a new topological index, namely, eccentric connectivity coindex of a connected graph. The eccentric connectivity coindex of a connected graph $ G $ is defined as \begin{document}$ \overline{\xi}^{c}(G) = \sum\limits_{uv\notin E(G)} (\varepsilon_{G}(u)+\varepsilon_{G}(v)). $\end{document} Where $ \varepsilon_{G}(u) $ (resp. $ \varepsilon_{G}(v) $) is the eccentricity of the vertex $ u $ (resp. $ v $). In this paper, some extremal problems on the $ \overline{\xi}^{c} $ of graphs with given parameters are considered. We present the sharp lower bounds on $ \overline{\xi}^{c} $ for general connecteds graphs. We determine the smallest eccentric connectivity coindex of cacti of given order and cycles. Also, we characterize the graph with minimum and maximum eccentric connectivity coindex among all the trees with given order and diameter. Additionally, we determine the smallest eccentric connectivity coindex of unicyclic graphs with given order and diameter and the corresponding extremal graph is characterized as well.

Given a graph G, the burning number of G is the smallest integer k for which there are vertices $$x_1, x_2,\ldots ,x_k$$ such that $$(x_1,x_2,\ldots ,x_k)$$ is a burning sequence of G. It has been shown that the graph burning problem is NP-complete, even for trees with maximum degree three, or linear forests. A t-unicyclic graph is a unicycle graph in which the unique vertex in the graph with degree greater than two has degree $$ t + 2 $$ . In this paper, we first present the bounds for the burning number of t-unicyclic graphs, and then use the burning numbers of linear forests with at most three components to determine the burning number of all t-unicyclic graphs for $$t\le 2$$ .

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.

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.

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.

Let G be a nontrivial connected graph with a vertex-coloring c: $$V(G)\rightarrow \{1,2,\ldots ,q\},q\in N$$ . For a set $$S\subseteq V(G)$$ and $$|S|\ge 2$$ , a subtree T of G satisfying $$S\subseteq V(T)$$ is said to be an S-Steiner tree or simply S-tree. The S-tree T is called a vertex-rainbow S-tree if the vertices of $$V(T)\setminus S$$ have distinct colors. Let k be a fixed integer with $$2\le k\le |V(G)|$$ , if every k-subset S of V(G) has a vertex-rainbow S-tree, then G is said to be vertex-rainbow k-tree connected. The k-vertex-rainbow index of G, denoted by $$rvx_{k}(G)$$ , is the minimum number of colors that are needed in order to make G vertex-rainbow k-tree connected. In this paper, we study the 3-vertex-rainbow index of unicyclic graphs and complementary graphs, respectively.

In this paper, we determine the unique graph among complements of unicyclic graphs which maximizes the distance spectral radius. We also characterize the unique graph among complements of unicyclic graphs of diameter three which maximizes the least distance eigenvalues.

Let g ( G ) denote the girth of a graph G. In this paper, we determine the unique graph with the maximum least Q-eigenvalue among all unicyclic graphs of order n = 6k ( k ≥ 8 ) with perfect matchin...

The ABC matrix of a graph G is a square matrix, where the ( i , j ) -entry A B C i j = d i + d j − 2 d i d j if there is an edge between vertices i and j in G, and A B C i j = 0 otherwise. The ABC spectral radius of G, denoted by ν 1 ( G ) , is the largest eigenvalue of the ABC matrix of G. In this paper, we prove that for a unicyclic graph G of order n ≥ 4 , 2 = ν 1 ( C n ) ≤ ν 1 ( G ) ≤ ν 1 ( S n + e ) , with equality if and only if G ≅ C n for the lower bound, and if and only if G ≅ S n + e for the upper bound. This solves a conjecture by Ghorbani et al.

Let T be the group of all complex numbers z with | z | = 1 . A complex unit gain graph, or simply a T -gain graph, is a triple Φ = ( G , T , φ ) consisting of a graph G = ( V , E ) , the circle group T and a gain function φ : E → → T such that φ ( v i v j ) = φ ( v j v i ) − 1 = φ ( v j v i ) ‾ for any adjacent vertices v i and v j . The adjacency matrix A ( Φ ) of the T -gain graph Φ = ( G , T , φ ) of order n is an n × n complex matrix ( a i j ) , where a i j = a j i ‾ = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 if otherwise. The rank of a T -gain graph Φ, denoted by r ( Φ ) , is the rank of the adjacency matrix of Φ. Yu et al. [24] obtained some properties of inertia indexes of a T -gain graph and they characterized the T -gain unicyclic graphs with small positive or negative index. Lu [8] characterized the T -gain bicyclic graphs with rank 2 , 3 or 4. Motivated by above, we determine the rank of a T -gain unicyclic graph and classify the T -gain graphs with rank 2.

Let G ( n , p ) denote the set of unicyclic graphs with n vertices and p ≥ 1 pendent vertices. Hua and Wang (2007) [4] claim to have determined the graph with minimal energy in G ( n , p ) except for the case when n = p + 5 which was left as an open problem. This case was later solved by Huo et al. (2010) [5] . In this paper, we provide a counter example to show that the main result of Hua and Wang (2007) is not true. We also give the correct form of the characterization of unicyclic graphs with given number of pendent vertices and minimal energy. We make use of the well known Coulson's integral formula for the energy of graphs. Our proof is more general and also includes the case n = p + 5 considered by Huo, Ji and Li (2010).

Given two graphs G and H, the k-colored Gallai–Ramsey number $$gr_k(G : H)$$ is defined to be the minimum integer n such that every k-coloring of the complete graph on n vertices contains either a rainbow copy of G or a monochromatic copy of H. In this paper, we consider $$gr_k(K_3 : H)$$ , where H is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai–Ramsey numbers for eight of them have been studied step by step in several papers. We determine all the Gallai–Ramsey numbers for the remaining five graphs, and we also obtain some related results for a class of unicyclic graphs. As applications, we find the mixed Ramsey spectra $$S(n; H, K_3)$$ for these graphs by using the Gallai–Ramsey numbers.

A graph G admits a graceful labeling if there is a one-to-one map f from the set of vertices of G to such that when an edge xy is assigned the label the resulting set of edge labels is When such a labeling exists, G is called graceful. Rosa showed that a cycle Cn () is graceful if and only if n is congruent to 0 or 3 modulo 4. Truszczyński conjectured that unicyclic graphs, except the cycles in Rosa’s result are graceful. Several classes of unicyclic graphs are known to be graceful. In this article, we present a survey of results related to Truszczyński’s conjecture. We also present a new class of graceful unicyclic graphs.

The Estrada index of a graph G is defined as EE(G)=∑i=1neλi, where λ1,λ2,…,λn are the eigenvalues of the adjacency matrix of G. A unicyclic graph is a connected graph with a unique cycle. Let U(n,d) be the set of all unicyclic graphs with n vertices and diameter d. In this paper, we give some transformations which can be used to compare the Estrada indices of two graphs. Using these transformations, we determine the graphs with the maximum Estrada indices among U(n,d). We characterize two candidate graphs with the maximum Estrada index if d is odd and three candidate graphs with the maximum Estrada index if d is even.

Let G be a unicyclic graph with edge ideal I ( G ) . For any integer s ≥ 1 , we denote the s-th symbolic power of I ( G ) by I ( G ) ( s ) . It is shown that reg ( I ( G ) ( s ) ) = reg ( I ( G ) s ) , for every s ≥ 1 .

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.

A connected graph G = (V(G), E(G)) is called a quasi-unicyclic graph, if there exists u0 ∈ V(G) such that G − u0 is a unicyclic graph. Denote Q(n, d0) = {G: G is a quasi-unicyclic graph of order n with G − u0 being a unicyclic graph and dG(u0) = d0}. Let A(G) be the adjacency matrix of a graph G, and let λ1(G), λ2(G),…, λn(G) be the eigenvalues in non-increasing order of A(G). The number $$\sum\limits_{i = 1}^n {\lambda _i^k(G)} $$ (k = 0,1, …, n−1) is called the k-th spectral moment of G, denoted by Sk (G). Let S (G) = (S0(G), S1(G),…, Sn−1(G)) be the sequence of spectral moments of G. For two graphs G1, G2, we have G1 ≺SG2 if for some k(k = 1,2,…, n−1), and we have Si(G1) = Si(G2) (i = 0,1, …, k−1) and Sk(G1) < Sk(G2). In this paper, we determine the second to the fourth largest quasi-unicyclic graphs, in an S-order, in the set Q(n, d0), respectively.

Signed graphs are graphs whose edges get signs ±1 and, as for unsigned graphs, they can be studied by means of graph matrices. Here we focus our attention to the largest eigenvalue, also known as the index of the adjacency matrix of signed graphs. Firstly we give some general results on the index variation when the corresponding signed graph is perturbed. Also, we determine signed graphs achieving the minimal or the maximal index in the class of unbalanced unicyclic graphs of order n ≥ 3 .

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.

Given a graph G we are interested in studying the symmetric matrices associated to G with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.

We show that the spectral radius of a graph is an upper bound on the spectral norm of any of its orientations. We also show that equality is attained only when the orientation is sink-source. As an application, we find the extremal values of the spectral norm over the set of oriented trees, oriented unicyclic graphs and connected digraphs with n vertices and n arcs.

Given a uniform probability $\rho$, $0

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

We propose a Nordhaus–Gaddum conjecture for q ( G ) , the minimum number of distinct eigenvalues of a symmetric matrix corresponding to a graph G: for every graph G excluding four exceptions, we conjecture that q ( G ) + q ( G c ) ≤ | G | + 2 , where G c is the complement of G. We compute q ( G c ) for all trees and all graphs G with q ( G ) = | G | − 1 , and hence we verify the conjecture for trees, unicyclic graphs, graphs with q ( G ) ≤ 4 , and for graphs with | G | ≤ 7 .

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 $G$ be a graph on $n$ vertices with $e(G)$ edges. The sum of eigenvalues of graphs has been receiving a lot of attention these years. Let $S_2 (G)$ be the sum of the first two largest signless Laplacian eigenvalues of $G$, and define $f(G) = e (G) +3 - S_2 (G)$. Oliveira et al. (2015) conjectured that $f(G) \geqslant f(U_{n})$ with equality if and only if $G \cong U_n$, where $U_n$ is the $n$-vertex unicyclic graph obtained by attaching $n-3$ pendent vertices to a vertex of a triangle. In this paper, it is proved that $S_2(G) < e(G) + 3 -\frac{2}{n}$ when $G$ is a tree, or a unicyclic graph whose unique cycle is not a triangle. As a consequence, it is deduced that the conjecture proposed by Oliveira et al. is true for trees and unicyclic graphs whose unique cycle is not a triangle.

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

A signed graph Γ is a graph whose edges are labeled by signs. If Γ has n vertices, its spectral radius is the number ϱ(Γ):= max{∣λi(Γ)∣: 1 ⩽ i ⩽ n}, where λ1(Γ) ⩾ … ⩾ λn(Γ) are the eigenvalues of the signed adjacency matrix A(Γ). Here we determine the signed graphs achieving the minimal or the maximal spectral radius in the classes $$\mathfrak{U}{_n}$$ and $$\mathfrak{B}{_n}$$ of unbalanced unicyclic graphs and unbalanced bicyclic graphs, respectively.

Let wG(u) be the sum of distances from u to all the other vertices of G. The Wiener complexity, CW(G), is the number of different values of wG(u) in G, and the eccentric complexity, Cec(G), is the number of different eccentricities in G. In this paper, we prove that for every integer c there are infinitely many graphs G such that CW(G)&minus, Cec(G)=c. Moreover, we prove this statement using graphs with the smallest possible cyclomatic number. That is, if c&ge, 0 we prove this statement using trees, and if c&lt, 0 we prove it using unicyclic graphs. Further, we prove that Cec(G)&le, 2CW(G)&minus, 1 if G is a unicyclic graph. In our proofs we use that the function wG(u) is convex on paths consisting of bridges. This property also promptly implies the already known bound for trees Cec(G)&le, CW(G). Finally, we answer in positive an open question by finding infinitely many graphs G with diameter 3 such that Cec(G)&lt, CW(G).

Let [Formula: see text] be a graph with vertex set [Formula: see text], and let [Formula: see text] denote the length of a shortest [Formula: see text] path in [Formula: see text]. A set [Formula: see text] is called a connected resolving set of [Formula: see text] if, for any distinct [Formula: see text], there exists a vertex [Formula: see text] such that [Formula: see text], and the subgraph of [Formula: see text] induced by [Formula: see text] is connected. The connected metric dimension, [Formula: see text], of [Formula: see text] is the minimum of the cardinalities over all connected resolving sets of [Formula: see text]. For a graph [Formula: see text] and its complement [Formula: see text], each of order [Formula: see text] and connected, we conjecture that [Formula: see text]; if [Formula: see text] is a tree or a unicyclic graph, we prove the conjecture and characterize graphs achieving equality.

The forgotten topological index of a graph [Formula: see text] is defined as the sum of weights [Formula: see text] over all edges [Formula: see text] of [Formula: see text], where [Formula: see text] and [Formula: see text] are the degrees of the vertices [Formula: see text] and [Formula: see text] in [Formula: see text], respectively. In this paper, we characterize the extremal properties of the F-index (forgotten topological index). We first introduce some graph transformations which increase or decrease this index. Furthermore, we will determine the extremal acyclic, unicyclic and bicyclic graphs with minimum and maximum of the F-index by a unified method, respectively. Recently, Akhter et al. [S. Akhter, M. Imran and M. R. Farahani, Extremal unicyclic and bicyclic graphs with respect to the F-index, AKCE Int. J. Graphs Comb. 14 (2017) 80–91] characterized the extremal graph of unicyclic and bicyclic graphs with minimum of the F-index. We will provide a shorter proof.

The Wiener polarity index WP(G) of a graph G is the number of unordered pairs of ver- tices {u,v} such that the distance between u and v is 3. In this paper, we determine the first three smallest Wiener polarity index of u- nicyclic graphs. Moreover, the corresponding extremal graphs are characterized.

The signless Laplacian Q and signless edge-Laplacian S of a given graph may or may not be invertible. The Moore-Penrose inverses of Q and S are studied. In particular, using the incidence matrix, we find combinatorial formulas of the Moore-Penrose inverses of Q and S for trees. Also, we present combinatorial formulas of the inverses of Q and S for odd unicyclic graphs.

We study the problem of exploring all vertices of an undirected weighted graph that is initially unknown to the searcher. An edge of the graph is only revealed when the searcher visits one of its endpoints. Beginning at some start node, the searcher's goal is to visit every vertex of the graph before returning to the start node on a tour as short as possible. We prove that the Nearest Neighbor algorithm's competitive ratio on trees with $n$ vertices is $\Theta(\log n)$, i.e. no better than on general graphs. Furthermore, we examine the algorithm Blocking for a range of parameters not considered previously and prove it is 3-competitive on unicyclic graphs as well as $5/2+\sqrt{2}\approx 3.91$-competitive on cactus graphs. The best known lower bound for these two graph classes is 2., Comment: 10 pages, 5 figures

In this paper, completely regular endomorphisms of unicyclic graphs are explored. Let G be a unicyclic graph and let c E n d ( G ) be the set of all completely regular endomorphisms of G. The necessary and sufficient conditions under which c E n d ( G ) forms a monoid are given. It is shown that c E n d ( G ) forms a submonoid of E n d ( G ) if and only if G is an odd cycle or G = G ( n , m ) for some odd n ≥ 3 and integer m ≥ 1 .

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 .

The revised Szeged index of a connected graph G is defined as $$\begin{aligned} Sz^*(G)=\sum _{e=uv\in E(G)}\left( n_u(e|G)+{\frac{n_0(e|G)}{2}}\right) \left( n_v(e|G)+{\frac{n_0(e|G)}{2}}\right) , \end{aligned}$$where E(G) is the edge set of G, and for any $$e = uv\in E(G)$$, $$n_u(e|G)$$ is the number of vertices of G lying closer to vertex u than to v, $$n_v(e|G)$$ is the number of vertices of G lying closer to vertex v than to u, and $$n_0(e|G)$$ is the number of vertices with equal distances from both end vertices of the edge e. In this paper, we characterize the graph with the minimum revised Szeged index among all the unicyclic graphs with given order and diameter.

A single-cone tree (unicyclic graph) is the join of a complete graph $$K_1$$ and a tree (unicyclic graph). Suppose $$\pi =(d_1, d_2, \ldots , d_n)$$ and $$\pi ^{\,\prime }=(d_1^{\,\prime }, d_2^{\,\prime }, \ldots , d_n^{\,\prime })$$ are two non-increasing degree sequences. We say $$\pi $$ is majorizated by $$\pi ^{\,\prime }$$, denoted by $$\pi \lhd \pi ^{\,\prime }$$, if and only if $$\pi \ne \pi ^{\,\prime }$$, $$\sum \nolimits _{i=1}^{n} d_i=\sum \nolimits _{i=1}^{n} d_i^{\,^{\,\prime }}$$, and $$\sum \nolimits _{i=1}^j d_i\le \sum \nolimits _{i=1}^j d_i^{\,^{\,\prime }}$$ for all $$j=1, 2, \ldots , n-1$$. We use $$J_{\pi }$$ to denote the class of single-cone trees (unicyclic graphs) with degree sequence $$\pi $$. Suppose that $$\pi $$ and $$\pi ^{\,\prime }$$ are two different non-increasing degree sequences of single-cone trees (unicyclic graphs). Let $$\rho $$ and $$\rho ^{\,\prime }$$ be the largest spectral radius of the graphs in $$J_{\pi }$$ and $$J_{\pi ^{\,\prime }}$$, respectively, $$\mu $$ and $$\mu ^{\,\prime }$$ be the largest signless Laplacian spectral radius of the graphs in $$J_{\pi }$$ and $$J_{\pi ^{\,\prime }}$$, respectively. In this paper, we prove that if $$\pi \lhd \pi ^{\,\prime }$$, then $$\rho

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.