- Computer Science Engineering (CSE)
- Theory of Computation
- Unit 1
- A Hamiltonian cycle in a Hamiltonian gra...

Q. |
## A Hamiltonian cycle in a Hamiltonian graph of order 24 has |

A. | 12 edges. |

B. | 24 edges |

C. | 23 edges |

D. | None of above. |

Answer» B. 24 edges |

View all MCQs in:
Theory of Computation

- Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is
- Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
- Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?
- Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
- A spanning tree for a simple graph of order 24 has
- Any given transition graph has an equivalent:
- If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
- If G is a connected planar graph of v vertices e edges and r regions then
- If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
- = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?

Login to Continue

It will take less than 2 minutes

Report MCQ