Edge proximity and matching extension in projective planar graphs

A graph $G$ with at least $2m+2$ vertices is said to be distance $d$ $m$-extendable if, for any matching $M$ of $G$ with $m$ edges in which the edges lie at distance at least $d$ pairwise, there exists a perfect matching of $G$ containing $M$. In this paper we prove that every 5-connected triangulation on the projective plane of even order is distance 3 7-extendable and distance 4 $m$-extendable for any $m$.     

Circuits through prescribed edges

We prove that a connected graph $G$ contains a circuit—a closed walk that repeats no edges—through any $k$ prescribed edges if and only if $G$ contains no odd cut of size at most $k$.     

Flexibility of planar graphs of girth at least six

Let $G$ be a planar graph with a list assignment $L$. Suppose a preferred color is given for some of the vertices. We prove that if $G$ has girth at least six and all lists have size at least three, then there exists an $L$-coloring respecting at least a constant fraction of the preferences.     

Edge Kempe equivalence of regular graph covers

Let $G$ be a finite $d$-regular graph with a proper edge coloring. An edge Kempe switch is a new proper edge coloring of $G$ obtained by switching the two colors along some bichromatic cycle. We prove that any other edge coloring can be obtained by performing finitely many edge Kempe switches, provided that $G$ is replaced with a suitable finite covering graph. The required covering degree is bounded above by a constant depending only on $d$.     

An Ore-type condition for large k-factor and disjoint perfect matchings

Win conjectured that a graph $G$ on $n$ vertices contains $k$ disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least $n+k-2$, where $n$ is even and $n\ge k+2$. In this paper, we prove that Win's conjecture is true for $k\ge n∕2$, where $n$ is sufficiently large. To show this result, we prove a theorem on $k$-factor in a graph under some Ore-type condition. Our main tools include Tutte's $k$-factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization and the solution to the long-standing 1-factor decomposition conjecture.     

Hamiltonian cycles in k-partite graphs

Chen et al determined the minimum degree threshold for which a balanced $k$-partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary $k$-partite graphs in that all parts have at most $n/2$ vertices (a necessary condition). To do this, we first prove a general result that both simplifies the process of checking whether a graph $G$ is a robust expander and gives useful structural information in the case when $G$ is not a robust expander. Then we use this result to prove that any $k$-partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.     

Reconfiguration of connected graph partitions

Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $k\ge 1$, a $k$-district map of $G$ is a partition of $V\left(G\right)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is PSPACE-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial lengths is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that take a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.     

Between the enhanced power graph and the commuting graph

The purpose of this note is to define a graph whose vertex set is a finite group $G$, whose edge set is contained in that of the commuting graph of $G$ and contains the enhanced power graph of $G$. We call this graph the deep commuting graph of $G$. Two elements of $G$ are joined in the deep commuting graph if and only if their inverse images in every central extension of $G$ commute. We give conditions for the graph to be equal to either of the enhanced power graph and the commuting graph, and show that automorphisms of $G$ act as automorphisms of the deep commuting graph.     

The optimal general upper bound for the distinguishing index of infinite graphs

The distinguishing index $D\prime \left(G\right)$ of a graph $G$ is the least cardinal number $d$ such that $G$ has an edge-coloring with $d$ colors, which is preserved only by the trivial automorphism. We prove a general upper bound $D\prime \text{◂≤▸}\left(G\right)\le \mathrm{\Delta }-1$ for any connected infinite graph $G$ with finite maximum degree $\mathrm{\Delta }\ge 3$. This is in contrast with finite graphs since for every $\mathrm{\Delta }\ge 3$ there exist infinitely many connected, finite graphs $G$ with $\text{◂,▸}D\prime \left(G\right)=\mathrm{\Delta }$. We also give examples showing that this bound is sharp for any maximum degree $\mathrm{\Delta }$.