1
GATE CSE 2007
+2
-0.6
Which of the following graphs has an Eulerian circuit?
A
Any $$k$$-regular graph where $$k$$ is an even number.
B
A complete graph on 90 vertices.
C
The complement of a cycle on 25 vertices.
D
None of the above.
2
GATE CSE 2006
+2
-0.6
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets intersect in exactly two elements.

the number of vertices of degree zero in $$G$$ is

A
$$1$$
B
$$n$$
C
$$n + 1$$
D
$${2^n}$$
3
GATE CSE 2006
+2
-0.6
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in $$G$$ is

A
$$\left( {\mathop 2\limits^{n/2} } \right){2^{n/2}}$$
B
$${2^{n - 2}}$$
C
$${2^{n - 3}} \times 3$$
D
$${2^{n - 1}}$$
4
GATE CSE 2006
+2
-0.6
Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have an edge between vertex $$u$$ and vertex $$v$$ if and only if $$u$$ and $$v$$ differ in exactly one bit position (in other words, $$v$$ can be obtained from $$u$$ by flipping a single bit). The ratio of the choromatic number of $$G$$ to the diameter of $$G$$ is
A
$$1/{2^{n - 1}}$$
B
$$1/n$$
C
$$2/n$$
D
$$3/n$$
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination