On the simultaneous metric dimension of a graph and its complement
A set \(S\subseteq V(G)\) is called a resolving set of a graph \(G\) if for any two distinct vertices \(x\) and \(y\) of \(G\), there exists a vertex \(z \in S\) such that \(d(x,z)\neq d(y,z)\). The metric dimension \(\dim G\) of \(G\) is the minimum of the cardinalities of all resolving sets of \(G\). A set \(S\subseteq V\) is a simultaneous resolving set for a finite collection \(\mathcal{C}\) of graphs on a common vertex set \(V\) if \(S\) is a resolving set for every graph in \(\mathcal{C}\). The minimum among the cardinalities of all such \(S\) is called the simultaneous metric dimension of \(\mathcal{C}\), denoted by \(Sd(\mathcal{C})\).\N\NThe authors prove some remarkable characterization theorems namely \( Sd(G,\overline{G}) = 1\) if and only if \(G\in \left\lbrace P_2, \overline{P_2}, P_3, \overline{P_3}\right\rbrace \) and \(Sd(G,\overline{G}) = n-1\) if and only if \(G\in \left\lbrace K_n,\overline{K_n}\right\rbrace \). It remains an open problem to characterize graphs \(G\) with \(Sd(G,\overline{G}) = 2\) and \(Sd(G, \overline{G} )= n-2\). \N\NThey also determine \(Sd (T, \overline{T})\) for trees with \(\operatorname{diam} T = 3= \operatorname{diam} \overline{T}\). For any unicyclic graph \(G\) of order \(n\geq3\), they prove that \( Sd(G, \overline{G})\in \left\lbrace \dim \overline{G}, 1+ \dim \overline{G}\right\rbrace \) and \(Sd(G, \overline{G}) = \dim \overline{G}\) for \(n\geq7\). They also prove the following realization theorem for \(Sd(G, \overline{G})\). For integers \(n, k\) with \((n/2) \leq k \leq n-1\), there exists a connected graph \(G\) of order \(n\) with \(Sd(G,\overline{G}) =k\).
- Extremal graph theory for metric dimension and diameter
- Factor domination in graphs
- Graph theory with applications
- scientific article; zbMATH DE number 3494441 (Why is no real title available?)
- scientific article; zbMATH DE number 3544092 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1749658 (Why is no real title available?)
- Landmarks in graphs
- Resolvability in graphs and the metric dimension of a graph
- The metric dimension of the lexicographic product of graphs
- The simultaneous metric dimension of graph families
This page was built for publication: On the simultaneous metric dimension of a graph and its complement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6977126)
