 français conference home canadam home

Average Graph Parameters - Part II
Org: Stijn Cambie (Radboud University Nijmegen, the Netherlands)
[PDF]

IAIN BEATON, Dalhousie University
The Average Order of Dominating Sets of a Graph  [PDF]

This talk focuses on the average order of dominating sets of a graph. We find the extremal graphs for the maximum and minimum value over all graphs on $n$ vertices, while for trees we prove that the star minimizes the average order of dominating sets. We prove the average order of dominating sets in graphs without isolated vertices is at most $3n/4$, but provide evidence that the actual upper bound is $2n/3$. Finally, we show that the normalized average, while dense in $[1/2,1]$, tends to $\frac{1}{2}$ for almost all graphs. This is joint work with Jason Brown (Dalhousie University)

JOHN HASLEGRAVE, University of Warwick
The average size of a connected set in a connected graph with degree constraints  [PDF]

We consider the average density of sets of vertices which are internally connected by edges of a fixed graph. When that graph is a tree, these sets are subtrees, and Jamison established the smallest and largest possible values. If the tree has no degree-2 vertex, both bounds change, and optimal values were given by Vince and Wang.

Much less is known for general graphs, and techniques for trees typically do not generalise. Again, it seems degree-2 vertices are critical. I shall discuss some new bounds, in particular answering a question of Vince, and some open questions.

VALISOA MISANANTENAINA, Stellenbosch University
The average size of independent vertex/edge sets of a graph  [PDF]

In this talk, we characterize both the average size of independent vertex sets and independent edge sets of a graph. These invariants are the logarithmic derivative of the independence (resp. matching) polynomial evaluated at one. We show that although they are not monotone, under an addition or a removal of an edge, like the number of vertex (resp. edge) independent sets, the extremal graphs remain the same for general graphs (the empty and complete graph) and the class of trees (the star and the path).

SUIL O, The State University of New York, Korea
The average connectivity matrix of a graph  [PDF]

In this talk, we introduce the average connectivity matrix of a graph and examine some properties of the matrix.

ANDREW VINCE, University of Florida
The Average Size of a Connected Vertex Set of a Graph  [PDF]

Although connectivity is a basic concept in graph theory, the enumeration of connected subgraphs of a graph has only recently received attention. The topic of this talk is the average order of a connected induced subgraph of a graph. This generalizes, to graphs in general, the average order of a subtree of a tree, a topic initiated in a 1984 paper by R. Jamison.