کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436590 | 690017 | 2014 | 7 صفحه PDF | دانلود رایگان |
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)G(R)□H(S) is defined as the graph with vertex set V(G)×V(H)V(G)×V(H) where two vertices (u,v)(u,v) and (x,y)(x,y) are adjacent exactly if either u=xu=x, u∈Ru∈R, and vy∈E(H)vy∈E(H); or u=xu=x, u∈V(G)∖Ru∈V(G)∖R, and vy∉E(H)vy∉E(H); or v=yv=y, v∈Sv∈S, and ux∈E(G)ux∈E(G); or v=yv=y, v∈V(H)∖Sv∈V(H)∖S, and ux∉E(G)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)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].
Journal: Theoretical Computer Science - Volume 521, 13 February 2014, Pages 1–7