CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//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)
[PDF]

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.