Igor Grunsky, Irina Mikhaylova, Sergey Sapunov, “Domination on the vertices of labeled graphs”, Algebra Discrete Math., 2012, Volume 14, Issue 2,Pages <nobr>174

RESEARCH ARTICLE

Domination on the vertices of labeled graphs

Igor Grunsky^a, Irina Mikhaylova^b, Sergey Sapunov^a

^a 83114, Ukraine, Donetsk, Rozy Luxemburg street, 74, IAMM NASU
^b Lugansk Taras Shevchenko National University, UKRAINE

Abstract: 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.

MSC: 68Q45, 68R10

Received: 21.11.2012
Accepted: 21.11.2012

Language: English