CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Independence Number: Theory and Applications I.
Chair: Craig Larson (Virginia Commonwealth University)
Org: Ermelinda DeLaVina (University of Houston--Downtown) and Craig Larson (Virginia Commonwealth University)

ERMELINDA DELAVINA, University of Houston-Downtown
Graffiti.pc on Independence  [PDF]

Graffiti.pc is a graph theoretical conjecture-making program whose creation was inspired by the well-known program of Siemion Fajtlowicz, Graffiti. In addition to a brief description of the principles of the program we discuss Graffiti.pc's conjectured bounds on the independence number and other independence related graph invariants.

ART FINBOW, Saint Mary's University
On Well-Covered Planar Triangulations  [PDF]

A graph G is said to be \textit{well-covered} if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a \textit{triangulation}. A characterization of the planar well-covered triangulations has finally been completed. In a series of three previous papers, we have completed the 4- and 5-connected cases. This talk will focus on the 3-connected case.

This is joint work with B. L. Hartnell, R. Nowakowski and Michael D. Plummer.

MICHAEL D. PLUMMER, Vanderbilt University
A Problem On Well-covered Graphs  [PDF] [SLIDES]

A graph is \textit{well-covered} if every maxim\textit{al} independent set of vertices is also maxim\textit{um}. In other words, all maximal independent sets of vertices in the graph have the same cardinality.

I will present and discuss the recently solved problem of characterizing all well-covered quadrangulations of the plane.

This is joint work with Finbow and Hartnell.

WILLIAM STATON, University of Mississippi
Independence Polynomials of k-Trees  [PDF] [SLIDES]

Explicit formulas are known for the independence polynomials of several classes of trees. We discuss extensions of some of these formulas to the corresponding classes of k-trees. Additionally, we generalize, to k-trees, Wingard’s bounds for the coefficients of the independence polynomial of a tree.

DAVID TANKUS, Ariel University Center of Samaria, ISRAEL
Weighted Well-Covered Graphs without Cycles of Lengths 4, 5, and 6  [PDF] [SLIDES]

A graph $G$ is \textit{well-covered} if all its maximal independent sets are of the same cardinality. Assume that a weight function $w$ is defined on its vertices. Then $G$ is $w$\textit{-well-covered} if all maximal independent sets are of the same weight. For every graph $G$, the set of weight functions $w$ such that $G$ is $w$-well-covered is a \textit{vector space}. Given an input graph $G$ without cycles of length $4$, $5$, and $6$, we characterize polynomially the vector space of weight functions $w$ for which $G$ is $w$-well-covered. \

This is joint work with Vadim E. Levit.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland