Name
Abstract | ||
|---|---|---|
For two graphs G and H, a set R of vertices of G, and a set S of vertices of H, the complementary product G(R)@?H(S) is defined as the graph with vertex set V(G)xV(H) where two vertices (u,v) and (x,y) are adjacent exactly if either u=x, u@?R, and vy@?E(H); or u=x, u@?V(G)@?R, and vy@?E(H); or v=y, v@?S, and ux@?E(G); or v=y, v@?V(H)@?S, and ux@?E(G). We show that for a fixed connected graph H and a fixed non-empty and proper subset S of its vertex set, it can be decided in polynomial time whether, for a given input graph F, there exists a graph G such that F is isomorphic to G(V(G))@?H(S). Furthermore, if such a graph G exists, then one such graph can be found in polynomial time. Our result gives a positive answer to a question posed by Haynes, Henning, Slater, and van der Merwe [5]. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2013.11.006 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
positive answer,fixed non-empty,graphs G,input graph F,vertex set,polynomial time,graph G,set R,complementary product,fixed connected graph H | Journal | 521, |
ISSN | Citations | PageRank |
0304-3975 | 3 | 0.50 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Márcia R. Cappelle | 1 | 3 | 2.19 |
| Lucia Draque Penso | 2 | 196 | 20.46 |
| Dieter Rautenbach | 3 | 946 | 138.87 |