The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs | ||
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.contributor.author | Dobson, Maria Patricia | |
| dc.contributor.author | Leoni, Valeria Alejandra | |
| dc.contributor.author | Nasini, Graciela Leonor | |
| dc.date.issued | 2010-08 | |
| dc.description.abstract | The notion of k-limited packing in a graph is a generalization of 2-packing. For a given non negative integer k, a subset B of vertices is a k-limited packing if there are at most k elements of B in the closed neighborhood of every vertex. On the other side, a k-tuple domination set in a graph is a subset of vertices D such that every vertex has at least k elements of D in its closed neighborhood. In this work we first reveal a strong relationship between these notions, and obtain from a result due to Liao and Chang (2002), the polynomiality of the k-limited packing problem for strongly chordal graphs.We also prove that, in coincidence with the case of domination, the k-limited packing problem is NP-complete for split graphs. Finally, we prove that both problems are polynomial for the non-perfect class of P4-tidy graphs, including the perfect classes of P4-sparse graphs and cographs. | es |
| dc.description.fil | Fil: Dobson, Maria Patricia. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Dobson, Maria Patricia; Leoni, Valeria Alejandra; Nasini, Graciela Leonor; The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs; Elsevier Science; Electronic Notes in Discrete Mathematics; 36; C; 8-2010; 559-566 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 1571-0653 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/100300 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | C | es |
| dc.journal.pagination | 559-566 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Electronic Notes in Discrete Mathematics | es |
| dc.journal.volume | 36 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.endm.2010.05.071 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S1571065310000727 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | COMPUTATIONAL COMPLEXITY | es |
| dc.subject | K-LIMITED PACKING | es |
| dc.subject | K-TUPLE DOMINATING SET | es |
| dc.subject | P4-TIDY GRAPHS | es |
| dc.subject | SPLIT GRAPHS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.14dfe7ea-7383-4f1e-ab8f-5b0b170cee95_A.pdf
- Tamaño:
- 199.62 KB
- Formato:
- Adobe Portable Document Format