تعداد نشریات | 5 |
تعداد شمارهها | 111 |
تعداد مقالات | 1,254 |
تعداد مشاهده مقاله | 1,203,710 |
تعداد دریافت فایل اصل مقاله | 1,064,427 |
The 2-dimension of a Tree | ||
Communications in Combinatorics and Optimization | ||
مقاله 17، دوره 5، شماره 1، شهریور 2020، صفحه 69-81 اصل مقاله (617.73 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2019.26495.1119 | ||
نویسندگان | ||
Jason Hedetniemi1؛ Stephen Hedetniemi2؛ Renu C. Renu C. Laskar3؛ Henry Martyn Mulder* 4 | ||
1Department of Mathematics Wingate University Wingate NC USA | ||
2School of Computing Clemson University Clemson, SC U.S.A. | ||
3Clemson University | ||
4Econometrisch Instituut Erasmus Universiteit Rotterdam Netherlands | ||
چکیده | ||
Let $x$ and $y$ be two distinct vertices in a connected graph $G$. The $x,y$-location of a vertex $w$ is the ordered pair of distances from $w$ to $x$ and $y$, that is, the ordered pair $(d(x,w), d(y,w))$. A set of vertices $W$ in $G$ is $x,y$-located if any two vertices in $W$ have distinct $x,y$-locations. A set $W$ of vertices in $G$ is 2-located if it is $x,y$-located, for some distinct vertices $x$ and $y$. The 2-dimension of $G$ is the order of a largest set that is 2-located in $G$. Note that this notion is related to the metric dimension of a graph, but not identical to it. We study in depth the trees $T$ that have a 2-locating set, that is, have 2-dimension equal to the order of $T$. Using these results, we have a nice characterization of the 2-dimension of arbitrary trees. | ||
کلیدواژهها | ||
resolvability؛ location number؛ 2-dimension؛ tree؛ 2-locating set | ||
مراجع | ||
[1] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1-3, 99–113.
[2] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
[3] S.T. Hedetniemi, R.C. Laskar, and H.M. Mulder, New resolvability parameters of graphs, submitted.
[4] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
| ||
آمار تعداد مشاهده مقاله: 696 تعداد دریافت فایل اصل مقاله: 418 |