Equitable factorizations of edge-connected graphs

Morteza Hasanvand

paper

Equitable factorizations of edge-connected graphs

arXiv:1906.04325

Abstract

In this paper, we show that every $(3 k - 3)$ -edge-connected graph $G$ , under a certain condition on whose degrees, can be edge-decomposed into $k$ factors $G_{1}, \dots, G_{k}$ such that for each vertex $v \in V (G_{i})$ , $∣ d_{G_{i}} (v) - d_{G} (v) / k ∣ < 1$ , where $1 \leq i \leq k$ . As application, we deduce that every $6$ -edge-connected graph $G$ can be edge-decomposed into three factors $G_{1}$ , $G_{2}$ , and $G_{3}$ such that for each vertex $v \in V (G_{i})$ , $∣ d_{G_{i}} (v) - d_{G} (v) /3∣ < 1$ , unless $G$ has exactly one vertex $z$ with $d_{G} (z) \neq \equiv 3 0$ . Next, we show that every odd- $(3 k - 2)$ -edge-connected graph $G$ can be edge-decomposed into $k$ factors $G_{1}, \dots, G_{k}$ such that for each vertex $v \in V (G_{i})$ , $d_{G_{i}} (v)$ and $d_{G} (v)$ have the same parity and $∣ d_{G_{i}} (v) - d_{G} (v) / k ∣ < 2$ , where $k$ is an odd positive integer and $1 \leq i \leq k$ . Finally, we give a sufficient edge-connectivity condition for a graph $G$ to have a parity factor $F$ with specified odd-degree vertices such that for each vertex $v$ , $∣ d_{F} (v) - ε d_{G} (v) ∣ < 2$ , where $ε$ is a real number with $0 < ε < 1$ .