Further contributions on the outer multiset dimension of graphs

DOI10.1007/S00025-022-01829-8MaRDI QIDQ2680828zbMATH OpenOpenAlexFDO

Authors Sandi Klavžar, Dorota Kuziak, Ismael G. Yero

Publication date 4 January 2023

Published in Results in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

gridslexicographic product of graphsouter multiset dimensionouter multiset resolving set

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The outer multiset dimension ${mdim}_{mms}(G)$ of a graph $G$ is the cardinality of a smallest set of vertices that uniquely recognize all the vertices outside this set by using multisets of distances to the set. It is proved that ${mdim}_{mms}(G)=n(G)-1$ if and only if $G$ is a regular graph with diameter at most $2$. Graphs $G$ with ${mdim}_{mms}(G)=2$ are described and recognized in polynomial time. A lower bound on the lexicographic product of $G$ and $H$ is proved when $H$ is complete or edgeless, and the extremal graphs are determined. It is proved that ${mdim}_{mms}(P_s,square,P_t)=3$ for $sgetge2$.

Recommendations

• Some properties of the multiset dimension of graphs
• A generalization of outerplanar graphs
• scientific article; zbMATH DE number 4008413
• On the number of outer connected dominating sets of graphs
• A generalization of outerplanar graphs
• Metric dimension of maximal outerplanar graphs
• Further results on degree sets for graphs
• scientific article; zbMATH DE number 177163
• On dominating sets of maximal outerplanar graphs
• Outer-weakly convex domination number of graphs

Cites work

• A characterization of some graphs with metric dimension two
• Constructing new families of transmission irregular graphs
• Distance-based vertex identification in graphs: the outer multiset dimension
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Infinite family of transmission irregular trees of even order
• Landmarks in graphs
• Metric bases in digital geometry
• On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs
• On transmission irregular starlike trees
• Pairs of a tree and a nontree graph with the same status sequence
• Some properties of the multiset dimension of graphs
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs

Cited in

(2)

• Distance-based vertex identification in graphs: the outer multiset dimension
• Complexity and equivalency of multiset dimension and ID-colorings

This page was built for publication: Further contributions on the outer multiset dimension of graphs

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