Search

Zero forcing and maximum nullity are two important graph parameters which have been laboriously studied in order to aid in the resolution of the Inverse Eigenvalue problem. Motivated in part by an observation that the zero forcing number for the complement of a tree on n vertices is either n − 3 or n − 1 in one exceptional case, we consider the zero forcing number for the complement of more general graphs under certain conditions, particularly those that do not contain complete bipartite subgraphs. We also move well beyond trees and completely study all of the possible zero forcing numbers for the complements of unicyclic graphs and cactus graphs. Finally, we yield equality between the maximum nullity and zero forcing number of several families of graph complements considered. [ABSTRACT FROM AUTHOR]

Mostar indices are recently proposed distance-based graph invariants, that already have been much investigated and found applications. In this paper, we investigate the inverse problem for Mostar indices of unicyclic and bicyclic molecular graphs. We prove that all positive integers other than 1, 2, 3, and 5 can be the Mostar index of some bicyclic molecular graph. In addition, we resolve the inverse edge Mostar index problem for molecular unicyclic and bicyclic graphs, and in doing so, establish the second and third smallest value of the edge Mostar index of unicyclic graphs. [ABSTRACT FROM AUTHOR]

The PI index of a graph G is given by PI(G) = Σe∈E(G) (|V (G)|−NG(e)), where NG(e) is the number of equidistant vertices for the edge e. Various topological indices of bicyclic graphs have already been calculated. In this paper, we obtained the exact value of the PI index of bicyclic graphs. We also explore the extremal graphs among all bicyclic graphs with respect to the PI index. Furthermore, we calculate the PI index of a cactus graph and determine the extremal values of the PI index among cactus graphs. [ABSTRACT FROM AUTHOR]

The multiplicative first Zagreb index is the product of the square of the degree of vertices in a graph G. The multiplicative reformulated first Zagreb index is defined as Π1, e (G) = Πx12x2∈E(G) (dG(x1) +dG(x1) - 2)²,where E(G) is the edge set of a graph G and dG(x1) is the degree of a vertex x1 in a graph G. In this paper, we characterize the minimum and maximum trees and unicyclic graphs with respect to matching and perfect matching using this graph invariant Π1,e(G) among the collection of all n-vertex graphs. [ABSTRACT FROM AUTHOR]

Mostar indices are recently proposed distance-based graph invariants, that already have been much investigated and found applications. In this paper, we investigate the inverse problem for Mostar indices of unicyclic and bicyclic molecular graphs. We prove that all positive integers other than 1, 2, 3, and 5 can be the Mostar index of some bicyclic molecular graph. In addition, we resolve the inverse edge Mostar index problem for molecular unicyclic and bicyclic graphs, and in doing so, establish the second and third smallest value of the edge Mostar index of unicyclic graphs.

Let $G$ be a connected graph and $W=\{w_1, w_2,\ldots,w_k\}$ be an ordered subset of vertices of $G$. For any vertex $v$ of $G$, the ordered $k$-vector $$r(v|W)=(d(v,w_1), d(v,w_2),\ldots,d(v,w_k))$$ is called the metric representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct metric representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension denoted by $\dim(G)$. A resolving set $W$ is called a non-isolated resolving set for $G$ if the induced subgraph $\langle W\rangle$ of $G$ has no isolated vertices. The minimum cardinality of a non-isolated resolving set for $G$ is called the non-isolated resolving number of $G$ and denoted by $nr(G)$. The aim of this paper is to find properties of unicyclic graphs that have non-isolated resolving number $2$ and then to characterize all these graphs.

The total structure connectivity and Narumi-Katayama indices of a simple graph G are defined as ... respectively, where du represents the degree of vertex u in G. In this paper, we determine the extremal values of total structure connectivity index on the class of unicyclic and bicyclic graphs and characterize the corresponding extremal graphs. In addition, we determine the bicyclic graphs extremal with respect to the Narumi-Katayama index. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Baghdad Science Journal is the property of Republic of Iraq Ministry of Higher Education & Scientific Research (MOHESR) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

AbstractFor a connected simple graph G, the inverse degree index and forgotten index are defined as [Formula: see text] and [Formula: see text] respectively, where [Formula: see text] denotes the degree of vertex u in G. In this article, we use some graph transformations and introduce a method for determining the extremal values of inverse degree index and forgotten index on the class of unicyclic graphs.

