91Ó°ÊÓ

For each integer \(n \geq 2\), determine a tree of order \(n\) whose domination number equals \(\lfloor n / 2]\).

Determine the domination number of the graph \(Q_{3}\) of vertices and edges of a three-dimensional cube.

Determine the domination number of a cycle graph \(C_{n}\).

Prove that an induced subgraph of a chordal graph is chordal.

Prove that all bipartite graphs are perfect.

Let \(k\) be a positive integer, and let \(G\) be a bipartite graph in which every vertex has degree \(k\). (a) Prove that \(G\) has a perfect matching. (b) Prove that the edges of \(G\) can be partitioned into \(k\) perfect matchings.

Consider the graph \(Q_{n}\) of vertices and edges of the \(n\) -dimensional cube. Usiny. induction, (a) Prove that \(Q_{n}\) has a perfect matching for each \(n \geq 1\). (b) Prove that \(Q_{n}\) has at least \(2^{2^{n-2}}\) perfect matchings.

Prove that if a tree has a perfect matching, then it has exactly one perfer-1 matching.

Let \(G\) be a graph of order \(n\) in which every vertex has degree equal to \(d\). (a) How large must \(d\) be in order to guarantee that \(G\) is connected? (b) How large must \(d\) be in order to guarantee that \(G\) is 2-connected?