Solution: A dominating set of vertices in a simple graph is

a) Define a simple graph, a multigraph, a pseudograph, a directed graph, and a directed multigraph. b) Use an example to show how each of the types of graph in part (a) can be used in modeling. For example,explain how to model different aspects of a computer network or airline routes.

Give at least four examples of how graphs are used in modeling.

What is the relationship between the sum of the degrees of the vertices in an undirected graph and the number of edges in this graph? Explain why this relationship holds.

Why must there be an even number of vertices of odd degree in an undirected graph?

What is the relationship between the sum ofthe in-degrees and the sum of the out-degrees ofthe vertices in a directed graph? Explain why this relationship holds.

Describe the following families of graphs. a) Kn, the complete graph on n vertices b) K m.n, the complete bipartite graph on m and n vertices c) en, the cycle with n vertices d) Wn, the wheel of size n e) Qn, the n-cub

How many vertices and how many edges are there in each of the graphs in the families in Question 6?

a) What is a bipartite graph? b) Which of the graphs Kn, en, and Wn are bipartite? c) How can you determine whether an undirected graph is bipartite?

a) Describe three different methods that can be used to represent a graph. b) Draw a simple graph with at least five vertices and eight edges. Illustrate how it can be represented using the methods you described in part (a).

a) What does it mean for two simple graphs to be isomorphic? b) What is meant by an invariant with respect to isomorphism for simple graphs? Give at least five examples of such invariants. c) Give an example of two graphs that have the same numbers of vertices, edges, and degrees of vertices, but that are not isomorphic. d) Is a set of invariants known that can be used to efficiently determine whether two simple graphs are isomorphic?

a) What does it mean for a graph to be connected? b) What are the connected components of a graph?

a) Explain how an adjacency matrix can be used to represent a graph. b) How can adjacency matrices be used to determine whether a function from the vertex set of a graph G to the vertex set of a graph H is an isomorphism? c) How can the adjacency matrix of a graph be used to determine the number of paths of length r, where r is a positive integer, between two vertices of a graph?

a) Define an Euler circuit and an Euler path in an undirected graph. b) Describe the famous Konigsberg bridge problem and explain how to rephrase it in terms of an Euler circuit. c) How can it be determined whether an undirected graph has an Euler path? d) How can it be determined whether an undirected graph has an Euler circuit?

a) Define a Hamilton circuit in a simple graph. b) Give some properties of a simple graph that imply that it does not have a Hamilton circuit.

Give examples of at least two problems that can be solved by finding the shortest path in a weighted graph.

a) Describe Dijkstra's algorithm for finding the shortest path in a weighted graph between two vertices. b) Draw a weighted graph with at least 1 0 vertices and 20 edges. Use Dijkstra's algorithm to find the shortest path between two vertices of your choice in the graph.

a) What does it mean for a graph to be planar? b) Give an example of a nonplanar graph.

a) What is Euler's formula for planar graphs? b) How can Euler's formula for planar graphs be used to show that a simple graph is nonplanar?

State Kuratowski's Theorem on the planarity of graphs and explain how it characterizes which graphs are planar.

a) Define the chromatic number of a graph. b) What is the chromatic number of the graph Kn when n is a positive integer? c) What is the chromatic number of the graph en when n is a positive integer greater than 2? d) What is the chromatic number ofthe graph Kmn when m and n are positive integers?

State the Four Color Theorem. Are there graphs that cannot be colored with four colors?

Explain how graph coloring can be used in modeling. Use at least two different examples.

How many edges does a 50-regular graph with 1 00 vertices have?

How many nonisomorphic subgraphs does K3 have?

In Exercises 3-5 determine whether the given pair of graphs is isomorphic.

In Exercises 3-5 determine whether the given pair of graphs is isomorphic.

In Exercises 3-5 determine whether the given pair of graphs is isomorphic.

Draw these graphs. a) K],2,3 b) K2,2,2 c) K1 ,2,2,

How many vertices and how many edges does the complete m-partite graph Knl ,nz, ... ,nm have?

a) Prove or disprove that there are always two vertices with the same degree in a finite simple graph having at least two vertices. b) Do the same as in part (a) for finite multigraphs.

