AIMS Mathematics · 2020 · 26 citations · 1 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsEdge MetricsGraph AlgorithmsGraph TheoryClique Number In Hypergraphs
Let $G = (V, E)$ be a connected graph of order $n$. $S \subseteq V$ is an edge metric generator of $G$ if any pair of edges in $E$ can be distinguished by some element of $S$. The edge metric dimension $edim(G)$ of a graph $G$ is the least size of an edge metric generator of $G$. In this paper, we give the characterization of all connected bipartite graphs with $edim = n-2$, which partially answers an open problem of Zubrilina (2018). Furthermore, we also give a sufficient and necessary condition for $edim(G) = n-2$, where $G$ is a graph with maximum degree $n-1$. In addition, the relationship between the edge metric dimension and the clique number of a graph $G$ is investigated by construction.
1
On graphs with the maximum edge metric dimension
Enqiang Zhu, Andrej Taranenko, Zehui Shao et al. · Discrete Applied Mathematics · 2018 · 52 citations