Let G be a connected graph and W = {w1;w2; . . . ;}kg be an ordered subset of vertices of G. For any vertex v of G, the ordered k-vector r(v|W) = (d(v;w1); d(v;w2); . . .; d(v;wk)) is called the metric representation of v with respect to W, where d(x; y) is the distance between the vertices x and y. A set W is called a resolving set for G if distinct vertices of G have distinct metric representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension denoted by dim(G). A resolving set W is called a non-isolated resolving set for G if the induced subgraph hWi of G has no isolated vertices. The minimum cardinality of a non-isolated resolving set for G is called the non-isolated resolving number of G and denoted by nr(G). The aim of this paper is to find properties of unicyclic graphs that have non-isolated resolving number 2 and then to characterize all these graphs. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) and v i ∈ V , denote by d i the degree of vertex v i . Let f (x , y) > 0 be a real symmetric function in x and y. The weighted adjacency matrix A f (G) of a graph G is a square matrix, where the (i, j)-entry is equal to f (d i , d j) if the vertices v i and v j are adjacent and 0 otherwise. Li and Wang (Linear Algebra Appl 620:61–75, 2021) tried to unify methods to study spectral radius of the weighted adjacency matrices of graphs weighted by various topological indices. If f x ′ (x , y) ≥ 0 and f x ′ ′ (x , y) ≥ 0 , then f (x , y) is said to be increasing and convex in variable x, respectively. They obtained the tree with the largest spectral radius of A f (G) is a star or a double star when f(x, y) is increasing and convex in variable x. If for any x 1 + y 1 = x 2 + y 2 and ∣ x 1 - y 1 ∣ > ∣ x 2 - y 2 ∣ , f (x 1 , y 1) > f (x 2 , y 2) , then f (x , y) is said to have the property P. In this paper, if f (x , y) > 0 is increasing and convex in variable x and for any x 1 + y 1 = x 2 + y 2 and ∣ x 1 - y 1 ∣ > ∣ x 2 - y 2 ∣ , f (x 1 , y 1) ≥ f (x 2 , y 2) , then we say f (x , y) has the property P ∗ and call A f (G) the weighted adjacency matrix with property P ∗ of G. It contains the weighted adjacency matrices weighted by first Zagreb index, first hyper-Zagreb index, general sum-connectivity index, forgotten index, Somber index, p-Sombor index and so on. We obtain the extremal trees with the smallest and largest spectral radii, and the extremal unicyclic graphs with the smallest and first three maximum spectral radii of A f (G) . Our results push ahead Li and Wang's research on unified approaches. [ABSTRACT FROM AUTHOR]

The modified Sombor index of a graph G is defined as the sum of weights 1 / d u 2 + d v 2 over all edges u v of G , where d u and d v are the degrees of the vertices u and v in G , respectively. In this paper, we give a sharp lower bound on the modified Sombor index of unicyclic graphs with given diameter in terms the number of vertices. [ABSTRACT FROM AUTHOR]

For a graph, the SK index is equal to the half of the sum of the degrees of the vertices, the SK1 index is equal to the half of the product of the degrees of the vertices, and the SK2 index is equal to the half of the square of the sum of the degrees of the vertices. This paper shows a simple and unified approach to the greatest SK indices for unicyclic graphs by using some transformations and characterizes these graphs with the first, second, and third SK indices having order r ≥ 5 and girth g ≥ 3, where girth is the length of the shortest cycle in a graph. [ABSTRACT FROM AUTHOR]

In this paper, we consider the spectral radius of signless p-Laplacian of a graph, which is a generalization of the quadratic form of the signless Laplacian matrix for p = 2 . Let π = (d 0 , d 1 , … , d n - 1) be a non-increasing sequence of positive integers and G π the set of graphs with degree sequence π . In this paper, we obtain some transformations for graphs in G π that do not decrease the largest signless p-Laplacian eigenvalue of a graph. Furthermore, if ∑ i = 0 n - 1 d i = 2 n and d 2 ≥ 2 , then we identify the graph maximizing the signless p-Laplacian spectral radius among G π . As an application, we get the extremal graph maximizing the signless p-Laplacian spectral radius among all unicyclic graphs. [ABSTRACT FROM AUTHOR]

The harmonic index H (G) of a graph G is ∑ u v ∈ E (G) 2 d (u) + d (v) , where d (v) is the degree of v ∈ V (G). We show that H (L (T)) > n 4 for any tree T of order n ≥ 3 , which confirm the validity of a conjecture proposed by Zhang and Wu. In addition, the same lower bound holds for a unicyclic graph G of order n. Two relevant conjectures are proposed as well. [ABSTRACT FROM AUTHOR]

