2025/03/22 by Jingyu Zheng, Zheng, Jingyu, Baoyindureng Wu +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Finite Group Theory Research
paper · pdf · doi:10.48550/arxiv.2503.17676
A graph G=(V,E) is said to be odd (or even, resp.) if dG(v) is odd (or even, resp.) for any v∈ V. Trivially, the order of an odd graph must be even. In this paper, we show that every 4-edge connected graph of even order has a connected odd factor. A spanning tree T of G is called a homeomorphically irreducible spanning tree (HIST by simply) if T contains no vertex of degree two. Trivially, an odd spanning tree must be a HIST. In 1990, Albertson, Berman, Hutchinson, and Thomassen showed that every connected graph of order n with δ(G)≥ min\\frac n 2, 4√(2n)\ contains a HIST. We show that every complete bipartite graph with both parts being even has no odd spanning tree, thereby for any even integer n divisible by 4, there exists a graph of order n with the minimum degree \frac n 2 having no odd spanning tree. Furthermore, we show that every graph of order n with δ(G)≥ \frac n 2 +1 has an odd spanning tree. We also characterize all split graphs having an odd spanning tree. As an application, for any graph G with diameter at least 4, G has a spanning odd double star. Finally, we also give a necessary and sufficient condition for a triangle-free graph G whose complement contains an odd spanning tree. A number of related open problems are proposed.