Mixed metric dimension of graphs Kelenc, Aleksander; Kuziak, Dorota; Taranenko, Andrej ...
Applied mathematics and computation,
12/2017, Letnik:
314
Journal Article
Recenzirano
Odprti dostop
Let G=(V,E) be a connected graph. A vertex w ∈ V distinguishes two elements (vertices or edges) x, y ∈ E ∪ V if dG(w, x) ≠ dG(w, y). A set S of vertices in a connected graph G is a mixed metric ...generator for G if every two distinct elements (vertices or edges) of G are distinguished by some vertex of S. The smallest cardinality of a mixed metric generator for G is called the mixed metric dimension and is denoted by dimm(G). In this paper we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results about the mixed metric dimension of some families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case.
Let G=(V,E) be a connected graph, let v∈V be a vertex and let e=uw∈E be an edge. The distance between the vertex v and the edge e is given by dG(e,v)=min{dG(u,v),dG(w,v)}. A vertex w∈V distinguishes ...two edges e1,e2∈E if dG(w,e1)≠dG(w,e2). A set S of vertices in a connected graph G is an edge metric generator for G if every two edges of G are distinguished by some vertex of S. The smallest cardinality of an edge metric generator for G is called the edge metric dimension and is denoted by edim(G). In this paper, we introduce the concept of edge metric dimension and initiate the study of its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the edge metric dimension and the standard metric dimension of graphs. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present some bounds and closed formulae for the edge metric dimension of several classes of graphs.
•Three problems regarding metric and edge metric dimension of a graph are considered: 1. For which integers r,t,n larger than 0 with r,t being at most n-1, can be constructed a graph G of order n ...with dim(G)=r and edim(G)=t? 2. Is it possible that dim(G) or edim(G) would be bounded from above by some constant factor of edim(G) or dim(G), respectively? 3. Can you construct some other families of graphs for which dim(G)>edim(G)?•We present an almost complete answer to question 1.•We show the unboundedness in problem 2.•We give positive answer to question 3.
Given a connected graph G, the metric (resp. edge metric) dimension of G is the cardinality of the smallest ordered set of vertices that uniquely identifies every pair of distinct vertices (resp. edges) of G by means of distance vectors to such a set. In this work, we settle three open problems on (edge) metric dimension of graphs. Specifically, we show that for every r,t≥2 with r≠t, there is n0, such that for every n≥n0 there exists a graph G of order n with metric dimension r and edge metric dimension t, which among other consequences, shows the existence of infinitely many graph whose edge metric dimension is strictly smaller than its metric dimension. In addition, we also prove that it is not possible to bound the edge metric dimension of a graph G by some constant factor of the metric dimension of G.
•We characterize graphs G of order n for which βm(G)=n−g(G)+3 where g(G) is the girth of G. This resolves a problem in Appl. Math. Comput. 314 (2017) 429–438.•Bounds on mixed metric dimension of ...Cartesian product G□H are determined. This resolves two problems in Discrete Math. 341 (2018) 2083–2088.•Two closed formulae for mixed metric dimension of T□Pn are provided. This generalizes the result on Ps□Pn in Appl. Math. Comput. 314 (2017) 429–438.
A vertex gv in a connected graph G is said to distinguish two distinct elements p,q∈V(G)⋃E(G) if dG(p,gv)≠dG(q,gv). A subset W⊆V(G) is a mixed metric generator of G if every two distinct elements from V(G)⋃E(G) are distinguished by W. The mixed metric dimension of G, denoted by βm(G), is the minimum cardinality of mixed metric generators in it. In this work, we first answer the problem of characterizing graphs G which achieve βm(G)=n−g(G)+3 in Appl. Math. Comput. 314 (2017) 429–438 where g(G) is the girth of G, and then determine bounds on the mixed metric dimension of Cartesian product G□H which resolves two open problems in Discrete Math. 341 (2018) 2083–2088 as a natural corollary. In addition, we provide two closed formulae for βm(T□Pn) in terms of βm(T) which generalize the result on βm(Ps□Pn) in Appl. Math. Comput. 314 (2017) 429–438.
Let G be a finite, simple, and connected graph with the vertex set V and the edge set E. The distance between the vertex u and the edge e=vw is defined as d(u,e)=min{d(u,v),d(u,w)}. A vertex x ...distinguishes two edges e1,e2 if d(x,e1)≠d(x,e2). A subset Le of V is called an edge metric generator for G if every two distinct edges of G are distinguished by some vertex of Le. The minimum cardinality of an edge metric generator for G is called the edge metric dimension and is denoted by dime(G). Similarly, a vertex x distinguishes two elements (vertices or edges) u,v∈V∪E if d(x,u)≠d(x,v). A subset Lm of V is called a mixed metric generator for G if every two distinct elements (vertices and edges) of G are distinguished by some vertex of Lm. The minimum cardinality of a mixed metric generator for G is called the mixed metric dimension and is denoted by dimm(G). In this paper, we study the edge metric dimension and mixed metric dimension of planar graph Qn. We prove that the edge metric dimension and the mixed metric dimension of Qn are both finite and do not depend upon the number of vertices.
An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S, where the distance between a vertex v and an ...edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dime(G). It follows that 1≤dime(G)≤n−1 for any n-vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O(n3) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful.
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.
In this paper extremal values of the difference between several graph invariants related to the metric dimension are studied: Mixed metric dimension, edge metric dimension and strong metric ...dimension. These non-trivial extremal values are computed over all connected graphs of given order. To obtain such extremal values several techniques are developed. They use functions related to metric dimension graph invariants to obtain lower and/or upper bounds on these extremal values and exact computations when restricting to some specific families of graphs.
For a given graph G, the metric and edge metric dimensions of G, dim(G) and edim(G), are the cardinalities of the smallest possible subsets of vertices in V(G) such that they uniquely identify the ...vertices and the edges of G, respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph G such that dim(G)=a and edim(G)=b for every pair of integers a,b, where 4≤b<a. For this we use subdivisions of complete graphs, whose metric dimension is in some cases smaller than the edge metric dimension. Along the way, we present an upper bound for the metric and edge metric dimensions of subdivision graphs under some special conditions.
PDF
