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.     

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.     

Extending regular edge-colorings of complete hypergraphs

A coloring (partition) of the collection $(\genfrac{}{}{0.0pt}{}{X}{h})$ of all $h$-subsets of a set $X$ is $r$-regular if the number of times each element of $X$ appears in each color class (all sets of the same color) is the same number $r$. We are interested in finding the conditions under which a given $r$-regular coloring of $(\genfrac{}{}{0.0pt}{}{X}{h})$ is extendible to an $s$-regular coloring of $(\genfrac{}{}{0.0pt}{}{Y}{h})$ for $s⩾r$ and $Y⊋X$. The case $\text{◂,▸}h=2,r=s=1$ was solved by Cruse, and due to its connection to completing partial symmetric latin squares, many related problems are extensively studied in the literature, but very little is known for $h⩾3$. The case $r=s=1$ was solved by Häggkvist and Hellgren, settling a conjecture of Brouwer and Baranyai. The cases $h=2$ and $h=3$ were solved by Rodger and Wantland, and Bahmanian and Newman, respectively. In this paper, we completely settle the cases $h=4,\text{◂⩾▸}|Y|⩾4|X|$ and $h=5,\text{◂⩾▸}|Y|⩾5|X|$.     

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.     

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$.     

The inverse conductivity problem via the calculus of functions of bounded variation

In this work, a novel approach for the solution of the inverse conductivity problem from one and multiple boundary measurements has been developed on the basis of the implication of the framework of $BV$ functions. The space of the functions of bounded variation is recommended here as the most appropriate functional space hosting the conductivity profile under reconstruction. For the numerical investigation of the inversion of the inclusion problem, we propose and implement a suitable minimization scheme of an enriched—constructed herein—functional, by exploiting the inner structure of $BV$ space. Finally, we validate and illustrate our theoretical results with numerical experiments.