Select all that are true (note that incorrect answers are penalized): Select one

ID: 3909255 • Letter: S

Question

Select all that are true (note that incorrect answers are penalized):

Select one or more:

A. With optimization version of the IS problem, the goal is to minimize the size of the IS.

B. A graph has a clique of size k, if the complement graph has an independent set of size n?k.

C. A graph has a clique of size k, if the complement graph has vertex cover of size n?k.

D. The length of the Hamiltonian path in a graph with n vertices is n

E. If a Hamiltonian path exists then a Hamiltonian cycle exists as well.

F. If a node is in the IS then none of its adjacent nodes are in the IS.

G. In the minimum vertex cover, every edge is covered only once.

H. Dominating set must cover every edge at least once

I. If the size of the IS in graph G(n,m) is n, then m=0.

J. If every vertex in the graph is of degree 5 or less then the maximum clique size is no larger than 6.

K. The longest path problem is easier to solve than the shortest path problem.

L. If a k-clique in graph G is known, then the vertex cover in G will be of size n?k.

The followings are true :

C. A graph has a clique of size k, if the complement graph has vertex cover of size n?k.

D. The length of the Hamiltonian path in a graph with n vertices is n

E. If a Hamiltonian path exists then a Hamiltonian cycle exists as well.

L. If a k-clique in graph G is known, then the vertex cover in G will be of size n?k.

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.