# Discrete Mathematics: Math 610,
Spring 2008

### DeBartolo 244: MWF 10:40 - 11:30

## Office Hours: after
class; and 12:30-1:30 Wednesday in
my office.

# Handouts

A Maple 11 worksheet on Coloring Cubes: http://www.nd.edu/~sommese/math08S610/ColorCubes.mws

A Maple 11 worksheet for counting four vertex
graphs: http://www.nd.edu/~sommese/math08S610/FourVertexGraphs.mws

A Maple 11 worksheet for the Petersen graph: http://www.nd.edu/~sommese/math08S610/PetersenGraph.mws

# Exam Schedule

## Exam 1: Monday, February 18 (take home
handed out on February 15 at the end of class).

## Exam 2: Monday, April 7 (take home handed
out on April 4 at the end of class).

## Final: Take home that will be handed out
on last day of class and will be due by 10AM,
Friday, May 9.

# Homework

## Homework 9 (due Friday, April 25):

A) Draw the trees
with Prufer encodings

1234567

1111111

222

111333

B) Do a cyclic permutation
on the vertices of the graphs you have constructed, e.g.,

for the first tree above
(on the 9 vertices 1, 2, 3, 4, 5, 6, 7, 8, 9), replace 1 by 2,

2 by 3, etc. Now compute the Prufer encodings of
these permuted graphs.

C) What are the
degrees of the 36 vertices of the graph with Prufer encoding equal to 13 ones

followed by 12 twos followed
by 6 ones followed by 3 nines.

## Homework 9 (due Wednesday, April 16):

Compute the chromatic
polynomial for the graphs K_n with n from 1 to 5; and

for the graphs
K_{a,b} with

## Homework 8 (due Wednesday, April 2):

For the graphs K_n
with n from 3 to 8; for K_3 + K_5

joined at one point;
and for K_4+K_4 joined at one point,

a) write down the
adjacency matrices;

b) compute the number
of edges;

c) compute the number
of walks of length 4;

d) compute the number
of triangles;

e) compute the ranks
of the adjacency matrices;

f) compute the
eigenvalues of the matrices; and

g) compute the
diameters of the graphs.

## Homework 7 (due Wednesday, March 26):

Given a poset P = (X,
R) with |X| = n > 0; we have shown there is at least one

order-preserving map
to a chain of length n. For each of
the posets P on page 188,

use the zeta
functions of their associated lattices L(P) to compute the numbers of

these order
preserving maps.

## Homework 7 (due Wednesday, March 19):

Problems 1 and 8 of
12.10.

## Homework 6 (due Wednesday, March 12):

Problems 8 of 7.5.

## Homework 5 (due Wednesday, February 27):

Problems 1 (only for
faces and for edges), 2 of 15.8.

## Homework 4 (due Wednesday, February 13):

Problems 2, 3, 6, and
7 of 13.6.

A) Write the permutation in
cycle notation. This gives a
partition of 8.

B) How many different permutations give rise to the same partition?

## Homework 3 (due Friday, February 8):

Problems 15b, 16 of 4.8.

Do Problems 7 and 8 of 5.6.

## Homework 2 (due Friday, February 1):

Compute S(n,k)
directly for k greater than n - 3 and also for k less than 3.

Do Problems 14, 17 of
4.8.

## Homework 1 (due Friday, January 25):

Do Problems 3, 8, 10,
11 of 2.8.

##

## Click here to go to the Department of
Mathematics home page.

**Click here to go to the Center for Applied
Mathematics home page. **

**Click here to go to the ****College**** of ****Science**** home page. **

**Click here to go to the ****University**** of ****Notre Dame**** home page. **

##

## You are visitor number

**since December
18, 2007. **