Consider the graph shown in Figure 3 of Section 9.4. Find the sub graphs induced by a) {a , b, c} , b) {a , e, g}. c) {b, c, f, g, h}.

Let n be a positive integer. Show that a subgraph induced by a nonempty subset of the vertex set of Kn is a complete graph.

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. In Exercises 1 1-1 3 find all cliques in the graph shown.

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. In Exercises 1 1-1 3 find all cliques in the graph shown.

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. In Exercises 1 1-1 3 find all cliques in the graph shown.

A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. In Exercises 14-16 find a minimum dominating set for the given graph.

A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. In Exercises 14-16 find a minimum dominating set for the given graph.

A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. In Exercises 14-16 find a minimum dominating set for the given graph.

Construct the simple graph representing the n x n chessboard with edges representing the control of squares by queens for a) n = 3 . b) n = 4.

Explain how the concept of a minimum dominating set applies to the problem of determining the minimum number of queens controlling an n x n chessboard.

Find the minimum number ofqueens controlling an n x n chessboard for a) n = 3 . b) n = 4. c) n = 5.

Suppose that G I and HI are isomorphic and that Gz and Hz are isomorphic. Prove or disprove that G I U Gz and HI U Hz are isomorphic.

Show that each of these properties is an invariant that isomorphic simple graphs either both have or both do not have. a) connectedness b) the existence of a Hamilton circuit c) the existence of an Euler circuit d) having crossing number C e) having n isolated vertices t) being bipartite

How can the adjacency matrix of G be found from the adjacency matrix of G, where G is a simple graph?

How many nonisomorphic connected bipartite simple graphs are there with four vertices?

How many nonisomorphic simple connected graphs with five vertices are there a) with no vertex of degree more than two? b) with chromatic number equal to four? c) that are nonplanar?

Determine whether the following graphs are selfconverse. a) a b d b) a b c d

Show that if the directed graph G is self-converse and H is a directed graph isomorphic to G, then H is also self-converse.

An orientation of an undirected simple graph is an assignment of directions to its edges such that the resulting directed graph is strongly connected. When an orientation of an undirected graph exists, this graph is called orientable. In Exercises 27- 29 determine whether the given simple graph is orientable.

An orientation of an undirected simple graph is an assignment of directions to its edges such that the resulting directed graph is strongly connected. When an orientation of an undirected graph exists, this graph is called orientable. In Exercises 27- 29 determine whether the given simple graph is orientable.

An orientation of an undirected simple graph is an assignment of directions to its edges such that the resulting directed graph is strongly connected. When an orientation of an undirected graph exists, this graph is called orientable. In Exercises 27- 29 determine whether the given simple graph is orientable.

Because traffic is growing heavy in the central part of a city, traffic engineers are planning to change all the streets, which are currently two-way, into one-way streets. Explain how to model this problem

Show that a graph is not orientable if it has a cut edge. A tournament "is a simple directed graph such that if u and v are distinct vertices in the graph, exactly one of (u, v) and (v, u) is an edge of the graph.

How many different tournaments are there with n vertices?

What is the sum ofthe in-degree and out-degree of a vertex in a tournament?

Show that every tournament has a Hamilton path.

Given two chickens in a flock, one of them is dominant. This defines the pecking order of the flock. How can a tournament be used to model pecking order?

Suppose that G is a connected multigraph with 2k vertices of odd degree. Show that there exist k subgraphs that have G as their union, where each of these subgraphs has an Euler path and where no two of these subgraphs have an edge in common. [Hint: Add k edges to the graph connecting pairs of vertices of odd degree and use an Euler circuit in this larger graph.]

Let G be a simple graph with n vertices. The band width of G, denoted by B(G), is the minimum, over all permutations, a i , a2 , ... , an of the vertices of G, of max{li - j l l ai and aj are adjacent} . That is, the band 1)-1)2 width is the minimum over all listings of the vertices of the maximum difference in the indices assigned to adjacent vertices. Find the band widths of these graphs. a) Ks b) K1 ,3 c) K2,3 d) K3,3 e) Q3 t) CS

