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 biarc 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 2cell 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 LogConcavity Conjecture, which has been open for more than 30 years, states that the genus polynomial of every graph is logconcave. 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 logconcave.
 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 2colourings [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 semiregular when you have a low degree [PDF]

We study the algebraic connectivity for several classes of random semiregular graphs. For large random semiregular 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 semiregular graphs that have higher algebraic connectivity than a random dregular 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 semiregular graphs whose average degree is d, not necessary an integer. This provides a natural generalization of a dregular graph in the case of a noninteger d. We characterise their algebraic connectivity in terms of a root of a certain 6thdegree polynomial. Finally, we construct a smallworldtype 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 wellknown result of NashWilliams says that every graph has a wellbalanced 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 wellstudied 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 SMITHROBERGE, 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 4colourable. This theorem does not carry over directly to the realm of list colouring: Voigt gave a construction of a planar graph that is not 4choosable. However, if we increase our list sizes by one, the resulting theorem holds: Thomassen proved that every planar graph is 5choosable. In addition, Thomassen proved that every planar graph of girth at least five is 3choosable. Voigt showed that this girth condition is best possible in the sense that there exist planar graphs of girth four that are not 3choosable. 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.
© Société mathématique du Canada