Trahtenbrot-Zykov problem and NP-completeness

✍ Scribed by Peter Bugata

• Book ID: 103060999
• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 419 KB
• Volume: 108
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90679-a

✦ Synopsis

Bugata, P., Trahtenbrot-Zykov problem and NP-completeness, Discrete Mathematics 108 (1992) 253-259. Zykov [5] posed a problem now known as the Trahtenbrot-Zykov problem: Given a finite graph H, does there exist a non-empty graph G with all neighbourhoods of its vertices isomorphic to H? This problem is algorithmically unsolvable in the class of all graphs but there exists a polynomial-time algorithm for trees. In the present paper we show that there exists a class of graphs in which the Trahtenbrot-Zykov problem is NP-complete.