Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 2, pp. 105-111. DOI: 10.18500/1816-9791-2013-13-2-1-105-111, EDN: SJJBAR

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
27.02.2013
Full text:
download
(downloads: 215)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.7
DOI: 
10.18500/1816-9791-2013-13-2-1-105-111
EDN: 
SJJBAR

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. 

Key words: 
vertex labeled graphs
languages over the label alphabet
vertex equivalence
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).
Received: 
29.08.2012
Accepted: 
16.01.2013
Published: 
27.02.2013
Short text (in English):
download
(downloads: 117)
  • 1292 reads