CAG Schedule of Talks: Fall 2004

Schedule of Talks: Fall 2004

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
Sept. 24 Grad center 3:30 None Meet for beer at grad center
Oct. 29 Cle C 112 2:30 Aaron Williams Perfect Elimination Orders of Chordal Graphs
Nov. 5 EOW 430 2:30 Peter Dukes Complete Bipartite Directed Graph Decompositions and Energy-Limited Sensor NetworkS
Nov. 12 EOW 430 2:30 Reading break
Nov. 19 EOW 430 2:30 No CAG Combinatorial Potlatch in Vancouver Nov. 20
Nov. 26 DSB C 113 2:30 Sudhakar Ganti Applying Network Tomography for Network Overlays
Dec. 6 EOW 430 2:30 Patrick Fowler Three aspects of fullerenes - nuts, knots and spirals

Upcoming Talks:

Applying Network Tomography for Network Overlays
Sudhakar Ganti
2:30, Friday Nov. 26, DSB C113

This talk presents the concepts of Network Tomography and the principles of traffic matrix estimation. This will be further applied to the Network Overlay designs using flexible service models. The talk will highlight some of the recent work in this area and what further research needs to be done.

Three aspects of fullerenes - nuts, knots and spirals
Patrick Fowler
2:30, Monday Dec. 6, EOW 430

Fullerenes are all-carbon molecules with trivalent polyhedral skeletons, having 12 faces pentagonal and all others hexagonal. Or equivalently, they correspond to 3-regular planar graphs which have twelve 5-faces and the remaining faces are hexagons. Many questions about their chemistry can be cast in graph-theoretical form. This talk deals with three subclasses of the fullerenes:

  1. Nut-graphs have exactly one zero eigenvalue in their adjacency spectrum and no zero entries in the corresponding eigenvector;
  2. Knot-graphs have exactly one Petrie path; and
  3. V-spiral graphs support at least one vertex-spiral that connects all vertices in one contiguous tightly wound Hamiltonian path.
Some results on occurrence of graphs of these types amongst the fullerenes, and on their relevance to chemistry, will be presented.

Previous Talks:

CAG General Meeting
Friday September 17

Please join us at the grad center at 3:30pm for beer or your favorite refreshments.

Here are some questions to consider before the meeting:

  1. Is the current CAG slot the best time (Fridays at 2:30) or should be switch back to the 3:30 talks? Or maybe some other time?
  2. Would anybody else like to be the CAG organizer? I have been doing it for at least 3 years now, and maybe someone else would like to have a turn?
  3. Are there any other types of interesting activities we would like to organize?
  4. So far, I have just facilitated visitors that other people invite. Are there any visitors the CAG group or individuals might like to sponsor?
  5. Who would like to give a CAG talk in the fall?
  6. Is it time to select a different room? If so, where? EOW 430 is convenient for computer science faculty, but less convenient for faculty in math or grad students in computer science.

Perfect elimination orders of chordal graphs
Aaron Williams
Friday Oct. 29, 2:30, Clearihue C 112

A graph is chordal if it does not contain an induced cycle of length four or greater. Chordal graphs are characterized by the existence of vertex orderings called perfect elimination orders. These orders are the basis for solving many NP-complete problems (including vertex colouring and maximum independent set) in linear time. For this reason, algorithms that quickly generate perfect elimination orders are of considerable practical value. One such algorithm is called maximum cardinality search. In this talk, we will prove the correctness of this simple and elegant algorithm. The proof is "new" in the sense that it differs from the original proof, and I have not seen it before.

Complete Bipartite Directed Graph Decompositions and Energy-Limited Sensor NetworkS
Peter Dukes
2:30, Friday Nov. 5, EOW 430

In this talk, we examine edge-decompositions of the lambda-fold complete directed graph lambda-Kn into complete bipartite directed subgraphs Ka,b as a model for communication in sensor networks. The n vertices of lambda Kn correspond to nodes in the network. A constituent Ka,b in the edge decomposition corresponds to a scheduled time slot for communication in which the a out-vertices are transmitting, the b in-vertices are listening, and all other n-a-b vertices are asleep (powered down). The decomposition guarantees lambda time slots for a transmission from any node x to any other node y. However, it is also desirable to minimize interference by a third node x'. We outline various constructions for these graph decompositions, with particular emphasis on properties minimizing interference.

This is joint work with Charles Colbourn and Violet Syrotiuk.

CAG Schedule of Talks: Fall 2004 / maintained by Wendy Myrvold / / revised Sept. 9, 2004