2019-04-29
1. On an n+1 graph, pick one vertex and have all the other vertexes connect to it.
2. The complement of G can be computed in polynomial time. Since this is one-to-one and onto, the reduction is one-to-one and onto, which makes it p-time isomorphism.
3. A CLIQUe of size n would map to the above graphs
1. On an n+1 graph, pick one vertex and have all the other vertexes connect to it.
2. The complement of G can be computed in polynomial time. Since this is one-to-one and onto, the reduction is one-to-one and onto, which makes it p-time isomorphism.
3. A CLIQUe of size n would map to the above graphs
2019-05-14
1) for any n >=1 , add one more vertex that is connected to all n many vertices, and such a graph will have vertex cover of size 1 ; 2) for the reduction from CLIQUE to VERTEX-COVER to work, it takes a) complement of original G, and b) compute the vertex-cover size of |V|-k for this complement graph in a). Given an adjacent matrix, finding complement graph of G can be completed in polynomial time or O(n^2), so can its vertex-cover with size of |V|-k. All in all, this is p-time isomorphism; 3) Clique size of n for |V| = n + 1 will map to this graph.
(Edited: 2019-05-14) 1) for any n >=1 , add one more vertex that is connected to all n many vertices, and such a graph will have vertex cover of size 1 ; 2) for the reduction from CLIQUE to VERTEX-COVER to work, it takes a) complement of original G, and b) compute the vertex-cover size of |V|-k for this complement graph in a). Given an adjacent matrix, finding complement graph of G can be completed in polynomial time or O(n^2), so can its vertex-cover with size of |V|-k. All in all, this is p-time isomorphism; 3) Clique size of n for |V| = n + 1 will map to this graph.
(c) 2024 Yioop - PHP Search Engine