Complexity properties of complementary prisms

Marcio Antônio Duarte (), Lucia Penso (), Dieter Rautenbach () and Uéverton Santos Souza ()
Additional contact information
Marcio Antônio Duarte: Universidade Federal de Goiás
Lucia Penso: Universität Ulm
Dieter Rautenbach: Universität Ulm
Uéverton Santos Souza: Universidade Federal Fluminense

Journal of Combinatorial Optimization, 2017, vol. 33, issue 2, No 1, 365-372

Abstract: Abstract The complementary prism $$G\bar{G}$$ G G ¯ of a graph G arises from the disjoint union of the graph G and its complement $$\bar{G}$$ G ¯ by adding the edges of a perfect matching joining pairs of corresponding vertices of G and $$\bar{G}$$ G ¯ . Haynes, Henning, Slater, and van der Merwe introduced the complementary prism and as a variation of the well-known prism. We study algorithmic/complexity properties of complementary prisms with respect to cliques, independent sets, k-domination, and especially $$P_3$$ P 3 -convexity. We establish hardness results and identify some efficiently solvable cases.

Keywords: Complementary prism; Clique; Independent set; k-Domination; $$P_3$$ P 3 -Convexity (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9968-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:2:d:10.1007_s10878-015-9968-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9968-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().