Publication at Faculty of Mathematics and Physics |
2008
Abstract
In this paper, we show the NP-completeness of the problem to determine if a given graph is switching-equivalent to a graph containing a clique whose size is at least a constant fraction of the graph size. We also prove the NP-completeness of deciding if a given graph is switching-equivalent to a graph having at least a given number of edges.