The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs

DOI10.1016/j.endm.2010.05.071zbMath1236.05144OpenAlexW1984732309MaRDI QIDQ2883613

V. Leoni, Maria Patricia Dobson, Graciela L. Nasini

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.071

zbMATH Keywords

computational complexitysplit graphs\(P_{4}\)-tidy graphs\(k\)-limited packing\(k\)-tuple dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

NP-completeness of the \(\{k \}\)-packing function problem in graphs ⋮ The multiple domination and limited packing problems in graphs ⋮ On the complexity of the {k}-packing function problem ⋮ Limited packing and multiple domination problems: polynomial time reductions ⋮ Labelled packing functions in graphs ⋮ Towards a Polynomial Equivalence Between $$\{k\}$$ -Packing Functions and k-Limited Packings in Graphs ⋮ Polynomial reductions between the Limited Packing and Tuple Domination problems in graphs ⋮ Generalized limited packings of some graphs with a limited number of \(P_4\)-partners

Cites Work

• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• \(k\)-tuple domination in graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Limited Packings in Graphs
• Totally-Balanced and Greedy Matrices
• Recognizing $P_4 $-Sparse Graphs in Linear Time

This page was built for publication: The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs