Factorizing the Rado graph and infinite complete graphs

Simone Costa ; Tommaso Traetta

Ars Mathematica Contemporanea, Tome 24 (2024) no. 1, article no. 02, 19 p.

Résumé

Let ℱ = {Fα : α ∈ A} be a family of infinite graphs, together with Λ. The Factorization Problem FP(ℱ,Λ) asks whether ℱ can be realized as a factorization of Λ, namely, whether there is a factorization G = {Γα : α ∈ A} of Λ such that each Γα is a copy of Fα. We study this problem when Λ is either the Rado graph R or the complete graph Kℵ of infinite order ℵ. When ℱ is a countably infinite family, we show that FP(ℱ,R) is solvable if and only if each graph in ℱ has no finite dominating set. We also prove that FP(ℱ,Kℵ) admits a solution whenever the cardinality of ℱ coincides with the order and the domination numbers of its graphs. For countable complete graphs, we show some non existence results when the domination numbers of the graphs in ℱ are finite. More precisely, we show that there is no factorization of Kℕ into copies of a k-star (that is, the vertex disjoint union of k countable stars) when k = 1, 2, whereas it exists when k ≥ 4, leaving the problem open for k = 3. Finally, we determine sufficient conditions for the graphs of a decomposition to be arranged into resolution classes.

Détail

DOI : 10.26493/1855-3974.2616.4a9

Keywords: Factorization Problem, resolution problem, Rado graph, infinite graphs