Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph

DOI10.1155/2020/9407456zbMATH Open1435.05065arXiv1910.12860OpenAlexW3031029086MaRDI QIDQ2188178FDOQ2188178

Hassan Zarei, Ali Zafari, Jiabao Liu

Publication date: 10 June 2020

Published in: Complexity (Search for Journal in Brave)

Abstract: Let $Gamma$ be a simple connected undirected graph with vertex set $V(Gamma)$ and edge set $E(Gamma)$. The metric dimension of a graph $Gamma$ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. For an ordered subset $W=w_1,w_2,\mathrm{...},w_k$ of vertices in a graph $Gamma$ and a vertex $v$ of $Gamma$, the metric representation of $v$ with respect to $W$ is the $k$-vector $r(v|W)=(d(v,w_1),d(v,w_2),\mathrm{...},d(v,w_k))$. If every pair of distinct vertices of $Gamma$ have different metric representations then the ordered set $W$ is called a resolving set of $Gamma$. It is known that the problem of computing this invariant is NP-hard. In this paper, we consider the problem of determining the cardinality $psi(Gamma)$ of minimal doubly resolving sets of $Gamma$, and the strong metric dimension for jellyfish graph $JFG(n,m)$ and cocktail party graph $CP(k+1)$.

Full work available at URL: https://arxiv.org/abs/1910.12860

Recommendations

• Computing minimal doubly resolving sets and the strong metric dimension of the layer sun graph and the line graph of the layer sun graph
• Minimal doubly resolving sets and the strong metric dimension of Hamming graphs
• Minimal doubly resolving sets of antiprism and Möbius ladders
• Resolvability in graphs and the metric dimension of a graph
• Minimal doubly resolving sets and the strong metric dimension of some convex polytopes

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Resolvability in graphs and the metric dimension of a graph
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the metric dimension of circulant graphs
• On \(k\)-dimensional graphs and their bases
• Landmarks in graphs
• Title not available (Why is that?)
• On Metric Generators of Graphs
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs
• The strong metric dimension of graphs and digraphs
• Title not available (Why is that?)
• Minimal doubly resolving sets and the strong metric dimension of Hamming graphs
• Computing minimal doubly resolving sets of graphs
• The Metric Dimension of Circulant Graphs
• On the metric dimension of Cartesian powers of a graph
• Minimal doubly resolving sets of prism graphs
• Title not available (Why is that?)
• Metric dimension of fullerene graphs
• On the spectrum of a class of distance-transitive graphs

Cited In (4)

• Graphs with doubly resolving number 2
• The fault‐tolerant beacon set of hexagonal Möbius ladder network
• Computing minimal doubly resolving sets and the strong metric dimension of the layer sun graph and the line graph of the layer sun graph
• On doubly resolving sets in graphs

This page was built for publication: Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188178)