Breaking Symmetry in Graphs by Resolving Sets

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

2 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

Abstract

Let $dim(G)$ and $D(G)$ respectively denote the metric dimension and the distinguishing number of a graph $G$. It is proved that $D(G) \le dim(G)+1$ holds for every connected graph $G$. Among trees, exactly paths and stars attain the bound, and among connected unicyclic graphs such graphs are $t$-cycles for $t\in \{3,4,5\}$. It is shown that for any $1\leq n< m$, there exists a graph $G$ with $D(G)=n$ and ${\rm dim}(G)=m$. Using the bound $D(G) \le dim(G)+1$, graphs with $D(G) = n(G)-2$ are classified. 

Keywords

Main Subjects

Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 15 April 2026

Files

Share

How to cite

Statistics