Page 698 - Discrete Mathematics and Its Applications

10.3 Representing Graphs and Graph Isomorphism 677

41. u 1 u 2 u 3 u 5 u 6 u 8 has the form

0 A
,
B 0
u 4 u 7
where the four entries shown are rectangular blocks.
v 1 v 2 v 4 v 5 v 6 v 8
A simple graph G is called self-complementary if G and G
are isomorphic.
50. Show that this graph is self-complementary.
v 3 v 7
a b
42. u 6 u 7

u 1 u 2 u 3 u 4 u 5

d c
51. Find a self-complementary simple graph with five ver-
u 8 u 9 u 10 tices.
v 6 v 7 ∗ 52. Show that if G is a self-complementary simple graph
with v vertices, then v ≡ 0 or 1 (mod 4).

v 1 v 2 v 3 v 4 v 5 53. For which integers n is C n self-complementary?
54. How many nonisomorphic simple graphs are there with n
vertices, when n is
a) 2? b) 3? c) 4?
v 8 v 9 v 10 55. How many nonisomorphic simple graphs are there with
43. u 2 v 2 five vertices and three edges?
56. How many nonisomorphic simple graphs are there with
u 9 v 1 v 8 v 3 six vertices and four edges?
u 1 u 10 u 8 u 3
v 10 57. Are the simple graphs with the following adjacency ma-
trices isomorphic?
u 7 v 6 v v v
u 6 7 9 4 a) ⎡ 0 0 1 ⎤ ⎡ 0 1 1 ⎤
0 0 ⎦ 1 0 0 ⎦
⎣
u 5 u 4 v 5 1 1 1 , ⎣ 1 0 0
0
44. u 1 v 1 b) ⎡ 0 1 0 1 ⎤ ⎡ 0 1 1 1 ⎤
u 8 u 2 v 8 v 2 ⎢ 1 0 0 1 ⎥ ⎢ 1 0 0 1 ⎥
⎢
⎥ ⎢
⎥
,
⎣ 0 0 0 1 ⎦ ⎣ 1 0 0 1 ⎦
1 1 1 0 1 1 1 0
u 7 u 3 v 7 v 3 ⎡ ⎤ ⎡ ⎤
c) 0 1 1 0 0 1 0 1
⎢ 1 0 0 1 ⎥ ⎢ 1 0 0 ⎥
⎢
⎥ ⎢
,
u 6 u 4 v 6 v 4 ⎣ 1 0 0 1 ⎦ ⎣ 0 0 0 0 ⎥
1
⎦
u 5 v 5 0 1 1 0 1 0 1 0
58. Determine whether the graphs without loops with these
45. Show that isomorphism of simple graphs is an equiva- incidence matrices are isomorphic.
lence relation. ⎡ ⎤ ⎡ ⎤
a) 1 0 1 1 1 0
46. Suppose that G and H are isomorphic simple graphs. ⎣ 0 1 1 , ⎣ 1 0 1 ⎦
⎦
Show that their complementary graphs G and H are also 1 1 0 0 1 1
isomorphic. ⎡ ⎤ ⎡ ⎤
b) 1 1 0 0 0 0 1 0 0 1
47. Describe the row and column of an adjacency matrix of ⎢ 1 0 1 0 1 ⎥ ⎢ 0 1 1 1 ⎥
⎥ ⎢
⎢
a graph corresponding to an isolated vertex. , 0 ⎥
0 0 0 1 1 ⎦ ⎣ 1 0 0 1 0 ⎦
⎣
48. Describe the row of an incidence matrix of a graph cor- 0 1 1 1 0 1 0 1 0 1
responding to an isolated vertex. 59. Extend the definition of isomorphism of simple graphs to
49. Show that the vertices of a bipartite graph with two or undirected graphs containing loops and multiple edges.
more vertices can be ordered so that its adjacency matrix 60. Define isomorphism of directed graphs.