Geodesic
Domination on the vertices of labeled graphs
Algebra and discrete mathematics, Tome 14 (2012) no. 2, pp. 174-184.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we introduce and study a domination relation on vertices of vertex-labeled graphs induced by vertex languages comparison. An effective method of checking this relation is developed. Properties of vertices maximal by this relation are investigated. It is shown that dominating vertices form a connected component of the graph.
Keywords: vertex labeled graph, languages over the vertex labels alphabets. 
@article{ADM_2012_14_2_a3,
     author = {Igor Grunsky and Irina Mikhaylova and Sergey Sapunov},
     title = {Domination on the vertices of labeled graphs},
     journal = {Algebra and discrete mathematics},
     pages = {174--184},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2012_14_2_a3/}
}
TY  - JOUR
AU  - Igor Grunsky
AU  - Irina Mikhaylova
AU  - Sergey Sapunov
TI  - Domination on the vertices of labeled graphs
JO  - Algebra and discrete mathematics
PY  - 2012
SP  - 174
EP  - 184
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2012_14_2_a3/
LA  - en
ID  - ADM_2012_14_2_a3
ER  - 
%0 Journal Article
%A Igor Grunsky
%A Irina Mikhaylova
%A Sergey Sapunov
%T Domination on the vertices of labeled graphs
%J Algebra and discrete mathematics
%D 2012
%P 174-184
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2012_14_2_a3/
%G en
%F ADM_2012_14_2_a3
Igor Grunsky; Irina Mikhaylova; Sergey Sapunov. Domination on the vertices of labeled graphs. Algebra and discrete mathematics, Tome 14 (2012) no. 2, pp. 174-184. http://geodesic.mathdoc.fr/item/ADM_2012_14_2_a3/

[1] Letichevsky A., “Algebra of bihavior transformation and its application”, Structural Theory of Automata, Semigroups and Universal Algebra, Springer, 2005, 241–272 | DOI | MR

[2] Droste M., Kuich W., Vogler H., Handbook of Weighted Automata, Springer, 2009 | MR

[3] Davey B. A., Introduction to lattices and Order, Cambridge University Press, 1990 | MR

[4] Dudek G., Jenkin M., Computational Principles of Mobile Robotics, Cambridge University Press, 2000

[5] Baier C., Katoen J.-P., Principle of Model Checking, MIT Press, 2008 | MR | Zbl

[6] Grunsky I., Kurgansky A., Potapov I., “Languages representable by vertex-labeled graphs”, Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, LNCS, 3618, 2005, 435–446 | MR | Zbl

[7] Sapunov S. V., “Method of labeled graphs indistinduishebikity checking”, Transaction of IAMM NASU, 16 (2008), 179–189 (in Russian) | MR | Zbl

[8] Grunsky I., Potapov I., Pryanichnikiva E., “On algebra of languages representable by vertex-labeled graphs”, Theoretical Computer Science, 426–427, 42–48 | DOI | MR | Zbl

[9] Anderson J. A., Automata Theory with Modern Applications, Cambridge University Press, 2006 | MR

[10] Bollobas B., Modern Graph Theory, Springer, 1998 | MR | Zbl

[11] Sapunov S. V., “Checking of deterministic graphs”, Transaction of IAMM NASU, 8 (2003), 106–110 (in Russian) | MR | Zbl

[12] Moore E. F., Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, Princeton University Press, 1956 | MR

[13] Cormen T. H., Leiserson Ch. E., Rivest R. L., Introduction to Algorithms, McGraw-Hill Higher Education, 2001