The distance between two distinct vertices VI and V2 of a connected simple graph is the length (number of edges) of the shortest path between VI and V2 . The radius of a graph is the minimum overall vertices v of the maximum distance from v to another vertex. The diameter of a graph is the maximum distance between two distinct vertices. Find the radius and diameter of a) K6. b) K4,S' c) Q3. d) C6.

a) Show that if the diameter of the simple graph G is at least four, then the diameter of its complement G is no more than two. b) Show that if the diameter of the simple graph G is at least three, then the diameter of its complement G is no more than three.

Suppose that a multigraph has 2m vertices of odd degree. Show that any circuit that contains every edge of the graph must contain at least m edges more than once

Find the second shortest path between the vertices a and z in Figure 3 of Section 9.6.

Devise an algorithm for finding the second shortest path between two vertices in a simple connected weighted graph.

Find the shortest path between the vertices a and z that passes through the vertex e in the weighted graph in Figure 4 in Section 9.6.

Devise an algorithm for finding the shortest path between two vertices in a simple connected weighted graph that passes through a specified third vertex.

Show that if G is a simple graph with at least 11 vertices, then either G or G, the complement of G, is nonplanar.

What is the independence number of a) Kn? b) Cn? c) Qn? d) Km,n ?

Show that the number of vertices in a simple graph is less than or equal to the product of the independence number and the chromatic number of the graph.

Show that the chromatic number of a graph is less than or equal to v - i + 1, where v is the number of vertices in the graph and i is the independence number of this graph.

Suppose that to generate a random simple graph with n vertices we first choose a real number p with 0 p 1. For each of the C(n , 2) pairs of distinct vertices we generate a random number x between 0 and 1. If 0 x p, we connect these two vertices with an edge; otherwise these vertices are not connected. a) What is the probability that a graph with m edges where 0 ::: m ::: C(n , 2) is generated? b) What is the expected number of edges in a randomly generated graph with n vertices if each edge is included with probability p? c) Show that if p = 1 /2 then every simple graph with n vertices is equally likely to be generated.

For each of these properties, determine whether it is monotone increasing and determine whether it is monotone decreasing a) The graph G is connected. b) The graph G is not connected. c) The graph G has an Euler circuit. d) The graph G has a Hamilton circuit. e) The graph G is planar. 1) The graph G has chromatic number four. g) The graph G has radius three. b) The graph G has diameter three.

Show that the graph property P is monotone increasing if and only if the graph property Q is monotone decreasing where Q is the property of not having property P.

Suppose that P is a monotone increasing property of simple graphs. Show that the probability a random graph with n vertices has property P is a monotonic nondecreasing function of p, the probability an edge is chosen to be in the graph.

Given the vertex pairs associated to the edges of an undirected graph, find the degree of each vertex.

Given the ordered pairs of vertices associated to the edges of a directed graph, determine the in-degree and outdegree of each vertex.

Given the list of edges of a simple graph, determine whether the graph is bipartite.

Given the vertex pairs associated to the edges of a graph, construct an adjacency matrix for the graph. (Produce a version that works when loops, multiple edges, or directed edges are present.)

Given an adjacency matrix of a graph, list the edges of this graph and give the number of times each edge appears.

Given the vertex pairs associated to the edges of an undirected graph and the number of times each edge appears, construct an incidence matrix for the graph.

Given an incidence matrix of an undirected graph, list its edges and give the number of times each edge appears.

Given a positive integer n, generate an undirected graph by producing an adjacency matrix for the graph so that all simple graphs are equally likely to be generated.

Given a positive integer n, generate a directed graph by producing an adjacency matrix for the graph so that all directed graphs are equally likely to be generated.

Given the lists of edges of two simple graphs with no more than six vertices, determine whether the graphs are isomorphic.

Given the lists of edges of two simple graphs with no more than six vertices, determine whether the graphs are isomorphic.

Given the list of edges of a simple graph, determine whether it is connected and find the number of connected components if it is not connected.

Given the vertex pairs associated to the edges of a multigraph, determine whether it has an Euler circuit and, if not, whether it has an Euler path. Construct an Euler path or circuit if it exists.

