CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Graphs and Degree Constraints

MEHDI AAGHABALI, The University of Edinburgh
Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges  [PDF]

We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on $2n$ vertices. The upper bound is sharp for even $n$. For odd $n$ we state a conjecture on a sharp upper bound

DEEPAK BAL, Montclair State University
Analysis of the 2Greedy Algorithm on Random Graphs with Fixed Degree Sequence  [PDF]

2Greedy is a simple greedy algorithm for finding a large 2-matching in a graph; that is, a spanning subgraph with maximum degree 2. Frieze introduced the algorithm and analyzed its performance on sparse random graphs conditioned to have minimum degree at least 3. We analyze the performance of 2Greedy on a graph chosen uniformly at random from the set of graphs having a specified degree sequence. We present a condition on the degree sequence which guarantees that the algorithm returns a 2-matching with $o(n)$ components whp. This is joint work with Patrick Bennett.

DAVID BURSTEIN, Swarthmore College
Tools for constructing graphs with fixed degree sequences  [PDF]

Constructing graphs that resemble their empirically observed counterparts is integral for simulating dynamical processes that occur on networks. Since many real world networks exhibit degree heterogeneity, we consider some challenges in randomly constructing graphs with a given bidegree sequence in an unbiased way. In particular, we propose a novel method for the asymptotic enumeration of directed graphs that realize a bidegree sequence, $\mathbf{d}$, with maximum degree $d_{max}=O(S^{\frac{1}{2}-\tau})$ for an arbitrarily small positive number $\tau$, where $S$ is the number of edges specified by $\mathbf{d}$; the previous best results allow for $d_{max}=o(S^{\frac{1}{3}})$ . Our approach is based on two key steps, graph partitioning and degree preserving switches. The former allows us to relate enumeration results to sequences that are easy to handle, while the latter facilitates expansions based on numbers of shared neighbors of pairs of nodes.

SHONDA GOSSELIN, University of Winnipeg
The metric dimension of circulants and their Cartesian products  [PDF]

A pair of vertices $x$ and $y$ in a graph $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a subset $W\subseteq V(G)$ if every pair of vertices in $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$. The metric dimension of a graph has applications in network discovery and verification, combinatorial optimization and chemistry. There is great interest in finding classes of graphs with bounded metric dimension, where the metric dimension does not grow with the number of vertices. In this talk, we bound the metric dimension of a class of circulant graphs and their Cartesian products. This is joint work with my student Kevin Chau.

FARZANEH PIRI, University of Semnan
Perfect 2-coloring of k-regular graphs  [PDF]

we study perfect colorings of k-regular graphs in two colors. In particular, we also investigate perfect 2-colorings of 4-regular graphs; and also we obtain perfect 2-colorings for some special series of Cartesian product graphs.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology