Narrow Results

The edge version of the Nirmala index is defined in terms of edge degrees as $\mathrm{\text{EN}}(G)={\sum }_{e\sim f}\sqrt{d(e)+d(f)}$, where $d(x)$ denotes the degree of the edge $x$ in graph $G$ and $e\sim f$ means that the edges $e$ and $f$ are adjacent. In this paper, we obtain some sharp bounds for the edge version of the Nirmala index in terms of the edge version of topological indices. Also, we give the extremal unicyclic graphs of order $n$ with the minimum edge version of the Nirmala index.

In this paper, we propose a family of unicyclic graphs to study robustness of network coherence quantified by the Laplacian spectrum, which measures the extent of consensus under the noise. We adjust the network parameters to change the structural asymmetries with an aim of studying their effects on the coherence. Using the graph’s structures and matrix theories, we obtain closed-form solutions of the network coherence regarding network parameters and network size. We further show that the coherence of the asymmetric graph is higher than the corresponding symmetric graph and also compare the consensus behaviors for the graphs with different asymmetric structures. It displays that the coherence of the unicyclic graph with one hub is better than the graph with two hubs. Finally, we investigate the effect of degree of hub nodes on the coherence and find that bigger difference of degrees leads to better coherence.

In this paper, we consider the problem of finding the minimum number of searchers to sweep networks/graphs with special topological structures. Such a number is called the search number. We first study graphs, which contain only one cycle, and present a linear time algorithm to compute the vertex separation and the optimal layout of such graphs; by a linear-time transformation, we can find the search number of this kind of graphs in linear time. We also investigate graphs, in which every vertex lies on at most one cycle and each cycle contains at most three vertices of degree more than two, and we propose a linear time algorithm to compute their search number and optimal search strategy. We prove explicit formulas for the search number of the graphs obtained from complete k-ary trees by replacing vertices by cycles. We also present some results on approximation algorithms.

The distance spectral radius of a connected graph is the largest eigenvalue of its distance matrix. For integers $n$ and $\mathrm{\Delta }$ with $3\le \mathrm{\Delta }\le n-2$, we prove that among the connected graphs on $n$ vertices of given maximum degree $\mathrm{\Delta }$ with at least one cycle, the graph $U(n,\mathrm{\Delta })$ uniquely maximizes the distance spectral radius, where $U(n,\mathrm{\Delta })$ is the graph obtained from the disjoint star on $\mathrm{\Delta }$ vertices and path on $n-\mathrm{\Delta }$ vertices by adding two edges, one connecting the star center with a path end, and the other being a chord of the star.

We introduce the concept of minimum edge cover for an induced subgraph in a graph. Let $G$ be a unicyclic graph with a unique odd cycle and $I=I(G)$ be its edge ideal. We compute the exact values of all symbolic defects of $I$ using the concept of minimum edge cover for an induced subgraph in a graph. We describe one method to find the quasi-polynomial associated with the symbolic defects of edge ideal $I$. We classify the class of unicyclic graphs when some power of maximal ideal annihilates $I^{(s)}/I^s$ for any fixed $s$. Also for those class of graphs, we compute the Hilbert function of the module $I^{(s)}/I^s$ for all $s.$

We characterize all connected graphs with exactly three distinct normalized Laplacian eigenvalues among which one is equal to 1, and determine all connected bipartite graphs with at least one vertex of degree 1 having exactly four distinct normalized Laplacian eigenvalues. In addition, we find all unicyclic graphs with three or four distinct normalized Laplacian eigenvalues.

Let $U_n^g$ be the set of connected unicyclic graphs of order $n$ and girth $g$. Let $C(T_1,T_2,\dots ,T_g)\in U_n^g$ be obtained from a cycle $v_1{v}_2\cdots v_g{v}_1$ (in an anticlockwise direction) by identifying $V_i$ with the root of a rooted tree $T_i$ of order $n_i$ for each $i=1,2,\dots ,g$, where $n_i\ge 1$ and $\sum _{i=1}^g{n}_i=n$. In this note, the graph with the minimal least eigenvalue (and the graph with maximal spread) in $C(T_1,T_2,\dots ,T_g)$ is determined.

