The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a gr...The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a graph G is the minimum eardinality of a set S of black vertices （whereas vertices in V（G）／S are colored white） such that V（G） is turned black after finitely many applications of ＂the color-change rule＂： a white vertex is converted black if it is the only white neighbor of a black vertex. We show that dim（T） ≤Z（T） for a tree T, and that dim（G）≤Z（G）＋I if G is a unicyclic graph; along the way, we characterize trees T attaining dim（T） = Z（T）. For a general graph G, we introduce the ＂cycle rank conjecture＂. We conclude with a proof of dim（T） - 2 ≤ dim（T ＋ e） ≤dim（T） ＋ 1 for e∈ E（T）.展开更多
A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if ...A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim（G）, is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim（G） equals 1, n-1, or n-2, respectively. We give a Nordhaus–Gaddum-type result for the strong metric dimension of a graph and its complement： for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim（G）＋sdim（G）≤2（ n-2）. It is readily seen that sdim（G）＋sdim（G）=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim（G）＋sdim（G）=2（n 2） if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim（G）＋sdim（G）≤2（n-3） if G is a tree; we also show that 4≤sdim（G）＋sdim（G）≤2（n-3） if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim（G）＋sdim（G）=2（n-3） when G is a tree or a unicyclic graph.展开更多
文摘The metric dimension dim（G） of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices. The zero forcing number Z（G） of a graph G is the minimum eardinality of a set S of black vertices （whereas vertices in V（G）／S are colored white） such that V（G） is turned black after finitely many applications of ＂the color-change rule＂： a white vertex is converted black if it is the only white neighbor of a black vertex. We show that dim（T） ≤Z（T） for a tree T, and that dim（G）≤Z（G）＋I if G is a unicyclic graph; along the way, we characterize trees T attaining dim（T） = Z（T）. For a general graph G, we introduce the ＂cycle rank conjecture＂. We conclude with a proof of dim（T） - 2 ≤ dim（T ＋ e） ≤dim（T） ＋ 1 for e∈ E（T）.
文摘A vertex x in a graph G strongly resolves a pair of vertices v, w if there exists a shortest x-w path containing v or a shortest x-v path containing w in G. A set of vertices SV（G） is a strong resolving set of G if every pair of distinct vertices of G is strongly resolved by some vertex in S. The strong metric dimension of G, denoted by sdim（G）, is the minimum cardinality over all strong resolving sets of G. For a connected graph G of order n≥2, we characterize G such that sdim（G） equals 1, n-1, or n-2, respectively. We give a Nordhaus–Gaddum-type result for the strong metric dimension of a graph and its complement： for a graph G and its complement G, each of order n≥4 and connected, we show that 2≤sdim（G）＋sdim（G）≤2（ n-2）. It is readily seen that sdim（G）＋sdim（G）=2 if and only if n=4; we show that, when G is a tree or a unicyclic graph, sdim（G）＋sdim（G）=2（n 2） if and only if n=5 and G ～=G ～=C5, the cycle on five vertices. For connected graphs G and G of order n≥5, we show that 3≤sdim（G）＋sdim（G）≤2（n-3） if G is a tree; we also show that 4≤sdim（G）＋sdim（G）≤2（n-3） if G is a unicyclic graph of order n≥6. Furthermore, we characterize graphs G satisfying sdim（G）＋sdim（G）=2（n-3） when G is a tree or a unicyclic graph.
