The metric dimension of the lexicographic product of graphs
From MaRDI portal
Publication:5894950
DOI10.1016/J.DISC.2012.07.025zbMath1252.05187arXiv1103.3336OpenAlexW2048592031MaRDI QIDQ5894950
Mohsen Jannesari, Behnaz Omoomi
Publication date: 26 October 2012
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: For an ordered set $W={w_1,w_2,...,w_k}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r(v|W):=(d(v,w_1),d(v,w_2),...,d(v,w_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$. 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$, $G[H]$. First, we introduce a new parameter which is called adjacency metric dimension of a graph. Then, we obtain the metric dimension of $G[H]$ in terms of the order of $G$ and the adjacency metric dimension of $H$.
Full work available at URL: https://arxiv.org/abs/1103.3336
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Retracts of strong products of graphs
- On \(k\)-dimensional graphs and their bases
- Resolvability in graphs and the metric dimension of a graph
- Extremal graph theory for metric dimension and diameter
- Discrepancies between metric dimension and partition dimension of a connected graph
- Landmarks in graphs
- Base size, metric dimension and other invariants of groups and graphs
- On the metric dimension of some families of graphs
- On the Metric Dimension of Cartesian Products of Graphs
- On the Complexity of Canonical Labeling of Strongly Regular Graphs
- On the dimension of trees
Related Items (45)
Bounds on the domination number and the metric dimension of co-normal product of graphs ⋮ The \(k\)-metric dimension of the lexicographic product of graphs ⋮ On the metric dimension of generalized tensor product of interval with paths and cycles ⋮ Resolvability in complement of the intersection graph of annihilator submodules of a module ⋮ The fractional \(k\)-truncated metric dimension of graphs ⋮ On adjacency metric dimension of some families of graph ⋮ The simultaneous metric dimension of families composed by lexicographic product graphs ⋮ Truncated metric dimension for finite graphs ⋮ Graphs with constant adjacency dimension ⋮ The adjacency dimension of graphs ⋮ Metric Dimension for Amalgamations of Graphs ⋮ Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Further contributions on the outer multiset dimension of graphs ⋮ The spectrum and metric dimension of Indu–Bala product of graphs ⋮ The simultaneous metric dimension of graph families ⋮ On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results ⋮ Resolvability and convexity properties in the Sierpiński product of graphs ⋮ On redundant locating-dominating sets ⋮ Metric Properties of Non-Commuting Graph Associated to Two Groups ⋮ Locating parameters of the total graph of \(\Gamma(\mathbb{Z}_{2^np^m})\) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Relationships between the 2-metric dimension and the 2-adjacency dimension in the lexicographic product of graphs ⋮ Computing the metric dimension of a graph from primary subgraphs ⋮ Edge metric dimension of some graph operations ⋮ Resolvability and strong resolvability in the direct product of graphs ⋮ Computing the metric dimension of the categorial product of some graphs ⋮ On the strong metric dimension of the strong products of graphs ⋮ The Local metric dimension of the lexicographic product of graphs ⋮ Unnamed Item ⋮ Simultaneous resolvability in families of corona product graphs ⋮ The \(k\)-metric dimension of corona product graphs ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Strong resolving partitions for strong product graphs and Cartesian product graphs ⋮ On dimension of some finite total graphs ⋮ On distance-\(s\) locating and distance-\(t\) dominating sets in graphs ⋮ Maker-breaker resolving game ⋮ The adjacency dimension of some path related trees ⋮ Computing the metric dimension of kayak paddles graph and cycles with chord ⋮ The comparative analysis of metric and edge metric dimension of some subdivisions of the wheel graph ⋮ Lexicographic metric spaces: Basic properties and the metric dimension ⋮ ON THE DISTANCE-DEGREE ENERGY OF GRAPHS ⋮ The simultaneous local metric dimension of graph families ⋮ Computing the metric dimension for chain graphs
This page was built for publication: The metric dimension of the lexicographic product of graphs