An added edge to a graph is called an inset edge. Predicting k inset edges, which minimize the average distance of a graph, is known to be NP-Hard. However, when k = 1 , the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the effect of inset edges on the tree's average distance are established. Using the tools, one can avoid using the distance matrix for better performance of algorithms. Here, some applications of the tools and a tight bound for the change of average distance when an inset edge is added to a tree are presented. [ABSTRACT FROM AUTHOR]

The Randić index R(G) of a graph G is the sum of the weights (dudv)1/2 of all edges uv in G, where du denotes the degree of vertex u. Du and Zhou [On Randić indices of trees, unicyclic graphs, and bicyclic graphs, Int. J. Quantum Chem. 111 (2011), 2760-2770] determined the n-vertex unicyclic graphs with the third maximum for n ≥ 5, the fourth maximum for n ≥ 7 and the fifth maximum for n ≥ 8. Recently, Li et al. [The Randić indices of trees, unicyclic graphs and bicyclic graphs, Ars Comb. 127 (2016), 409-419] obtained the n-vertex unicyclic graphs with the sixth maximum and the seventh maximum for n ≥ 9 and the eighth maximum for n ≥ 10. In this paper, we characterize the n-vertex unicyclic graphs with the ninth maximum, the tenth maximum, the eleventh maximum, the twelfth maximum and the thirteenth maximum of Randić values. [ABSTRACT FROM AUTHOR]

Topological indices are widely used as mathematical tools to analyze different types of graphs emerged in a broad range of applications. The Hyper-Zagreb index (HM) is an important tool because it integrates the first two Zagreb indices. In this paper, we characterize the trees and unicyclic graphs with the first four and first eight greatest HM-value, respectively. [ABSTRACT FROM AUTHOR]

We use Rosa-type labelings to decompose complete graphs into unicyclic, disconnected, bipartite graphs on nine edges - namely, those featuring cyclic component C4, C6, or C8. For any such graph H, we prove there exists an H-design of K18k+1 and K18k for all positive integers k. [ABSTRACT FROM AUTHOR]

The graph in this paper is a simple and connected graph with V(G) is vertex set and E(G) is edge set. An inklusif local irregularity vertex coloring is defined should be maping l:V(G) í {1,2,..., k} as vertex labeling and wi : V(G) í N is function of inclusive local irregularity vertex coloring, with wi(v) = l(v) + ∑u∈N(v) l(u) in other words, an inclusive local irregularity vertex coloring is to assign a color to the graph with the resulting weight value by adding up the labels of the vertices that are should be neighboring to its own label. The minimum number of colors produced from inclusive local irregularity vertex coloring of graph G is called inclusive chromatic number local irregularity, denoted by Xlisi(G). Should be in this paper, we learn about the inclusive local irregularity vertex coloring and determine the chromatic number on unicyclic graphs.

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 $ \overline{\xi}^{c}(G) = \sum\limits_{uv\notin E(G)} (\varepsilon_{G}(u)+\varepsilon_{G}(v)). $ 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.

Denote by G(n, c, g, k) the set of all connected graphs of order n, having c cycles, girth g, and k pendant vertices. In this paper, we give a partial characterisation of the structure of those graphs in G(n, c, g, k) maximising the number of connected induced subgraphs. For the special case where c = 1, we find a complete characterisation of all maximal unicyclic graphs. We also derive a precise formula for the corresponding maximum number given the following parameters: (1) order, girth, and number of pendant vertices; (2) order and girth; (3) order. [ABSTRACT FROM AUTHOR]

Let U be a non-singular unicyclic graph. We show that the inverse of the adjacency matrix of U has a combinatorial description in terms of maximum matchings of U. [ABSTRACT FROM AUTHOR]

Let T be a tree on n (≥ 7) vertices with λ as a positive eigenvalue of multiplicity k. If λ 2 ≥ 2 is an integer, then we prove that k ≤ ⌊ n − 4 3 ⌋ and all extremal graphs attaining the upper bound are characterized. This result revises and improves the main conclusion of Wong, Zhou and Tian (2020). Moreover, applying this result we investigate the eigenvalue multiplicity of unicyclic graphs. Let G be a unicyclic graph of order n (≥ 11) , which contains λ (λ 2 ≥ 2 is an integer) as a positive eigenvalue of multiplicity m. Then it is proved that m ≤ ⌊ n − 2 3 ⌋ , and all extremal graphs attaining the upper bound are determined. These two upper bounds improve the conclusions of Rowlinson (2010, 2011), respectively. [ABSTRACT FROM AUTHOR]

