class preparation
For Monday Jan 23rd
Read Chapter 1 and come ready to discuss exercises 1.1 and 1.2.
For Thursday Jan 26th
Read Chapter 2. Come prepared to discuss any difficulties you had and the content, especially the proofs. Attempt exercises 2.1, 2.4, 2.5, 2.9, 2.10 for discussion in class.
For Monday Jan 30th
Read Chapter 3. Attempt exercises 3.3, 3.7, 3.9.
For Thursday Feb 2nd
Make sure that you have indeed attempted the various exercises from Chapters 2 and 3 above. We'll be talking about them and about the second half of Chapter 3.
For Monday Feb 6th
Read Chapter 4 up to 4.3 and consider questions 4.1 and 4.2.
For Thursday Feb 9th
There will be opportunity to ask about any difficulties you are having with the homework that is due tomorrow. Also, we'll start to plan the middle section of the course: be ready to discuss how you'd like the this portion of the class to be structured and if there are topics you are itching to have included, have those in mind too.
For Monday Feb 13th
None.
For Thursday Feb 16th
Here are some problems to think about for Thursday's class. At least one is fairly straightforward, at least one is hard, at least one is an open question and at least one I have no idea about either the answer or how tricky it is.
In all cases, messing around with specific instances and generating some intuition is the way to go. Partial answers should be considered successes: X is true at least up to ten vertices; Y is true when n is even... that sort of thing. Breaking hard questions up into smaller do-able chunks is an important first step towards an eventual solution.
I've gone a bit overboard with the questions. Read them all, but consider the overall goal to be: "Play with graceful labelings and get a feel for how they work. Spot patterns. Make conjectures." Do this and you'll be set. You're probably better spending more time on one or two questions than making shallower attempts at the whole list.
General
- Take a graceful labeling on a tree with n vertices (so it uses the labels 0,1,...n-1). Show that the labeling obtained by replacing each label x with n-1-x is also a graceful labeling. This is called taking the complement.
Snakes
- Given a graceful labeling of a snake we can get new ones by reversing the order of the labels and/or complementing. Are there graceful labelings of snakes other than the one we found in class and the ones we can reach from that one in these ways? For every n?
For the next two, play around and see what conjectures you can generate.
- What possible labels can be used on a leaf (i.e. one of the two vertices of degree 1) on a snake with n vertices?
- What pairs of labels can be used as the two leaf labels of a graceful labeling of a snake with n vertices? Or on a leaf vertex and its adjacent one? (In particular, are there pairs that can't be so used?)
Stars
A star is a graph with a central vertex and lots of paths of length 1 coming from it.
- Show that all stars are graceful.
- What labels are possible on the central vertex of a star with n vertices?
Tripods
For three positive integers a b and c where a≤b≤c
, an (a,b,c)-tripod is a central vertex with paths of lengths a, b and c coming from it. (So, if n is the number of vertices then n = a+b+c+1)
- What labels can possibly appear on the central vertex of some gracefully labeled tripod? On some leaf of a tripod?
- What about the above question but for some given n? Or some given (a,b,c)?
- How many (families of) tripods can you show are graceful?
Other trees
- For what other trees can you find graceful labelings? Any infinite families other than caterpillars?
Unrelated... or is it?
Dudeney's Ramsgate Sands Problem: 13 girls are going to perform 6 dances on Ramsgate Sands (a beach in England). For each dance they will hold hands in a circle. Is it possible to arrange the girls so that each girl holds hands with every other girl exactly once?
It is a special case of a problem posed by Lucas in 1892. For each odd number v, Lucas asked for an arrangement in which v girls perform (v−1)/2 dances. As in Dudeney’s problem, the girls must dance in a circle each time and each girl must hold hands with every other girl exactly once. Setting v = 13 gives Dudeney’s problem.
Can you describe the problem in graph theoretic language? For which values of v can you find a solution?
Monday Feb 20th
Graceful labelings, first targets:
Prove Isaac's result: If it is possible to gracefully label a snake with a 0 in any specified position then all tripods are graceful.
Where can labels go on snakes? Especially: what possible labels can be at one end? what possible pairs of labels can (and cannot) start the labelling? what possible pairs can (and cannot) go on the two ends?
Similar questions for tripods. Can we always put the 0 on the junction? (If so, does this tell us anything about tetrapods?) What is possible on the ends?
You might also like to check out Gallian's survey paper in the Electronic Journal of Combinatorics. I can't link to it because the site is weird, but go to
the homepage, click "Dyanimic Surveys" and it's Number 6.
Also, take a crack at the Ramsgate Sands problem listed for last time.
Thu Mar 1st
Presentations I.
Thu Mar 8th
Presentations II.
Mon Mar 26th
Read Chapters 9 and 10 of Wilson.
Thu Mar 29th
Read Chapter 11 of Wilson and
this page about the newer 1997 proof of the result.
