CanaDAM 2021
On-line, May 25 - 28, 2021

Enumerative and Extremal Graph Theory
Org: Rachel Kirsch (Iowa State University)

GABRIELA ARAUJO-PARDO, Universidad Nacional Autónoma de México
The Moore and Cage Problems on Mixed Graphs  [PDF]

The Moore and Cage Problems are two classical topics on Extremal Graph Theory. In both of them the goal is find regular graphs, in the first they have fixed diameter and maximum order and in the second the graphs have fixed girth and minimum order.

We study both problems on Mixed Graphs, a {\it{Mixed regular graph}} is a $(z,r)$-graph, $z$-regular by arcs and $r$-regular by edges, a $(z,r;d)$-mixed Moore graph is a mixed graph with fixed diameter $d$ and maximum order whereas a $[z, r; g]$-mixed cage is a mixed graph with fixed girth $g$ and minimum order.

ZHANAR BERIKKYZY, Fairfield University
Rainbow solutions to the Sidon equation in cyclic groups and in the interval  [PDF]

Given a coloring of group elements, a rainbow solution to an equation is solution whose every element is assigned a different color. Rainbow number of $\mathbb{Z}_n$ for an equation $eq$, denoted $rb(\mathbb{Z}_n,eq)$, is the smallest number of colors $r$ such that every exact $r$-coloring of $\mathbb{Z}_n$ admits a rainbow solution to this equation. We show that for every exact $4$-coloring of $\mathbb{Z}_p$, where $p\geq 3$ is prime, there exists a rainbow solution to the Sidon equation $x_1+x_2=x_3+x_4$. Furthermore, we determine the rainbow numbers of $\mathbb{Z}_n$ and the set of integers $[n]=\{1,\ldots,n\}$ for the Sidon equation. Joint work with J\"urgen Kritschgau.

JESSICA DE SILVA, California State University Stanislaus
Image Segmentation via Hypergraph-based MRF Models  [PDF]

X-ray micro-tomography ($\mu$-CT) is a non-destructive 3D imaging technique often used to image material samples. Synchrotron-based $\mu$-CT instruments produce high volumes of data at a fast rate. This leads to the need for image processing techniques capable of extracting valuable information in large complex data sets. Recent approaches to image segmentation exploit the local properties of Markov Random Fields (MRFs) to run computations in parallel. We have developed an image segmentation algorithm using a hypergraph-based MRF model. The algorithm is coded in C++ and preliminary results indicate that this generalized model improves the precision of the segmentation of $\mu$-CT images.

MICHAEL GUYER, Auburn University
On clique immersions in line graphs  [PDF]

In this talk we will discuss the immersion relation on graphs. This relation is similar but incomparable to the well-known minor relation. We will explore the relationship between coloring and such containment relations. In particular, we prove that if $L(G)$ immerses $K_t$ then $L(mG)$ immerses $K_{mt}$, where $mG$ is the graph obtained from $G$ by replacing each edge in $G$ with a parallel edge of multiplicity $m$. We also show that when $G$ is a line graph, $G$ has a $K_t$-immersion iff $G$ has a $K_t$-minor whenever $t \leq 4$. This equivalence fails in both directions when $t \geq 5$.

LINDA LESNIAK, Western Michigan University
On the necessity of Chv\'{a}tal's hamiltonian degree condition  [PDF]

In 1972, Chv\'{a}tal gave a well-known sufficient condition for a degree sequence to be forcibly hamiltonian, and showed that in some sense his condition is best possible. In this paper, we conjecture that with probability 1 as $n \rightarrow \infty$, Chv\'{a}tal's sufficient condition is also necessary. In contrast, we essentially prove that the sufficient condition of Bondy and Boesch for forcible $k$-connectedness is not necessary in the same way, for every $k \geq 1$.