Let F = {Fα : α ∈ A} be a family of infinite graphs, together with Λ. The Factorization Problem FP(F, Λ) asks whether F 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 F is a countably infinite family, we show that FP(F, R) is solvable if and only if each graph in F has no finite dominating set. We also prove that FP(F, Kℵ) admits a solution whenever the cardinality of F 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 F are finite. More precisely, we show that there is no factorization of KN 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.
Factorizing the Rado graph and infinite complete graphs
Costa S.
;Traetta T.
2023-01-01
Abstract
Let F = {Fα : α ∈ A} be a family of infinite graphs, together with Λ. The Factorization Problem FP(F, Λ) asks whether F 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 F is a countably infinite family, we show that FP(F, R) is solvable if and only if each graph in F has no finite dominating set. We also prove that FP(F, Kℵ) admits a solution whenever the cardinality of F 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 F are finite. More precisely, we show that there is no factorization of KN 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.