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.