Given the ordered pairs of vertices associated to the edges of a directed multi graph, construct an Euler path or Euler circuit, if such a path or circuit exists.

Given the list of edges of a simple graph, produce a Hamilton circuit, or determine that the graph does not have such a circuit.

Given the list of edges of a simple graph, produce a Hamilton path, or determine that the graph does not have such a path.

Given the list of edges and weights of these edges of a weighted connected simple graph and two vertices in this graph, find the length of a shortest path between them using Dijkstra's algorithm. Also, find a shortest path.

Given the list of edges of an undirected graph, find a coloring ofthis graph using the algorithm given in the exercise set of Section 9.8.

Given a list of students and the courses that they are enrolled in, construct a schedule of final exams

Given the distances between pairs of television stations, assign frequencies to these stations.

Display all the simple graphs with four vertices.

Display a full set of nonisomorphic simple graphs with six vertices.

Display a full set of nonisomorphic directed graphs with four vertices

Generate at random 10 different simple graphs each with 20 vertices so that each such graph is equally likely to be generated.

Construct a Gray code where the code words are bit strings of length six.

Construct knight's tours on chessboards of various sizes.

Determine whether each of the graphs you generated in Exercise 4 of this set is planar. If you can, determine the thickness of each of the graphs that are not planar.

Determine whether each of the graphs you generated in Exercise 4 of this set is connected. If a graph is not connected, determine the number of connected components of the graph.

Generate at random simple graphs with 10 vertices. Stop when you have constructed one with an Euler circuit. Display an Euler circuit in this graph.

Generate at random simple graphs with 10 vertices. Stop when you have constructed one with a Hamilton circuit. Display a Hamilton circuit in this graph.

Find the chromatic number of each of the graphs you generated in Exercise 4 of this set

Find the shortest path a traveling salesperson can take to visit each of the capitals of the 50 states in the United States, traveling by air between cities in a straight line.

Estimate the probability that a randomly generated simple graph with n vertices is connected for each positive integer n not exceeding ten by generating a set of random simple graphs and determining whether each is connected.

Work on the problem of determining whether the crossing number of K (7, 7) is 77, 79, or 81. It is known that it equals one of these three values.

Describe the origins and development of graph theory prior to the year 1 900.

Discuss the applications of graph theory to the study of ecosystems.

Discuss the applications of graph theory to sociology and psychology.

Discuss what can be learned by investigating the properties of the Web graph.

Describe algorithms for drawing a graph on paper or on a display given the vertices and edges ofthe graph. What considerations arise in drawing a graph so that it has the best appearance for understanding its properties?

What are some of the capabilities that a software tool for inputting, displaying, and manipulating graphs should have? Which ofthese capabilities do available tools have?

Describe some ofthe algorithms available for determining whether two graphs are isomorphic and the computational complexity ofthese algorithms. What is the most efficient such algorithm currently known?

Describe how Euler paths can be used to help determine DNA sequences.

Define de Bruijn sequences and discuss how they arise in applications. Explain how de Bruijn sequences can be constructed using Euler circuits

Describe the Chinese postman problem and explain how to solve this problem.

Describe some of the different conditions that imply that a graph has a Hamilton circuit.

Describe some of the strategies and algorithms used to solve the traveling salesman problem.

Describe several different algorithms for determining whether a graph is planar. What is the computational complexity of each of these algorithms?

In modeling, very large scale integration (VLSI) graphs are sometimes embedded in a book, with the vertices on the spine and the edges on pages. Define the book number of a graph and find the book number of various graphs including Kn for n = 3 , 4, 5, and 6.

Discuss the history of the Four Color Theorem

Describe the role computers played in the proof of the Four Color Theorem. How can we be sure that a proof that relies on a computer is correct?

Describe and compare several different algorithms for coloring a graph, in terms of whether they produce a coloring with the least number of colors possible and in terms of their complexity.

Explain how graph multicolorings can be used in a variety of different models.

Explain how the theory of random graphs can be used in nonconstructive existence proofs of graphs with certain properties.