On the Metric Dimension of Corona Product of a Graph with K1
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
For an ordered set W = {w1, w2, . . . , wk} of vertices and a vertex v in a connected graph G, the k-vector r(v|W) = (d(v, w1), d(v, w2), . . . , d(v, wk)) is called the metric representation of v with respect to W, where d(x, y) is the distance between the vertices x and y. A set W is called a resolving set for G if distinct vertices of G have distinct metric representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension dim(G), and a resolving set of minimum cardinality is a basis of G. The corona product, G ⊙ H of graphs G and H is obtained by taking one copy of G and n(G) copies of H, and by joining each vertex of the ith copy of H to the ith vertex of G. In this paper, we obtain bounds for dim(G ⊙ K1), characterize all graphs G with dim(G ⊙ K1) = dim(G), and prove that dim(G ⊙ K1) = n − 1 if and only if G is the complete graph Kn or the star graph K1,n−1.
Abstract
For an ordered set W = {w1, w2, . . . , wk} of vertices and a vertex v in a connected graph G, the k-vector r(v|W) = (d(v, w1), d(v, w2), . . . , d(v, wk)) is called the metric representation of v with respect to W, where d(x, y) is the distance between the vertices x and y. A set W is called a resolving set for G if distinct vertices of G have distinct metric representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension dim(G), and a resolving set of minimum cardinality is a basis of G. The corona product, G ⊙ H of graphs G and H is obtained by taking one copy of G and n(G) copies of H, and by joining each vertex of the ith copy of H to the ith vertex of G. In this paper, we obtain bounds for dim(G ⊙ K1), characterize all graphs G with dim(G ⊙ K1) = dim(G), and prove that dim(G ⊙ K1) = n − 1 if and only if G is the complete graph Kn or the star graph K1,n−1.
참고문헌 (14)
- Z. Beerliova, "Network dicovery and verification", IEEE J. Sel. Areas Commun, 24(12), pp.2168~2181 (2006)
- P. Buczkowski, "On k-dimensional graphs and their bases", Period. Math. Hungar, 46(1), pp.9~15 (2003)
- J. Caceres, "On the metric dimension of cartesian products of graphs", SIAM J. Discrete Math, 21(2), pp.423~441 (2007)
- G. G. Chappell, "Bounds on the metric and partition dimensions of a graph", Ars Combin, 88, pp.349~366 (2008)
- G. Chartrand, "Resolvability in graphs and the metric dimension of a graph", Discrete Appl. Math, 105, pp.99~113 (2000)
- G. Chartrand, "The theory and applications of resolvability in graphs", Congr. Numer, 160, pp.47~68 (2003)
- H. Fernau, "On the (adjacency) metric dimension of corona and strong product graphs and their local variants: Combinatorial and com-putational results", Discrete Appl. Math, 236, pp.183~202 (2018)
- F. Harary, "On the metric dimension of a graph", Ars Combin, 2, pp.191~195 (1976)
- S. Khuller, "Landmarks in graphs", Discrete Appl. Math, 70(3), pp.217~229 (1996)
- R. A. Melter, "Metric bases in digital geometry", Comput. Graph. Image Process, 25, pp.113~121 (1984)
- A. Sebo, "On metric generators of graphs", Math. Oper. Res, 29(2), pp.383~393 (2004)
- P. J. Slater, "Leaves of trees", Congr. Numer, 14, pp.549~559 (1975)
- P. J. Slater, "Dominating and reference sets in graphs", J. Math. Phys. Sci, 22, pp.445~455 (1988)
- I. G. Yero, "On the metric dimension of corona product graphs", Comput. Math. Appl, 61, pp.2793~2798 (2011)