Name
Abstract | ||
|---|---|---|
The complementary prism $$G\\bar{G}$$GG¯ 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$$P3-convexity. We establish hardness results and identify some efficiently solvable cases. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s10878-015-9968-5 | J. Comb. Optim. |
Keywords | DocType | Volume |
Complementary prism,Clique,Independent set,k,-Domination,\(P_3\),-Convexity | Journal | 33 |
Issue | ISSN | Citations |
2 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| marcio antonio duarte | 1 | 0 | 0.34 |
| Lucia Draque Penso | 2 | 196 | 20.46 |
| Dieter Rautenbach | 3 | 946 | 138.87 |
| Uéverton S. Souza | 4 | 20 | 21.12 |