Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

192 GRAPH THEORY [CHAP. 8

Fig. 8-59

SPECIAL GRAPHS

8.48. Draw two 3-regular graphs with: (a) eight vertices; (b) nine vertices.

8.49. Consider the complete graphKn.

(a) Find the diameter ofKn.

(b) Find the numbermof edges inKn.

(c) Find the degree of each vertex inKn.

(d) Find those values ofnfor whichKnis: (i) traversable; (ii) regular.

8.50. Consider the complete graphKm,n.

(a) Find the diameter ofKm,n.

(b) Find the numberEof edges inKm,n.

(c) Find thoseKm,nwhich are traversable.

(d) Which of the graphsKm,nare isomorphic and which homeomorphic?

8.51. Then-cube, denoted byQn, is the graph whose vertices are the 2nbit strings of lengthn, and where two vertices are

adjacent if they differ in only one position. Figure 8-60(a)and(b)show then-cubesQ 2 andQ 3.

(a) Find the diameter ofQn.

(b) Find the numbermof edges inQn.

(c) Find the degree of each vertex inQn.

(d) Find those values ofnfor whichQnis traversable.

(e) Find a Hamiltonian circuit (called aGray code) for (i)Q 3 ; (ii)Q 4.

Fig. 8-60