Kyungpook Mathematical Journal (12256951)63(1)pp. 123-129
For an ordered set W = {w1,w2,…,wk} of vertices and a vertex v in a connected graph G, the k-vector (Formula Presented) 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 dim(G), and a resolving set of minimum cardinality is a basis of G. The corona product, (Formula Presented) of graphs G and H is obtained by taking one copy of G and n(G) copies of H, and by joining each vertex of the ith copy of H to the ith vertex of G. In this paper, we obtain bounds for dim(Formula Presented), characterize all graphs G with dim(Formula Presented), and prove that dim(Formula Presented) if and only if G is the complete graph Kn or the star graph K1,n−1. © Kyungpook Mathematical Journal
Discrete Mathematics, Algorithms and Applications (17938317)14(4)
For a set W of vertices and a vertex v in a graph G, the k-vector r2(v|W) = (aG(v,w1),⋯,aG(v,wk)) is the adjacency representation of v with respect to W, where W = {w1,⋯,wk} and aG(x,y) is the minimum of 2 and the distance between the vertices x and y. The set W is an adjacency resolving set for G if distinct vertices of G have distinct adjacency representations with respect to W. The minimum cardinality of an adjacency resolving set for G is its adjacency dimension. It is clear that the adjacency dimension of an n-vertex graph G is between 1 and n - 1. The graphs with adjacency dimension 1 and n - 1 are known. All graphs with adjacency dimension 2, and all n-vertex graphs with adjacency dimension n - 2 are studied in this paper. In terms of the diameter and order of G, a sharp upper bound is found for adjacency dimension of G. Also, a sharp lower bound for adjacency dimension of G is obtained in terms of order of G. Using these two bounds, all graphs with adjacency dimension 2, and all n-vertex graphs with adjacency dimension n - 2 are characterized. © 2022 World Scientific Publishing Company.
Bulletin Of The Malaysian Mathematical Sciences Society (01266705)45(5)pp. 2041-2052
Two vertices u, v in a connected graph G are doubly resolved by vertices x, y of G if d(v,x)-d(u,x)≠d(v,y)-d(u,y).A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W. Doubly resolving number of a graph G, denoted by ψ(G) , is the minimum cardinality of a doubly resolving set for the graph G. The aim of this paper is to investigate doubly resolving sets in graphs. An upper bound for ψ(G) is obtained in terms of order and diameter of G. ψ(G) is computed for some graphs, and all graphs G of order n with the property ψ(G) = n- 1 are determined. Also, doubly resolving sets for unicyclic graphs are studied and it is proved that the difference between the number of leaves and doubly resolving number of a unicyclic graph is at most 2. © 2022, This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply.
Discrete Mathematics, Algorithms and Applications (17938317)9(2)
A set W ∪ V (G) is called a resolving set, if for each pair of distinct vertices u,v ϵ V (G) there exists t ϵ W such that d(u,t)=d(v,t), where d(x,y) is the distance between vertices x and y. The cardinality of a minimum resolving set for G is called the metric dimension of G and is denoted by dimM(G). A k-tree is a chordal graph all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k. A k-path is a k-tree with maximum degree 2k, where for each integer j, k ≤ j < 2k, there exists a unique pair of vertices, u and v, such that deg(u) =deg(v) = j. In this paper, we prove that if G is a k-path, then dimM(G) = k. Moreover, we provide a characterization of all 2-trees with metric dimension two. © 2017 World Scientific Publishing Company.
Ars Combinatoria (03817032)127pp. 357-372
For an ordered set W = {ω1, ω1,···, ωk} of vertices and a vertex v in a connected graph G, the ordered fc-vector r(ν|W):= (d(ν, ω1), d(ν, ω1),···, d{ν, ω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. The set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W. a minimum resolving set for G is a basis of G and its cardinality is the metric dimension of G. The resolving number of a connected graph G is the minimum k, such that every fc-set of vertices of G is a resolving set. a connected graph G is called randomly k-dimensional if each k-set of vertices of G is a basis. In this paper, along with some properties of randomly k-dimensional graphs, we prove that a connected graph G with at least two vertices is randomly fc-dimensional if and only if G is complete graph Kk+1 or an odd cycle.
Ars Combinatoria (03817032)129pp. 249-259
A set W C V(G) is called a resolving set, if for each two distinct vertices u v € V(G) there exists w € W such that d(uw) d(v,w), where d(x,y) is the distance between the vertices x and y. A resolving set for G with minimum cardinality is called a metric basis. A graph with a unique metric basis is called a unique basis graph. In this paper, we study some properties of unique basis graphs.
Bulletin Of The Iranian Mathematical Society (10186301)41(3)pp. 633-638
A set W ⊆ V (G) is called a resolving set for G, if for each two distinct vertices u, v ∈ V (G) there exists w 2 W such that d(u,w) ≠ d(v,w), where d(x, y) is the distance between the vertices x and y. The minimum cardinality of a resolving set for G is called the metric dimension of G, and denoted by dim(G). In this paper, it is proved that in a connected graph G of order n which has a cycle, dim(G) ≤ n-g(G)+2, where g(G) is the length of the shortest cycle in G, and the equality holds if and only if G is a cycle, a complete graph or a complete bipartite graph Ks,t, s, t ≥ 2. © 2015 Iranian Mathematical Society.
Mathematica Bohemica (24647136)139(1)pp. 1-23
For an ordered set W = {w1, w2,..., wk} of vertices and a vertex v in a connected graph G, the ordered k-vector r(v{pipe}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 vertices x and y. A set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension. In this paper, we characterize all graphs of order n with metric dimension n - 3.
Discrete Mathematics (0012365X)312(22)pp. 3349-3356
For a set W of vertices and a vertex v in a connected graph G, the k-vector rW(v)=(d(v,w1),⋯,d(v,wk)) is the metric representation of v with respect to W, where W=w1,⋯,wk and d(x,y) is the distance between the vertices x and y. The set W is 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. In this paper, we study the metric dimension of the lexicographic product of graphs G and H, denoted by G[H]. First, we introduce a new parameter, the adjacency dimension, of a graph. Then we obtain the metric dimension of G[H] in terms of the order of G and the adjacency dimension of H. © 2012 Elsevier B.V. All rights reserved.
Match (03406253)65(1)pp. 71-78
The Wiener index of a simple graph is defined as the sum of distances between all vertices of the graph. It is well known that the Wiener index of a tree can be obtained as an edge additive quantity where edge contributions are given as the product of the number of vertices closer to each of the two end points of each edge. Thus the distances between vertices are not used for computing the Wiener index of trees. In a similar manner we introduce new topological indices which yields the Wiener, hyper-Wiener, Schultz and modified Schultz indices as special cases for trees. One advantage of this method is that in computing Schultz and modified Schultz of trees we need not take in to account the distances between vertices.
Applied Mathematics Letters (18735452)24(10)pp. 1625-1629
For an ordered set W=w1,w2,⋯,wk of vertices and a vertex v in a connected graph 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. The set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G with minimum cardinality is called a basis of G and its cardinality is the metric dimension of G. A connected graph G is called a randomly k-dimensional graph if each k-set of vertices of G is a basis of G. In this work, we study randomly k-dimensional graphs and provide some properties of these graphs. © 2011 Elsevier Ltd. All rights reserved.
Match (03406253)65(1)pp. 27-32
Gutman and Zhou (Relations between Wiener, hyper-Wiener and Zagreb indices, Chemical Physics Letters 394 (2004) 93-95) obtained some bounds on Wiener and hyper-Wiener indices, in term of the first Zagreb index in molecular graphs with girth greater than four. We obtain new inequalities for Wiener and hyperWiener indices, in terms of the first and the second Zagreb indices and the number of hexagons in these graphs. These inequalities improve the bounds obtained by Gutman and Zhou and are the best possible bounds. Using these relations we obtain a bound on the second Zagreb index in terms of the first Zagreb index, for hexagon-free graphs.
Discrete Applied Mathematics (0166218X)158(3)pp. 219-221
A block graph is a graph whose blocks are cliques. For each edge e = u v of a graph G, let Ne (u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e = u v ∈ E (G), if x ∈ Ne (u) and y ∈ Ne (v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22]. © 2009 Elsevier B.V. All rights reserved.
Applied Mathematics Letters (18735452)22(10)pp. 1571-1576
In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G = Kk ∨ (K1 + Kn - k - 1), the join of Kk, the complete graph on k vertices, with the disjoint union of K1 and Kn - k - 1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum. © 2009 Elsevier Ltd. All rights reserved.