The article focuses on Chen and Li who characterized the sum-connectivity index of unicyclic graphs with k pendent vertices. Topics include examines to characterize the minimum sum-connectivity indices of trees and unicyclic graphs of a given matching number and characterize the minimum general sum-connectivity index of unicyclic graphs and Xing et al. obtained lower and upper bounds for the sum-connectivity index of molecular trees with fixed number of vertices and pendant vertices.

Given a simple connected graph G, the metric dimension dim (G) (and edge metric dimension edim (G) ) is defined as the cardinality of a smallest vertex subset S ⊆ V (G) for which every two distinct vertices (and edges) in G have distinct distances to a vertex of S. It is an interesting topic to discuss the relation between these two dimensions for some class of graphs. This paper settles two open problems on this topic for unicyclic graphs. We recently learned that Sedlar and Škrekovski settled these problems, but our work presents the results in a completely different way. By introducing four classes of subgraphs, we characterize the structure of a unicyclic graph G such that dim (G) and edim (G) are equal to the cardinality of any minimum branch-resolving set for unicyclic graphs. This generates an approach to determine the exact value of the metric dimension (and edge metric dimension) for a unicyclic graph. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) with maximum degree Δ , let f : V ⟶ { 0 , 1 , ... , ⌈ Δ 2 ⌉ + 1 } be a function and let B i = { v ∈ V : f (v) = i } for each i ∈ { 0 , 1 } and B 2 = { v ∈ V : f (v) ≥ 2 } = V - (B 0 ∪ B 1) . The function f is a strong Roman dominating function (StRDF) on G if every vertex v ∈ V with f (v) = 0 is adjacent to a vertex u with f (u) ≥ ⌈ 1 2 | N G (u) ∩ B 0 | ⌉ + 1 . The weight of f is the sum f (V) = ∑ v ∈ V f (v) . The minimum weight of a StRDF on G is the strong Roman domination number of G. In this paper, we give a linear algorithm that computes the strong Roman domination number of trees, answering a problem which was posed in 2017. Then, we give a linear algorithm to compute the strong Roman domination number of unicyclic graphs. [ABSTRACT FROM AUTHOR]

Given a connected graph G , its Lanzhou index is L z (G) = ∑ v ∈ V (G) d (v) 2 [ n − 1 − d (v) ] , where n is the order and d (v) is the degree of v ∈ G. As usual with topological indices and their meaning in Chemical Graph Theory, we are interested in determining the graphs maximizing or minimizing the considered index. We show that by applying the majorization method, we identify all unified extremal trees with maximum Lanzhou index among the trees of order n and diameter d ≥ 8. Using the same method, we identify the unified extremal unicyclic graphs with maximum Lanzhou index among the unicyclic graphs of order n and diameter d ≥ 9 with n ≥ 3 d − 8. [ABSTRACT FROM AUTHOR]

For a vertex x of a connected graph G = (V G , E G) , the weighted reverse cover cost of x is proposed as R C π G (x) = ∑ y ∈ V G d (y) H y x , where d (y) denotes the degree of y and H y x denotes the hitting time for random walk starting at y to visit x. In this paper, we first obtain the sharp lower bound of R C π G (x) among all trees with order n and given diameter, and then determine the sharp upper bound of R C π G (x) among all unicyclic graphs with order n and given diameter. Furthermore, all the corresponding extremal graphs are identified. • Present the sharp lower bound of weighted reverse cover cost among all trees of order n and diameter d. • Present the sharp upper bound of weighted reverse cover cost among all unicyclic graphs of order n and diameter d. • Characterize the corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

For a graph, the SK index is equal to the half of the sum of the degrees of the vertices, the SK1 index is equal to the half of the product of the degrees of the vertices, and the SK2 index is equal to the half of the square of the sum of the degrees of the vertices. This paper shows a simple and unified approach to the greatest SK indices for unicyclic graphs by using some transformations and characterizes these graphs with the first, second, and third SK indices having order r ≥ 5 and girth g ≥ 3, where girth is the length of the shortest cycle in a graph.

