Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms

DOI10.1142/S0129054121500027zbMath1458.68074OpenAlexW3119765340MaRDI QIDQ5859672

Priscila P. Camargo, Uéverton S. Souza, Julliano Rosa Nascimento

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054121500027

zbMATH Keywords

independent setkernelcliquecomplementary prisms\( P_3\)-hull2-contamination

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers

Cites Work

• Recognizing some complementary products
• Complexity properties of complementary prisms
• Irreversible conversion of graphs
• Domination and total domination in complementary prisms
• Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• On the geodetic number of complementary prisms
• \(P_3\)-hull number of graphs with diameter two
• Cycles in complementary prisms
• Parametrized complexity theory.
• Co-Nondeterminism in Compositions
• Parameterized Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms