COS 341, November 19, 1997Handout Number 17
Extra-Credit Homework Set
This is an extra-credit assignment. If you decide to do it, the due date is Wednesday, November 26, and late submissions will not be accepted. Please note that no collaboration is allowed for this special assignment. Otherwise it's open-book, open-notes, just like other homework sets.
Problem 1 [20pts] (a)[5 points] Let B(x), C(x), D(x), E(x) be the generating functions for the sequences
If B(x) = C(x)D(x)E(x), express 
as a summation of
terms involving the other three sequences.
(b)[15 points] Let 
, where 
and for 
,
Find a closed-form expression for A(x).
Problem 2 [35pts] Let G=(V,E) where
and E consists of the edges 
, 
and 
,
. Answer each of the following questions;
justify your answers.
(a) [5 points] What is 
, the size of the largest
clique?
(b) [5 points] What is 
, the size of the largest
independent set?
(c) [5 points] What is 
, the chromatic number?
(d) [5 points] Is G a planar graph?
(e) [5 points] Is G an Eulerian graph?
(f) [10 points] Does G contain a Hamiltonian cycle?
Problem 3 [30pts] For any n>0, let
be the ladder graph with n rungs as
shown below. Let 
be the number of spanning
trees of . Clearly, 
.
Let 
.
(a)[5 points] Determine the value of 
.
(b)[5 points] Determine the value of 
.
(c)[20 points] Derive a closed-form formula for T(x).
Hint: Let 
be the number of
spanning trees of that contain the
edge 
. Note 
, 
. Find
a recurrence relation involving both 's and 's.