The vertex (resp. edge) metric dimension of a connected graph G is the size of a smallest set S ⊆ V (G) which distinguishes all pairs of vertices (resp. edges) in G. In Sedlar and Škrekovski (2021) 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. [ABSTRACT FROM AUTHOR]

An electrical network is often modeled as a graph where every edge of the graph is assumed to be a resistor. The Kirchhoff index Kf(G) of a simple connected graph G is the sum of the resistances between every pair of vertices in G. In this paper, we determine the minimum Kirchhoff index among the unicyclic graphs with given girth and diameter. [ABSTRACT FROM AUTHOR]

The exponential second Zagreb index of a connected graph G , denoted by e M 2 (G) , is defined as the sum of the weights e d G (u) d G (v) over all edges u v ∈ E (G) , where d G (u) denotes the degree of vertex u. The maximum value of e M 2 in the class of connected acyclic graphs has already been studied. In this paper, maximal unicyclic and bicyclic graphs of order n with respect to e M 2 are represented. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Miličević et al., in 2004, introduced topological indices known as Reformulated Zagreb indices, where they modified Zagreb indices using the edge-degree instead of vertex degree. In this paper, we present a simple approach to find the upper and lower bounds of the second reformulated Zagreb index, EM2(G), by using six graph operations/transformations. We prove that these operations significantly alter the value of reformulated Zagreb index. We apply these transformations and identify those graphs with cyclomatic number at most 3, namely trees, unicyclic, bicyclic and tricyclic graphs, which attain the upper and lower bounds of second reformulated Zagreb index for graphs. [ABSTRACT FROM AUTHOR]

The graph in this paper is a simple and connected graph with V (G) is vertex set and E(G) is edge set. An inklusif local irregularity vertex coloring is defined should be maping l:V (G){1, 2, ..., k} as vertex labeling and: ( ) i w V G N > is function of inclusive local irregularity vertex coloring, with i w v = l v + (u)N v l u. in other words, an inclusive local irregularity vertex coloring is to assign a color to the graph with the resulting weight value by adding up the labels of the vertices that are should be neighboring to its own label. The minimum number of colors produced from inclusive local irregularity vertex coloring of graph G is called inclusive chromatic number local irregularity, denoted by () i lis (G). Should be in this paper, we learn about the inclusive local irregularity vertex coloring and determine the chromatic number on unicyclic graphs. [ABSTRACT FROM AUTHOR]

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.

A tadpole (also a canoe paddle or lollipop) is a graph that arises from a cycle and a path by gluing a terminal vertex of the path to an arbitrary vertex of the cycle. In this article, we show that all tadpoles factorize the complete graph if n is odd. We use methods similar to those used for isomorphic factorizations of complete graphs into spanning trees. In of this article, we show that our methods do not work for isomorphic factorizations of into tadpoles if n is even.

The distance Laplacian spectral radius of a connected graph G is the largest eigenvalue of its distance Laplacian matrix L(G) defined as L(G) = Tr(G) - D(G), where Tr(G) is the diagonal matrix of vertex transmissions and D(G) is the distance matrix of G. We determine the unique trees with maximum distance Laplacian spectral radius among trees of perfect matchingwith givenmaximumdegree, the unique treeswith second (third, respectively) maximum distance Laplacian spectral radius, and the unique bipartite unicyclic graphs with maximum distance Laplacian spectral radius. We also determine the unique graphswithminimum distance Laplacian spectral radius among bicyclic graphs. [ABSTRACT FROM AUTHOR]

We examine the problem of gathering k ≥ 2 agents (or multi-agent rendezvous) in dynamic graphs which may change in every round. We consider a variant of the 1 -interval connectivity model [9] in which all instances (snapshots) are always connected spanning subgraphs of an underlying graph, not necessarily a clique. The agents are identical and not equipped with explicit communication capabilities, and are initially arbitrarily positioned on the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the underlying graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering, where the agents are allowed to gather either at the same node, or at two adjacent nodes. Our goal is to characterize the class of 1-interval connected graphs and initial configurations in which the problem is solvable, both with and without homebases. On the negative side we show that when the underlying graph contains a spanning bicyclic subgraph and satisfies an additional connectivity property, weak gathering is unsolvable, thus we concentrate mainly on unicyclic graphs. As we show, in most instances of initial agent configurations, the agents must meet on the cycle. This adds an additional difficulty to the problem, as they need to explore the graph and recognize the nodes that form the cycle. We provide a deterministic algorithm for the solvable cases of this problem that runs in O (n 2 + n k) number of rounds. [ABSTRACT FROM AUTHOR]

