Source-linked AI summary
Mixed metric dimension of graphs
Aleksander Kelenc, Dorota Kuziak, Andrej Taranenko, Ismael G. Yero
TL;DR
Graph metric dimension identifies vertices, while edge metric dimension identifies edges; this paper asks how to identify both kinds of elements with one vertex set. It studies the structure and bounds of mixed metric generators, graph families and girth-related bounds, and complexity, characterizing both extreme bounds and proving general-case NP-hardness.
Problem
The paper studies how a vertex set can distinguish every pair of vertices and edges in a connected graph, extending distance-based identification beyond vertices or edges alone.
Source: §1 · pp. 1–2Method
Results
The paper characterizes mdim(G) = 2 exactly for paths, characterizes mdim(G) = n by a maximal-neighbour condition, and proves that determining mixed metric dimension is NP-hard in general.
Source: §3 · pp. 4–5, §6 · p. 9Takeaways & Limitations
Mixed metric dimension provides a single distance-based measure for identifying both vertices and edges, with structural characterizations at its two extreme bounds.
Source: §1 · p. 2, §3 · pp. 4–5The stated setting is connected graphs with at least two vertices; singleton graphs are excluded.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
Let $G=(V,E)$ be a connected graph. A vertex $w\in V$ distinguishes two elements (vertices or edges) $x,y\in E\cup V$ if $d_G(w,x)\ne d_G(w,y)$. A set $S$ of vertices in a connected graph $G$ is a mixed metric generator for $G$ if every two 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 $\mathrm{mdim}(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.
1 Introduction
The paper extends graph distance-based identification from vertices and edges separately to identifying both kinds of elements with one vertex set. It studies mixed metric generators, their structure and bounds, graph families, and computational complexity.
1 Introduction
- Metric dimension has been studied in connection with network navigation, chemistry, pattern recognition, image processing, and related graph invariants.The concept was introduced independently by Slater and Harary and Melter.Source: §1 · pp. 1–2
- Mixed metric identification combines vertex and edge recognition, which need not coincide under separate metric and edge metric generators.The paper defines the target as uniquely identifying vertices and edges by distance vectors to a fixed vertex set.Source: §1 · p. 2
- The paper considers connected graphs with at least two vertices.Singleton graphs are excluded.Source: §1 · pp. 2–3
- The paper studies mixed metric generators, characterizes graphs attaining the lower and upper bounds, treats graph families and girth-based bounds, and proves general-case NP-hardness.It also presents three open problems.Source: §1 · p. 3
2 Definition of the problem
The section defines mixed metric generators as vertex sets that distinguish every pair drawn from a graph’s vertices and edges. It also formulates finding a minimum such set as an optimization problem over binary vertex-selection variables.
2 Definition of the problem
- A mixed metric generator is a vertex set whose members distinguish every pair of vertices and edges by their distances to those elements; its minimum size is mdim(G).A minimum mixed metric generator is called a mixed metric basis.Source: §2 · p. 3
- The optimization model uses binary variables for vertices and an n × (n + m) distance matrix whose columns correspond to vertices and edges.The objective is the sum of the vertex-selection variables.Source: §2 · p. 3
- Minimizing the model subject to its constraints yields a mixed metric basis, while a mixed metric basis gives a minimum solution.The selected vertices are those whose variables equal 1.Source: §2 · p. 3
3 The Structure of Mixed Metric Generators
The section gives structural conditions on mixed metric generators and characterizes graphs attaining both extreme values of mixed metric dimension. It establishes the bounds 2 ≤ mdim(G) ≤ n, with paths attaining the lower bound and a maximal-neighbour condition characterizing the upper bound.
3 The Structure of Mixed Metric Generators
- Every mixed metric generator is both a metric generator and an edge metric generator, and 2 ≤ mdim(G) ≤ n.The full vertex set is a mixed metric generator, but a single vertex cannot be one because it shares its distance to itself with an incident edge.Source: §3 · pp. 3–4
- True twins both belong to every mixed metric generator, whereas a generator must contain at least one of any pair of false twins.True twins have equal closed neighborhoods; false twins have equal open neighborhoods.Source: §3 · p. 4
- Every extreme vertex and every degree-1 vertex belongs to every mixed metric generator.For an extreme vertex, its neighborhood induces a complete graph.Source: §3 · p. 4
- mdim(G) = 2 if and only if G is a path.The two leaves of a path distinguish all pairs of vertices and edges.Source: §3 · pp. 4–5
- If each edge vw incident to the omitted vertex v is distinguished from w by some vertex in V(G)\{v}, then V(G)\{v} is a mixed metric generator.The proof reduces the remaining checks to pairs consisting of a neighbor of v and its incident edge to v.Source: §3 · p. 5
- mdim(G) = n if and only if every vertex has a maximal neighbour whose closed neighborhood contains its own.A maximal neighbour u of v satisfies N[v] ⊆ N[u].Source: §3 · p. 5
4 Mixed Metric Dimension of Some Families of Graphs
The section determines mixed metric dimensions for cycles, complete bipartite graphs, trees, and grid graphs. The results give exact values in each family, with the complete bipartite value depending on whether either part has size two.
4 Mixed Metric Dimension of Some Families of Graphs
- mdim(C_n) = 3 for every n ≥ 4.The proof uses three vertices to distinguish vertex–edge pairs after two already distinguish vertex pairs and edge pairs.Source: §4 · p. 6
- For K_{r,t} with r,t ≥ 3, mdim(K_{r,t}) = r + t − 2; if r = 2 or t = 2, it is r + t − 1.When a part has size two, a mixed generator of size r + t − 2 would fail to distinguish a vertex from an incident edge.Source: §4 · p. 6
- For a tree T with l(T) leaves, mdim(T) = l(T).The proof shows that all leaves form a mixed metric generator and uses a lower bound to establish equality.Source: §4 · pp. 6–7
- For the grid graph P_r□P_t with r ≥ t ≥ 2, mdim(P_r□P_t) = 3.The proof uses three corner vertices as a mixed metric generator.Source: §4 · pp. 7–8
5 An Upper Bound for the Mixed Metric Dimension of Graphs
For a graph of order n containing a cycle, the paper bounds mixed metric dimension using the graph's girth. The bound is achieved by examples including cycles, complete graphs, and complete bipartite graphs K_{2,t}.
5 An Upper Bound for the Mixed Metric Dimension of Graphs
- For any graph G of order n with a cycle, mdim(G) ≤ n − g(G) + 3.Here g(G) is the order of the smallest cycle in G.Source: §5 · p. 8
- The proof constructs a generator from all vertices outside a shortest cycle plus three vertices on that cycle.The selected cycle vertices are v_0, v_1, and v_{⌈r/2⌉}; the proof checks vertex pairs, edge pairs, and vertex–edge pairs.Source: §5 · p. 8
- The bound is sharp for cycles, complete graphs, and K_{2,t}; it is also sharp when every vertex has a maximal neighbour.For cycles, complete graphs, and K_{2,t}, the paper gives mdim values equal to n − g(G) + 3.Source: §5 · p. 9
6 The Complexity of the Mixed Metric Dimension Problem
The paper reduces 3-SAT to the mixed metric dimension problem and proves the decision problem NP-complete. Its construction encodes truth assignments in graph components and makes satisfiability equivalent to achieving the specified generator size.
6 The Complexity of the Mixed Metric Dimension Problem
- The MDIM decision problem is NP-complete.The proof establishes polynomial verification and a polynomial reduction from 3-SAT.Source: §6 · pp. 9, 13
- A proposed mixed metric generator can be verified in polynomial time by computing its distances to all vertices and edges and checking every pair.This establishes membership of the decision problem in NP.Source: §6 · p. 9
- The reduction maps a 3-SAT formula with m clauses and n variables to a connected graph with target r = 2m + n, whose mixed metric dimension is at most r exactly when the formula is satisfiable.The construction uses truth-setting and satisfaction-testing components, augmented with edges for communication and connectivity.Source: §6 · pp. 9–11
- Each truth-setting component represents a variable, with T_i and F_i as truth-value ends, and every mixed metric generator must select at least one of a_i or b_i.The component attaches to the rest of the graph only through T_i and F_i.Source: §6 · p. 9
- Each clause component requires c5_j and c6_j in every mixed metric generator, while communication edges link literal polarity to the clause component.Positive and negative occurrences connect the truth-setting and clause vertices in opposite endpoint patterns.Source: §6 · p. 10
- A satisfying assignment yields a mixed metric generator of size r, so satisfiable formulas produce graphs with mixed metric dimension exactly r.The construction includes the clause vertices c5_j and c6_j and one assignment-dependent vertex per variable.Source: §6 · pp. 11–12
- Conversely, a generator of size r selects exactly one assignment vertex per variable and the required two vertices per clause, from which the proof derives a satisfying assignment.The proof uses a distinguishing pair of clause edges to identify a satisfied literal.Source: §6 · pp. 12–13
7 Open problems
The paper closes with three open characterization problems concerning equality between mixed metric dimension and other bounds.
7 Open problems
- The authors ask for characterizations of graphs where mixed metric dimension equals metric dimension, equals edge metric dimension, or achieves the bound from Theorem 5.1.These are posed as three open problems.Source: §7 · p. 13