Consider the simple graph with degree sequence {7, 3, 3, 3, 3, 3, 3, 3 }, If x be cardinality of largest independance set and y be cardinality of the minimum vertex cover, then the x $\times$ y is_________.
15

Open in App

Solution

The correct option is A 15
With given degree sequence, sample graph will be

Independence set or stable set is a set of vertices in a graph , no two of which are adjacent
So, largest independence set is |{a, d, f}| =3
We know that,
Total vertex = Largest independence set +Minimal vertex cover
8 = 3 + y
y = 5
$S o, x \times y = 5 \times 3 = 15$

Suggest Corrections

Similar questions

\frac{2 x + 3}{3} \geq \frac{3 x - 1}{4}

Find the cardinal number of the following sets :

(i) $A_{1} = {- 2, - 1, 1, 3, 5}$

(ii) $A_{2} = {x : x \in N a n d 3 \leq x < 7}$

(iii) $A_{3} = {p : p \in W a n d 2 p - 3 < 8}$

(iv) $A_{4} = {b : b \in Z a n d - 7 < 3 b - 1 \leq 2}$ $Cardinal~Number~of~set~:The number of elements in a set is called its Cardinal Number.$

\cup

A

4

B

3

A Δ B

Solve the following inequation and find the cardinality of the solution set.

$\frac{2 x + 3}{3} \geq \frac{3 x - 1}{4}$ where x is positive even integer.

Join BYJU'S Learning Program