Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem

In this paper,we consider the NP-hard problem of finding the minimum dominant resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B.A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B.The dominant metric dimension of G is the cardinality number of the minimum dominant resolving set.The dominant metric dimension is computed by a binary version of the Archimedes optimization algorithm(BAOA).The objects of BAOA are binary encoded and used to represent which one of the vertices of the graph belongs to the dominant resolving set.The feasibility is enforced by repairing objects such that an additional vertex generated from vertices of G is added to B and this repairing process is iterated until B becomes the dominant resolving set.This is the first attempt to determine the dominant metric dimension problem heuristically.The proposed BAOA is compared to binary whale optimization(BWOA)and binary particle optimization(BPSO)algorithms.Computational results confirm the superiority of the BAOA for computing the dominant metric dimension.

On Cycle Related Graphs with Constant Metric Dimension

If G is a connected graph, the distance d (u,v) between two vertices u,v ∈ V(G) is the length of a shortest path between them. Let W = {w1, w2, ..., wk} be an ordered set of vertices of G and let v be a vertex of G . The repre-sentation r(v|W) of v with respect to W is the k-tuple (d(v,w1), d(v,w2), …, d(v,wk)). . If distinct vertices of G have distinct representations with respect to W , then W is called a resolving set or locating set for G. A re-solving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension of G , denoted by dim (G). A family ? of connected graphs is a family with constant metric dimension if dim (G) is finite and does not depend upon the choice of G in ?. In this paper, we show that dragon graph denoted by Tn,m and the graph obtained from prism denoted by 2Ck + {xkyk} have constant metric dimension.

ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION

In this paper, we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn, a class of cubic convex polytopes considering the open problem raised in [M. Imran et al., families of plane graphs with constant metric dimension, Utilitas Math., in press] and finally Harary graphs H5,n by partially answering to an open problem proposed in Ⅱ. Javaid et al., Families of regular graphs with constant metric dimension, Utilitas Math., 2012, 88： 43-57]. We prove that these classes of regular graphs have constant metric dimension.

The Fractional Metric Dimension of Permutation Graphs

