Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
V tomto článku dokazujeme NP-úplnost problému, zda je daný graf ekvivalentní v přepnutí grafu obsahujícímu kliku, která je aspoň konstantně velká vzhledem k velikosti celého grafu. Dokazujeme také NP-úplnost problému, zda je daný graf ekvivalentní v přepnutí grafu, který má aspoň určitý počet hran.