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

DOI10.1016/J.ENDM.2010.05.071MaRDI QIDQ2883613zbMATH OpenOpenAlexFDO

Authors V. Leoni, M. P. Dobson, G. 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)

Recommendations

• scientific article; zbMATH DE number 6837043
• $$\{k\}$$-Packing Functions of Graphs
• Limited Packings in Graphs
• The multiple domination and limited packing problems in graphs
• Limited packings in graphs

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• A tree representation for \(P_ 4\)-sparse graphs
• Algorithmic aspect of k-tuple domination in graphs.
• Domination, independent domination, and duality in strongly chordal graphs
• Limited Packings in Graphs
• Recognizing P₄ -Sparse Graphs in Linear Time
• Totally-Balanced and Greedy Matrices
• \(k\)-tuple domination in graphs

Cited in

(10)

• Limited packings: related vertex partitions and duality issues
• Labelled packing functions in graphs
• Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
• On the complexity of the {\(k\)}-packing function problem
• Limited packing and multiple domination problems: polynomial time reductions
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs
• NP-completeness of the \(\{k \}\)-packing function problem in graphs
• Polynomial reductions between the limited packing and tuple domination problems in graphs
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• The multiple domination and limited packing problems in graphs

This page was built for publication: The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2883613)