A graph G(p, q) is said to have an edge-magic total labeling if there exists a bijective function f: V(G) ∪ E(G) → {1, 2, ...,p + q}, such that for any edge uv∊E(G) the condition f(u)+f(v)+f(uv)=k is satisfied, k is a constant. In this paper, a new algorithm, based on the graph generate algorithm, is designed to obtain the edge-magic total labeling of the unicyclic graphs. Some theorems about unicyclic graphs are also deduced from the algorithm's results. It's believed that the algorithm proposed is innovative and can be adopted by other researchers. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V (G) , and let d (u , w) denote the length of a shortest u − w path in G. A set S ⊆ V (G) is called a connected resolving set of G if, for any distinct x , y ∈ V (G) , there exists a vertex z ∈ S such that d (x , z) ≠ d (y , z) , and the subgraph of G induced by S is connected. The connected metric dimension, cdim (G) , of G is the minimum of the cardinalities over all connected resolving sets of G. For a graph G and its complement G ¯ , each of order n ≥ 4 and connected, we conjecture that cdim (G) + cdim (G ¯) ≤ 2 n − 5 ; if G is a tree or a unicyclic graph, we prove the conjecture and characterize graphs achieving equality. [ABSTRACT FROM AUTHOR]

The forgotten topological index of a graph is defined as the sum of weights d u 2 + d v 2 over all edges u v of , where d u and d v are the degrees of the vertices u and v in , 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. [ABSTRACT FROM AUTHOR]

The max–min rodeg ( M m sde ) index is a useful topological index in mathematical chemistry. Damir Vuki c ˇ evi 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 ≥ 7 , and the fifth for n ≥ 10 minimum M m sde indices, unicyclic graphs with the second and the third for n ≥ 5 , the fourth, the fifth and the sixth for n ≥ 7 , and the seventh for n ≥ 9 minimum M m sde indices, and bicyclic graphs with the first for n ≥ 4 , the second and the third for n ≥ 6 , and the fourth for n ≥ 8 minimum M m sde indices. [ABSTRACT FROM AUTHOR]

A topological index being a graph theoretic parameter plays a role of function for the assignment of a numerical value to a molecular graph which predicts the several physical and chemical properties of the underlying molecular graph such as heat of evaporation, critical temperature, surface tension, boiling point, octanol-water partition coefficient, density and flash points. For a (molecular) graph Γ, the Lanzhou index (Lz index) is obtained by the sum of deg(v)2de¯g(v) over all the vertices, where deg(v) and de¯g(v) are degrees of the vertex v in Γ and its complement Γ¯ respectively. Let Vαβ be a class of unicyclic graphs (same order and size) such that each graph of this class has order α and β leaves (vertices of degree one). In this note, we compute the lower and upper bounds of Lz index for each unicyclic graph in the class of graphs Vαβ. Moreover, we characterize the extremal graphs with respect to Lz index in the same class of graphs.

In a connected 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 unicyclic graph G which is derived from the structure of G. We further consider graphs G with edge disjoint cycles, where for each cycle C i of G we define a unicyclic subgraph G i of G in which C i is the only cycle. Applying the result for unicyclic graph to the subgraph G i of every cycle C i 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. [ABSTRACT FROM AUTHOR]

A set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G , denoted by ι (G) , is the minimum cardinality of an isolating set of G. It is known that ι (G) ≤ n / 3 , if G is a connected graph of order n , n ≥ 3 , distinct from C 5. The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number equal to n / 3. Moreover, we provide a family of general graphs attaining this upper bound on the isolation number. [ABSTRACT FROM AUTHOR]

Given a simple connected graph G, the metric dimension dim(G) (and edge metric dimension edim(G)) is defined as the cardinality of a smallest vertex subset S⊆V(G) for which every two distinct vertices (and edges) in G have distinct distances to a vertex of S. It is an interesting topic to discuss the relation between these two dimensions for some class of graphs. This paper settles two open problems on this topic for unicyclic graphs. We recently learned that Sedlar and Škrekovski settled these problems, but our work presents the results in a completely different way. By introducing four classes of subgraphs, we characterize the structure of a unicyclic graph G such that dim(G) and edim(G) are equal to the cardinality of any minimum branch-resolving set for unicyclic graphs. This generates an approach to determine the exact value of the metric dimension (and edge metric dimension) for a unicyclic graph.