Connected Even Factors in the Square of Essentially 2-Edge-connected Graph

  • Jan Ekstein
  • Baoyindureng Wu
  • Liming Xiong
Keywords: Connected even factors, (Essentially) 2-edge connected graphs, Square of graphs


An essentially $k$-edge connected graph $G$ is a connected graph such that deleting less than $k$ edges from $G$ cannot result in two nontrivial components. In this paper we prove that if an essentially 2-edge-connected graph $G$ satisfies that for any pair of leaves at distance 4 in $G$ there exists another leaf of $G$ that has distance 2 to one of them, then the square $G^2$ has a connected even factor with maximum degree at most 4. Moreover we show that, in general, the square of essentially 2-edge-connected graph does not contain a connected even factor with bounded maximum degree.
Article Number