Grundy dominating sequences on X-join product
| Autor: | Pablo Daniel Torres, Graciela L. Nasini |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Matemáticas
Domination analysis 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences purl.org/becyt/ford/1 [https] Combinatorics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Split graph Otras Matemáticas Time complexity Mathematics POWERS OF PATHS Applied Mathematics purl.org/becyt/ford/1.1 [https] 021107 urban & regional planning Lexicographical order Graph POWERS OF CYCLES 010201 computation theory & mathematics Independent set X-JOIN PRODUCT Combinatorics (math.CO) GRUNDY DOMINATING SEQUENCES SPLIT GRAPHS CIENCIAS NATURALES Y EXACTAS |
| Zdroj: | CONICET Digital (CONICET) Consejo Nacional de Investigaciones Científicas y Técnicas instacron:CONICET |
| ISSN: | 0166-218X |
| Popis: | In this paper we study the Grundy domination number on the X-join product G↩R of a graph G and a family of graphs R={Gv:v∈V(G)}. The results led us to extend the few known families of graphs where this parameter can be efficiently computed. We prove that if, for all v∈V(G), the Grundy domination number of Gv is given, and G is a power of a cycle, a power of a path, or a split graph, computing the Grundy domination number of G↩R can be done in polynomial time. In particular, our results for powers of cycles and paths are derived from a polynomial reduction to the Maximum Weight Independent Set problem on these graphs. As a consequence, we derive closed formulas to compute the Grundy domination number of the lexicographic product G∘H when G is a power of a cycle, a power of a path or a split graph, generalizing the results on cycles and paths given by Brešar et al. in 2016. Moreover, our results on the X-join product when G is a split graph also provide polynomial-time algorithms to compute the Grundy domination number for (q,q−4) graphs, partner limited graphs and extended P4-laden graphs, graph classes that are high in the hierarchy of few P4’s graphs. Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Torres, Pablo. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect