Cite this article as:
Sapunov S. V. On upper bound of vertex distinguishing word length on vertex labeled graph . Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2013, vol. 13, iss. 2, pp. 105-111. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-1-105-111
On upper bound of vertex distinguishing word length on vertex labeled graph
The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word length equal to half the number of vertices is obtained.
1. Glushkov V. M., Tsejtlyn G. E., Yuschenko E. L. Al-
gebra. Iazyki. Programmirovanie [Algebra. Languages.
Programming]. Kiev, Naukova dumka, 1989, 378 p. (in
Russian).
2. Kapitonova Yu. V., Letichevsky A. A. Matemati-
cheskaia teoriia proektirovaniia vychislitel’nykh sistem
[Mathematical Theory of Computational Systems
Design]. Moscow, Nauka, 1988, 298 p. (in Russian).
3. Kilibarda G., Kudryavtsev V. B., Ushchumlich Sh.
Independent systems of automata on mazes. Diskretnaya
matematika, 2003, vol. 15, no. 2, pp. 3–39 (in Russian).
4. Dudek G., Jenkin M. Computational Principles of
Mobile Robotics. Cambridge University Press, 2000,
280 p.
5. Sapunov S. V. Ekvivalentnost’ pomechennykh grafov
[Vertex Labeled Graphs Equivalence. Trudy IPMM
NANU, 2002, vol. 7, pp. 162–167 (in Russian).
6. Hopcroft J. E., Motwani R., Ullman J. D. Vvedenie
v teoriiu avtomatov, iazykov i vychislenii [Introduction
to Automata Theory, Languages, and Computation].
Moscow, Izdat. dom «Williams», 2002, 528 p. (in
Russian).
7. Grunsky I. S., Sapunov S. V. Reconstruction of the
graph of operating environment of mobile robot by vertexlabeling
sufficient for further navigation. Iskusstvennyj
intellekt, 2012, no. 4, pp. 420–428 (in Russian).
8. Grunsky I. S., Sapunov S. V. Identifikatsiia vershin
pomechennykh grafov [Vertex Identification on Vertex
Labeled Graphs]. Trudy IPMM NANU, 2010, vol. 21,
pp. 86–97 (in Russian).
