Algorithmic aspects of \(\{P_k\}\)-isolation in graphs and extremal graphs for a \(\{P_3\}\)-isolation bound

DOI10.1016/j.ipl.2024.106521zbMATH Open1547.0522MaRDI QIDQ6602332

Shou-Jun Xu, Jie Chen, Yi-Ping Liang, Cai-Xia Wang

Publication date: 11 September 2024

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

extremal graphsNP-completenessdomination\(\mathcal{F}\)-isolation number

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• A survey of selected recent results on total domination in graphs
• Independent domination in graphs: A survey and recent results
• Isolation of cycles
• Isolation of \(k\)-cliques
• Partial domination of maximal outerplanar graphs
• \( K_{1 , 2}\)-isolation in graphs
• Isolation number of maximal outerplanar graphs
• Extensions of the Art Gallery Theorem
• Dominating Sets in Chordal Graphs
• Partial domination - the isolation number of a graph
• Isolation of connected graphs

This page was built for publication: Algorithmic aspects of \(\{P_k\}\)-isolation in graphs and extremal graphs for a \(\{P_3\}\)-isolation bound