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

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

Algebraic techniques for least squares problems in commutative quaternionic theory

Due to the rise of commutative quaternion in Hopfield neural networks, digital signal, and image processing, one encounters the approximate solution problems of the commutative quaternion linear equations $AX\approx B$ and $AXC\approx B$. This paper, by means of real representation and complex representation of commutative quaternion matrices, introduces concepts of norms of commutative quaternion matrices and derives two algebraic techniques for finding solutions of least squares problems in commutative quaternionic theory.     

Colorings versus list colorings of uniform hypergraphs

Let $r$ be an integer with $r\ge 2$ and $G$ be a connected $r$-uniform hypergraph with $m$ edges. By refining the broken cycle theorem for hypergraphs, we show that if $k>\text{◂/▸}\frac{m-1}{\ln (1+\sqrt{2})}\approx \text{◂⋅▸}1.135\left(m-1\right)$, then the $k$-list assignment of $G$ admitting the fewest colorings is the constant list assignment. This extends the previous results of Donner, Thomassen, and the current authors for graphs.