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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/588550
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact