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 delivery person must leave the central location of the business, deliver packages at a number of addresses, and then return. Naturally, he/she wishes to reduce costs by finding the most efficient route. This motivat...A delivery person must leave the central location of the business, deliver packages at a number of addresses, and then return. Naturally, he/she wishes to reduce costs by finding the most efficient route. This motivates the following： Given a set of k distinct vertices S = {x1, x2,..., xk } in a simple graph G, the closed k-stop-distance of set S is defined to be展开更多
文摘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 delivery person must leave the central location of the business, deliver packages at a number of addresses, and then return. Naturally, he/she wishes to reduce costs by finding the most efficient route. This motivates the following： Given a set of k distinct vertices S = {x1, x2,..., xk } in a simple graph G, the closed k-stop-distance of set S is defined to be
