Réunion d'été SMC 2022

St. John's, 3 - 6 juin 2022

Théorie des graphes
Org: Rick Brewster (Thompson Rivers University) et Gary MacGillivray (Victoria)
[PDF]

RICHARD BREWSTER, Thompson Rivers University List homomorphisms to signed trees [PDF]

The list homomorphism problem for a fixed signed graph $(H,\pi)$ takes as input a signed graph $(G, \sigma)$, equipped with lists $L(v) \subseteq V(H)$, $v \in V(G)$, of allowed images, and asks if there is a homomorphism $\varphi: (G, \sigma) \to (H, \pi)$. We classify the computational complexity of this problem when $H$ is a tree (irreflexive, reflexive, and general). The polynomial targets exhibit interesting structures. The tools developed are useful for general targets, and the patterns discovered for trees suggest nice families (such as the bi-arc graphs which characterize the problem for graphs) may classify the polynomial cases in general.

This is joint work with Jan Bok, Tom\'as Feder, Pavol Hell, and Nikola Jedli\v{c}kov\'a

ANDREA BURGESS, University of New Brunswick Saint John Mutually orthogonal cycle systems [PDF]

A $k$-cycle system of order $n$ is a set of $k$-cycles whose edges partition the edge set of $K_n$. We say that two cycle systems $\mathcal{C}$ and $\mathcal{C}'$ are orthogonal if every cycle in $\mathcal{C}$ shares at most one edge with each cycle in $\mathcal{C}'$. Orthogonal cycle systems arise naturally from simple Heffter arrays and biembeddings of cycle decompositions.

A collection of cycle systems is mutually orthogonal if any two of the systems are orthogonal. In this talk, we give bounds on the number of mutually orthogonal $k$-cycle systems of order $n$ and provide constructions for sets of mutually orthogonal cyclic cycle systems.

This is joint work with Nicholas Cavenagh and David Pike.

MACKENZIE CARR, Simon Fraser University The Genus Polynomials of Cubic Graphs [PDF]

Given a graph $G$, its genus distribution is the sequence $\{a_g\}_{g\geq 0}$, where $a_g$ is the number of 2-cell embeddings of $G$ in the oriented surface of genus $g$. The genus polynomial of $G$ is defined similarly to be $\sum_{g\geq 0} a_gx^g$. The Log-Concavity Conjecture, which has been open for more than 30 years, states that the genus polynomial of every graph is log-concave. It was further conjectured by Stahl that the genus polynomial of every graph has only real roots, however this was later disproved. In this talk, we examine the genus polynomials of cubic graphs and the distribution of their roots. We present some cubic graphs whose genus polynomials have complex roots and explore the difficulty in using the roots of these polynomials to determine whether they are log-concave.

SHONDA DUECK, University of Winnipeg The threshold strong dimension of a graph [PDF]

A set $W$ of vertices of a connected graph $G$ is a strong resolving set for $G$ if, for every pair of vertices, one of the vertices in the pair lies on a shortest path from the other vertex to some vertex of $W$. The smallest cardinality of a strong resolving set of vertices of $G$ is the strong dimension of $G$. The threshold strong dimension of $G$ is the smallest strong dimension among all graphs having $G$ as a spanning subgraph, and it is denoted by $\tau_s(G)$. We present a geometric characterization of $\tau_s(G)$, which expresses $\tau_s(G)$ in terms of the smallest number of paths (each of sufficiently large order) whose strong product admits a certain type of embedding of $G$. We also establish logarithmic bounds on $\tau_s(G)$ for graphs in general, and for trees. This is joint work with Nadia Benakli, Novi H. Bong, Linda Eroh, Beth Novick, and Ortrud Oellermann.

ARNOTT KIDNER, Memorial University of Newfoundland $\Gamma$-switchable 2-colourings [PDF]

Informally, a $(m,n)$-mixed graph is a mixed graph whose edges are assigned $m$ colours and arcs are assigned $n$ colours. For a permutation $\pi$ that acts on the edge colours, arc colours, and arc orientations, we say switching at a vertex $v$ with respect to $\pi$ changes the edges/arcs incident with $v$ with the action of $\pi$. We show that it is polynomial time decidable to determine whether; for a fixed permutation group, there admits a sequence of switches on a $(m,n)$-mixed graph such that the resulting graph admits a homomorphism to a simple target on $2$ vertices.

THEODORE KOLOKOLNIKOV, Dalhousie University It is better to be semi-regular when you have a low degree [PDF]

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity and as well as the full spectrum distribution. For an integer $d \in [3,8]$, we find families of random semi-regular graphs that have higher algebraic connectivity than a random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semiregular graphs when d >8. More generally, we study random semi-regular graphs whose average degree is d, not necessary an integer. This provides a natural generalization of a d-regular graph in the case of a non-integer d. We characterise their algebraic connectivity in terms of a root of a certain 6th-degree polynomial. Finally, we construct a small-world-type network of average degree 2.5 with a relatively high algebraic connectivity. We also propose some related open problems and conjectures

LUCAS MOL, Thompson Rivers University On connectivity of orientations of graphs [PDF]

An orientation of a graph $G$ is a directed graph obtained from $G$ by assigning a direction to every edge. A well-known result of Nash-Williams says that every graph has a well-balanced orientation - an orientation that best preserves the overall level of connectivity in some sense. We consider some related problems, providing more questions than answers.

BEN SEAMONE, Dawson College Fractional eternal domination [PDF]

We introduce the study of fractional eternal domination in graphs, a natural relaxation of the well-studied eternal domination problem. One can naturally define the fractional eternal domination number of a graph $G$, which is the smallest total weight for which one can fractionally eternally dominate $G$. We highlight connections to flows and linear programming, and study the behaviour of the fractional eternal domination number as it relates to other domination parameters. We also determine bounds on, and in some cases exact values for, the fractional eternal domination number of $G$ when $G$ is a member of one of a variety of important graph classes, including trees, split graphs, strongly chordal graphs, Kneser graphs, abelian Cayley graphs, and graph products.

EVELYNE SMITH-ROBERGE, University of Waterloo Planar Graphs are Local Girth Choosable [PDF]

Perhaps the most famous theorem in the field of graph colouring is the four colour theorem, which states that every planar graph is 4-colourable. This theorem does not carry over directly to the realm of list colouring: Voigt gave a construction of a planar graph that is not 4-choosable. However, if we increase our list sizes by one, the resulting theorem holds: Thomassen proved that every planar graph is 5-choosable. In addition, Thomassen proved that every planar graph of girth at least five is 3-choosable. Voigt showed that this girth condition is best possible in the sense that there exist planar graphs of girth four that are not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment, wherein the list size of each vertex depends not on the girth of the graph but only on the length of the shortest cycle in which the vertex is contained. I will present a local choosability theorem that unifies and strengthens the two theorems of Thomassen mentioned above. This is joint work with Luke Postle.

haut de la page