CanaDAM 2013 Université Memorial de Terre-Neuve, 10 - 13 juin 2013 www.smc.math.ca//2013f

Graph Theory I
PrÃ©sident: Odile Marcotte (CRM and UQAM)
[PDF]

Two Laplacians for the Distance Matrix of a Graph  [PDF] [SLIDES]

We introduce a Laplacian and a signless Laplacian for the distance matrix of a connected graph, called the distance Laplacian and distance signless Laplacian, respectively. We show the equivalence between the distance signless Laplacian, distance Laplacian and the distance spectra for the class of transmission regular graphs. There is also an equivalence between the Laplacian spectrum and the distance Laplacian spectrum of any connected graph of diameter 2. Similarities between $n$, as a distance Laplacian eigenvalue, and the algebraic connectivity are established.

SARADA HERKE, The University of Queensland
Perfect 1-factorisations of circulant graphs of degree 4  [PDF] [SLIDES]

A 1-factorisation of a graph $G$ is a partition of the edge set of $G$ into 1-factors. A 1-factorisation of a graph $G$ is said to be perfect if the union of every pair of 1-factors in the 1-factorisation is a Hamilton cycle of $G$. The study of perfect 1-factorisations originated with questions posed by Kotzig almost 50 years ago, and many open problems remain. In this talk, some results on perfect 1-factorisations of circulant graphs of degree 4 will be presented.

MATTHIAS KRIESELL, Technical University Ilmenau
On the Structure of Graphs of Minimum Degree at least Four  [PDF] [SLIDES]

We characterize the graphs of minimum degree at least 4 which cannot be reduced to smaller such graphs by either contracting or deleting a single edge, in terms of decompositions into edge disjoint copies of graphs out of a small list of small building blocks.

ODILE MARCOTTE, CRM and UQAM
On the maximum orders of an induced forest, an induced tree, and a stable set  [PDF] [SLIDES]

Let G be a connected graph, n the order of G, and f (resp. t) the maximum order of an induced forest (resp. tree) in G. We give upper bounds for f-t (depending upon the value of n) and show that these bounds are tight. We present similar results for the difference between the stability number of G and the maximum order of an induced tree in G.

PAUL WENGER, Rochester Institute of Technology
Saturated Subgraphs of Multipartite Graphs  [PDF]

Given graphs $G$ and $H$, a subgraph $J$ of $G$ is \textit{$H$-saturated} if $H$ is not a subgraph of $J$, but the addition of any new edge from $G$ to $J$ completes a copy of $H$. In this talk we present results on the minimum size of $K_t$-saturated subgraphs of complete balanced multipartite graphs. These results provide a contrast to recent results about the maximum edge density of $K_t$-free subgraphs of complete multipartite graphs. This is joint research with Michael Ferrara, Michael Jacobson, and Florian Pfender.