CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Structure of graphs II
Président: Mark Ellingham (Vanderbilt University)

ALIZÉE GAGNON, Université de Montréal
On Self-Contained Graphs  [PDF]

We revisit the twin graphs conjecture and prove that it is enough to prove it for connected graphs. It says that a graph has either zero or infinitely many non-isomorphic twins. Two graphs G and H are twins if they are not isomorphic and each embeds into the other. Our proof relies on a structural lemma for disconnected self-contained graphs, that is, graphs that are properly embeddable into themselves. The talk is based on work with G. Hahn and R.E. Woodrow.

SHONDA GOSSELIN, University of Winnipeg
Almost t-complementary uniform hypergraphs  [PDF]

An almost $t$-complementary $k$-hypergraph is a $k$-uniform hypergraph with vertex set $V$ and edge set $E$ for which there exists a permutation $\theta\in Sym(V)$ such that the sets $E, E^\theta, E^{\theta^2}, \ldots, E^{\theta^{t-1}}$ partition the set of all $k$-subsets of $V$ minus one edge. Such a permutation $\theta$ is called an almost $(t,k)$-complementing permutation. The almost $t$-complementary $k$-hypergraphs are a natural generalization of the almost self-complementary graphs which were previously studied by Clapham, Kamble et al, and Wojda. We prove that there exists an almost $p$-complementary $k$-hypergraph of order $n$ whenever the base-$p$ representation of $k$ is a subsequence of the base-$p$ representation of $n$, where $p$ is prime.

JOHN IRVING, Saint Mary's University
Counting Locally Oriented Noncrossing Trees  [PDF]

Let $T$ be a noncrossing tree on vertices $\{1,2,\ldots,n\}$. We say $T$ is \emph{locally oriented} if each edge is directed toward its smallest endpoint. Let $e_i(T)$ (respectively, $d_i(T))$ be the number of vertices of indegree (outdegree) $i$ in $T$. Okoth and Wagner found an elegant multiplicative formula counting locally-oriented noncrossing trees with specified in- and out-degree vectors $(e_i(T))_{i \geq 0}$ and $(d_i(T))_{i \geq 0}$. We generalize their result to give a simple formula counting these trees with specified numbers $(n_{ij})_{i,j \geq 0}$ of vertices of indegree $i$ and outdegree $j$. We also modestly generalize some enumerative results of Noy concerning noncrossing graphs and outerplanar maps.

ROBERT D. LUTHER, Memorial University of Newfoundland
Existential Closure in Line Graphs  [PDF]

For a positive integer $n$, a graph $G$ is {\it $n$-existentially closed} or {\it $n$-e.c.}, if for any proper $n$-subset $S$ of the vertices of $G$, and for any subset $T$ of $S$, there is a vertex $x$ not in $S$ such that $x$ is adjacent to each vertex of $T$ and no vertex of $S-T$. The focus of our work will be investigating the $n$-e.c.\ property in line graphs. We say $G$ is an {\it $n$-line e.c.}\ graph if and only if the corresponding line graph is an $n$-e.c.\ graph. We present new results on finding and classifying $2$-line e.c.\ graphs.

MASOOD MASJOODY, Simon Fraser University
Cops and Robbers on Graphs with a Set of Forbidden Induced Subgraphs  [PDF]

It is known that the class of all graphs not containing a graph $H$ as an induced subgraph is cop-bounded if and only if $H$ is a forest whose every component is a path. In this study, we characterize all sets $\mathcal{H}$ of graphs with bounded diameter, such that $\mathcal{H}$-free graphs are cop-bounded. This, in particular, gives a characterization of cop-bounded classes of graphs defined by a finite set of connected graphs as forbidden induced subgraphs. Furthermore, we extend our characterization to the case of cop-bounded classes of graphs defined by a set $\mathcal{H}$ of forbidden induced subgraphs such that the components of members of $\mathcal{H}$ have bounded diameter.