Aspire Faculty ID #19223 · Topic: UGC NET Computer Science June 2019 (Paper II) · Just now
UGC NET Computer Science June 2019 (Paper II)

For which values of $m$ and $n$ does the complete bipartite graph $K_{m,n}$ have a Hamilton circuit?

Solution

In a complete bipartite graph $K_{m,n}$, vertices are divided into two parts.

A Hamilton circuit must visit every vertex exactly once and return to the starting vertex.

In a bipartite graph, every cycle alternates between the two parts.

So, for a Hamilton circuit to include all vertices, both parts must have the same number of vertices.

Therefore,

$m=n$

Also, a cycle needs at least $2$ vertices in each part.

So,

$m,n \ge 2$

Hence, $K_{m,n}$ has a Hamilton circuit when

$m=n,\ m,n \ge 2$

Previous 10 Questions — UGC NET Computer Science June 2019 (Paper II)

Nearest first

Next 10 Questions — UGC NET Computer Science June 2019 (Paper II)

Ascending by ID
1
Which of the following is principal conjunctive normal form for $[(p \vee q)\wedge[p \to q]]$?
Topic: UGC NET Computer Science June 2019 (Paper II)
2
How many cards must be selected from a standard deck of $52$ cards to guarantee that at least three hearts are present …
Topic: UGC NET Computer Science June 2019 (Paper II)
3
List-I List-II (a) $p \to q$ (i) $\neg(q \to \neg p)$ …
Topic: UGC NET Computer Science June 2019 (Paper II)
4
Find the zero-one matrix of the transitive closure of the relation given by the matrix $A$:
Topic: UGC NET Computer Science June 2019 (Paper II)
5
Consider an LPP given as: $\text{Max } Z=2x_1-x_2+2x_3$ subject to the constraints: $2x_1+x_2\le 10$ $x_1+2x_2-2x_3\le …
Topic: UGC NET Computer Science June 2019 (Paper II)
6
Which type of addressing mode requires the least number of memory references?
Topic: UGC NET Computer Science June 2019 (Paper II)
7
Suppose that the register $A$ and the register $K$ have the bit configuration. Only the three leftmost bits of $A$ are …
Topic: UGC NET Computer Science June 2019 (Paper II)
8
How many different Boolean functions of degree $n$ are there?
Topic: UGC NET Computer Science June 2019 (Paper II)
9
The fault can be easily diagnosed in the micro-program control unit using diagnostic tools by maintaining the contents …
Topic: UGC NET Computer Science June 2019 (Paper II)
10
What will be the number of states when a $MOD-2$ counter is followed by a $MOD-5$ counter?
Topic: UGC NET Computer Science June 2019 (Paper II)
Ask Your Question or Put Your Review.

loading...