The harmonic index of a graph $G$, denoted by $H(G)$, is defined as the sum of weights $2/[d(u)+d(v)]$ over all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex $u$. Hu and Zhou [WSEAS Trans. Math.12 (2013) 716–726] proved that for any unicyclic graph $G$ of order $n\ge 3$, $H(G)\le \frac{n}{2}$ with equality if and only if $G=C_n$. Recently, Zhong and Cui [Filomat29 (2015) 673–686] generalized the above bound and proved that for any unicyclic graph $G$ of order $n\ge 4$ other than $C_n$, $H(G)\le \frac{n}{2}-\frac{2}{15}$. In this paper, we generalize the aforemention results and show that for any connected unicyclic graph $G$ of order $n\ge 3$ with maximum degree $\mathrm{\Delta }$,

The forgotten topological index of a graph $G$, denoted by $F(G)$, is defined as the sum of weights $d{(u)}^2+d{(v)}^2$ over all edges $uv$ of $G$, where $d(u)$ denotes the degree of the vertex $u$. In this paper, we establish upper bounds on the forgotten topological index of trees, unicyclic graphs and bicyclic graphs with a given domination number.

The forgotten topological index ($F$-index) of a graph $G$, denoted by $F(G)$, is defined as the sum of cubes of the degrees of all the vertices in a graph. A connected graph with equal order and size is called unicyclic graph, where order is number of vertices and size is number of edges. In this paper, we investigate the new sharp upper bounds on $F$-index in terms of the order and maximum degree.

We study the general Randić index of a graph $G$, $R_a(G)={\sum }_{uv\in E(G)}{[d_G(u)d_G(v)]}^a$, where $a\in ℝ$, $E(G)$ is the edge set of $G$ and $d_G(u)$ and $d_G(v)$ are the degrees of vertices $u$ and $v$, respectively. For $-1\le a<0$, we present lower bounds on the general Randić index for unicyclic graphs of given diameter and girth, and unicyclic graphs of given diameter. Lower bounds on the classical Randić index and the second modified Zagreb index are corollaries of our results on the general Randić index.

In this paper, we determine the two graphs in the class of unicyclic bipartite graphs with n vertices, having the first two largest spectral radius.

Let be the set of unicyclic graphs with n vertices and k cut vertices. In this paper, we determine the unique graph with the maximal spectral radius among all graphs in for 1 ≤ k ≤ n - 3.

The zero forcing number, Z(G), of a graph G is the minimum cardinality of a set S of black vertices (whereas vertices in V(G)\S are colored white) such that V(G) is turned black after finitely many applications of "the color-change rule": a white vertex is converted to a black vertex if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the "AIM Minimum Rank-Special Graphs Work Group". It is known that Z(G) ≥ δ(G), where δ(G) is the minimum degree of G. We show that Z(G) ≤ n - 3 if a connected graph G of order n has a connected complement graph . Further, we characterize a tree or a unicyclic graph G which satisfies either or .

Let $G$ be a graph with vertex set $V(G)$. The domination number, $\gamma (G)$, of $G$ is the minimum cardinality of a set $S\subseteq V(G)$ such that every vertex not in $S$ is adjacent to a vertex in $S$. The metric dimension, $dim(G)$, of $G$ is the minimum cardinality of a set of vertices such that every vertex of $G$ is uniquely determined by its vector of distances to the chosen vertices. For a tree $T$ of order at least two, we show that $\gamma (T)+dim(T)\le |V(T)|-\mathrm{\text{ex}}(T)$, where $\mathrm{\text{ex}}(T)$ denotes the number of exterior major vertices of $T$; further, we characterize trees $T$ achieving equality. For a connected graph $G$ of order $n\ge 2$, Bagheri Gh. et al. proved that $\gamma (G)+dim(G)\le n$ and equality holds if and only if $G\in \{K_n,K_{s,n-s}\}$ for $s\ge 2$ and $n-s\ge 2$, where $K_n$ denotes the complete graph and $K_{s,n-s}$ denotes a complete bi-partite graph of order $n$. We characterize graphs $G$ for which $\gamma (G)+dim(G)$ equals two and three, respectively. We also characterize graphs $G$ satisfying $\gamma (G)+dim(G)=|V(G)|-1$ when $G$ is a tree, a unicyclic graph, or a complete multi-partite graph.

