ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


For citation:

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: 10.18500/1816-9791-2013-13-2-1-105-111

Published online: 
27.02.2013
Full text:
(downloads: 39)
Language: 
Russian
Heading: 
UDC: 
519.7
DOI: 
10.18500/1816-9791-2013-13-2-1-105-111

On upper bound of vertex distinguishing word length on vertex labeled graph

Autors: 
Sapunov Sergey Valerievich, Institute of Applied Mathematics and Mechanics
Abstract: 

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. 

References: 
  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).
Short text (in English):
(downloads: 13)