Let G =（V（G）, E（G）） be a graph with vertex set V（G） and edge set E（G）. For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V（G） and for U V（G）, let g（U） =∑s∈Ug（s）. A real-valued function g ： V（G） → [0, 1] is a resolving function of G if g（RG{x, y}） ≥ 1 for any two distinct vertices x, y ∈ V（G）. The fractional metric dimension dimf（G）of a graph G is min{g（V（G）） ： g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ ： V（G1） → V（G2） be a bijection. Then, a permutation graph Gσ =（V, E） has the vertex set V = V（G1） ∪ V（G2） and the edge set E = E（G1） ∪ E（G2） ∪ {uv ｜ v = σ（u）}. First,we determine dimf（T） for any tree T. We show that 1 〈 dimf（Gσ） ≤1/2（｜V（G）｜ ＋ ｜S（G）｜） for any connected graph G of order at least 3, where S（G） denotes the set of support vertices of G. We also show that, for any ε 〉 0, there exists a permutation graph Gσ such that dimf（Gσ）- 1 〈 ε. We give examples showing that neither is there a function h1 such that dimf（G） 〈 h1（dimf（Gσ）） for all pairs（G, σ）, nor is there a function h2 such that h2（dimf（G）） 〉 dimf（Gσ） for all pairs（G, σ）. Furthermore,we investigate dimf（Gσ） when G is a complete k-partite graph or a cycle.

On Strong Metric Dimension of Graphs and Their Complements

A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim（G）, is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim（G） equals 1, n-1, or n-2, respectively. We give a Nordhaus–Gaddum-type result for the strong metric dimension of a graph and its complement： for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim（G）＋sdim（G）≤2（ n-2）. It is readily seen that sdim（G）＋sdim（G）=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim（G）＋sdim（G）=2（n 2） if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim（G）＋sdim（G）≤2（n-3） if G is a tree; we also show that 4≤sdim（G）＋sdim（G）≤2（n-3） if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim（G）＋sdim（G）=2（n-3） when G is a tree or a unicyclic graph.

On the Constant Metric Dimension of Generalized Petersen Graphs P(n,4)

In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） and n = 4k ＋ 3 （k is odd）, we prove that the metric dimension of P（n,4） is bounded above by 4. This shows that each graph of the family of generalized Petersen graphs P（n, 4） has constant metric dimension.

On the Metric Dimension of Barycentric Subdivision of Cayley Graphs

In a connected graph G, the distance d（u, v） denotes the distance between two vertices u and v of G. Let W = {w1, w2,……, wk} be an ordered set of vertices of G and let v be a vertex of G. The representation r（v1W） of v with respect to W is the k-tuple （d（v, w1）, d（v, w2）,…, d（v, wk））. The set W is called a resolving set or a locating set if every vertex of G is uniquely identified by its distances from the vertices of W, or equivalently, if distinct vertices of G have distinct representations with respect to W. A resolving set of minimum cardinality is called a metric basis for G and this cardinality is the metric dimension of G, denoted by β（G）. Metric dimension is a generalization of affine dimension to arbitrary metric spaces （provided a resolving set exists）. In this paper, we study the metric dimension of barycentric subdivision of Cayley graphs Cay （Zn Z2）. We prove that these subdivisions of Cayley graphs have constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of barycentric subdivision of Cayley graphs Cay （Zn Z2）.

A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs

The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a graph G is the minimum eardinality 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 black if it is the only white neighbor of a black vertex. We show that dim（T） ≤Z（T） for a tree T, and that dim（G）≤Z（G）＋I if G is a unicyclic graph; along the way, we characterize trees T attaining dim（T） = Z（T）. For a general graph G, we introduce the ＂cycle rank conjecture＂. We conclude with a proof of dim（T） - 2 ≤ dim（T ＋ e） ≤dim（T） ＋ 1 for e∈ E（T）.

Resolvability in Circulant Graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v E V（G） there is a vertex w E W such that d（u, w） ≠ d（v, w）. A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim（G）. For a vertex u of G and a subset S of V（G）, the distance between u and S is the number minses d（u,s）. A k-partition II = {$1,$2,..., Sk} of V（G） is called a resolving partition if for every two distinct vertices u, v E V（G） there is a set Si in H such that d（u, Si） ≠ d（v, Si）. The minimum k for which there is a resolving k-partition of V（G） is called the partition dimension of G, denoted by pd（G）. The circulant graph is a graph with vertex set Zn, an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i - j （rood n） E C, where C C Zn has the property that C = -C and 0 ￠ C. The circulant graph is denoted by Xn,△ where A = ｜C｜. In this paper, we study the metric dimension of a family of circulant graphs Xn,3 with connection set C = {1, 3, n - 1} and prove that dim（Xn,3） is independent of choice of n by showing that dim（Xn,a） = {3 for all n ≡0 （mod 4）,4 for all n≡2 （mod4）.We also study the partition dimension of a family of circulant graphs Xm,4 with connection set C = {±1, ±2} and prove that pd（Xn,4） is independent of choice of n and show that pd（X5,4） = 5 and pd（Xn,a） ={ 3 for all odd n≥9,4 for all even n≥6 and n=7.

Metric Identification of Vertices in Polygonal Cacti

The distance between two vertices u and v in a connected graph G is the number of edges lying in a shortest path(geodesic)between them.A vertex x of G performs the metric identification for a pair(u,v)of vertices in G if and only if the equality between the distances of u and v with x implies that u=v(That is,the distance between u and x is different from the distance between v and x).The minimum number of vertices performing the metric identification for every pair of vertices in G defines themetric dimension of G.In this paper,we performthemetric identification of vertices in two types of polygonal cacti:chain polygonal cactus and star polygonal cactus.

Minimal Doubly Resolving Sets of Certain Families of Toeplitz Graph

The doubly resolving sets are a natural tool to identify where diffusion occurs in a complicated network.Many realworld phenomena,such as rumour spreading on social networks,the spread of infectious diseases,and the spread of the virus on the internet,may be modelled using information diffusion in networks.It is obviously impractical to monitor every node due to cost and overhead limits because there are too many nodes in the network,some of which may be unable or unwilling to send information about their state.As a result,the source localization problem is to find the number of nodes in the network that best explains the observed diffusion.This problem can be successfully solved by using its relationship with the well-studied related minimal doubly resolving set problem,which minimizes the number of observers required for accurate detection.This paper aims to investigate the minimal doubly resolving set for certain families of Toeplitz graph Tn(1,t),for t≥2 and n≥t+2.We come to the conclusion that for Tn(1,2),the metric and double metric dimensions are equal and for Tn(1,4),the double metric dimension is exactly one more than the metric dimension.Also,the double metric dimension for Tn(1,3)is equal to the metric dimension for n=5,6,7 and one greater than the metric dimension for n≥8.

关于非交换群的非交换图的度量维数

给定一个非交换群,该群的非交换图以该群所有非中心元素构成的集合为顶点集,两个不同的顶点x和y相邻的充分必要条件是xy≠yx.文章研究非交换群的非交换图的度量维数问题,确定了二面体群的非交换图的度量维数,且对任意非交换群的非交换图的度量维数给出了紧的上下界.

哑铃图的度量维数(英文)

设W是图G的一个顶点子集,若G中每一个顶点到W的距离构成的向量都不相同,则称W是G的一个分辨集;G的度量维数是指G的分辨集基数的最小值.确定了哑铃图的度量维数,推广了Ali等的一个结果.

项链图的边度量生成集

图的度量维数问题是组合优化领域研究的一个热点问题,边度量生成集问题是其一个重要变形.给出了项链图的一个边度量生成集,并证明了其边度量维数为3.

The Commuting Graphs on Dicyclic Groups

For a group G and a non-empty subsetΩof G,the commuting graph C(G,Ω)ofΩis a graph whose vertex set isΩand any two vertices are adjacent if and only if they commute in G.Define T4n=(a,b|a^(2)n=b^(4)=1,an=b2,b^(−1)ab=a^(−1)),the dicyclic group of order 4n(n≥3),which is also known as the generalized quaternion group.We mainly investigate the properties and metric dimension of the commuting graphs on the dicyclic group T4n.