Let ${\lambda }_2(G)$ be the second smallest normalized Laplacian eigenvalue of a graph $G$, called the normalized algebraic connectivity of $G$. In this paper, we study the relation between the normalized algebraic connectivity of the coalescence of two graphs and that of these two graphs. Furthermore, we investigate how the normalized algebraic connectivity behaves when the graph is perturbed by relocating pendent edges.

Let $G$ be a connected graph of order at least two with vertex set $V(G)$. For $x,y\in V(G)$, let $d(x,y)$ denote the length of an $x-y$ geodesic in $G$. A function $f:V(G)\to {\mathbb{Z}}^{+}\cup \{0\}$ is called a dominating broadcast function of $G$ if, for each vertex $x\in V(G)$, there exists a vertex $y\in V(G)$ such that $f(y)>0$ and $d(x,y)\le f(y)$, and the broadcast domination number, ${\gamma }_b(G)$, of $G$ is the minimum of ${\sum }_{z\in V(G)}f(z)$ over all dominating broadcast functions $f$ of $G$. For $u,v\in V(G)$, let $S\{u,v\}$ denote the set of vertices $w\in V(G)$ such that either $u$ lies on a $v-w$ geodesic or $v$ lies on a $u-w$ geodesic of $G$. Let $g:V(G)\to \{0,1\}$ be a function and, for any $U\subseteq V(G)$, let $g(U)={\sum }_{\alpha \in U}g(\alpha )$. We say that $g$ is a strong resolving function of $G$ if $g(S\{u,v\})\ge 1$ for every pair of distinct vertices $u,v\in V(G)$, and the strong metric dimension, $\text{sdim}(G)$, of $G$ is the minimum of ${\sum }_{z\in V(G)}g(z)$ over all strong resolving functions $g$ of $G$. For any connected graph $G$, we show that $2\le {\gamma }_b(G)+\text{sdim}(G)\le |V(G)|$; we characterize $G$ satisfying ${\gamma }_b(G)+\text{sdim}(G)$ equals two and three, respectively, and characterize unicyclic graphs achieving ${\gamma }_b(G)+\text{sdim}(G)=|V(G)|$. For any tree $T$ of order at least three, we show that ${\gamma }_b(T)+\text{sdim}(T)\le |V(T)|-1$, and characterize trees achieving equality. Moreover, for a tree $T$ of order $n\ge 2$, we obtain the results that ${\gamma }_b(T)+\text{sdim}(T)\le n-\text{rad}(T)$ if $T$ is central, and that ${\gamma }_b(T)+\text{sdim}(T)\le n-\text{rad}(T)+1$ if $T$ is bicentral; in each case, we characterize trees achieving equality. We conclude this paper with some remarks and an open problem.

Let ${\mathcal{𝒰}}_{n,g+}^{-}$ be the set of all unbalanced unicyclic graphs of order $n$ and girth at least $g$. In this paper, we determine the signed graph whose largest eigenvalue is maximal among all graphs in ${\mathcal{𝒰}}_{n,g+}^{-}$.

The Wiener index of a connected graph is the sum of the distance of all pairs of distinct vertices. It was introduced by Wiener in 1947 to analyze some aspects of branching by fitting experimental data for several properties of alkane compounds. Denote by ${{𝒰}}_{n,r}$ the set of unicyclic graphs with $n$ vertices and $r$ vertices of even degree. In this paper, we present a structural result on the graphs in ${{𝒰}}_{n,r}$ with minimum Wiener index and completely characterize such graphs when $r\le \frac{n+3}{2}$.

Topological indices of graphs have been studied due to their extensive applications in chemistry. We obtain lower bounds on the general sum-connectivity index ${\chi }_a(G)$ for unicyclic graphs $G$ of given girth and diameter, and for unicyclic graphs of given diameter, where $-1\le a<0$. We present the extremal graphs for all the bounds. Our results generalize previously known results on the harmonic index for unicyclic graphs of given diameter.