ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.02
https://doi.org/10.26493/1855-3974.2616.4a9
(Also available at http://amc-journal.eu)
Factorizing the Rado graph and
infinite complete graphs*
Simone Costa † , Tommaso Traetta
DICATAM - Sez. Matematica, Università degli Studi di Brescia,
Via Valotti 9, I-25123 Brescia, Italy
Received 30 April 2021, accepted 18 January 2023, published online 1 August 2023
Abstract
Let F = {Fα : α ∈ A} be a family of infinite graphs, together with Λ. The Factor-
ization 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 dom-
ination 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.
Keywords: Factorization problem, resolution problem, Rado graph, infinite graphs.
Math. Subj. Class. (2020): 05C63, 05C70
*The authors gratefully acknowledge support from GNSAGA of Istituto Nazionale di Alta Matematica.
†Corresponding author.
E-mail addresses: simone.costa@unibs.it (Simone Costa), tommaso.traetta@unibs.it (Tommaso Traetta)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.02
https://doi.org/10.26493/1855-3974.2616.4a9
(Dostopno tudi na http://amc-journal.eu)
Faktorizacija Radojevega grafa in
neskončnih polnih grafov*
Simone Costa † , Tommaso Traetta
DICATAM - Sez. Matematica, Università degli Studi di Brescia,
Via Valotti 9, I-25123 Brescia, Italy
Prejeto 30. aprila 2021, sprejeto 18. januarja 2023, objavljeno na spletu 1. avgusta 2023
Povzetek
Naj bo F = {Fα : α ∈ A} družina neskončnih grafov, vključno z grafom Λ. Problem
faktorizacije FP (F ,Λ) sprašuje, ali se da F predstaviti kot faktorizacijo grafa Λ, z drugimi
besedami, ali obstaja takšna faktorizacija G = {Γα : α ∈ A} grafa Λ, da je vsak Γα kopija
grafa Fα.
Ta problem preučujemo ob pogoju, da je Λ bodisi Radojev graf R bodisi polni graf Kℵ
neskončnega reda ℵ. Pokažemo, da je, kadar je F števno neskončna družina, FP (F , R)
rešljiva natanko takrat, ko noben graf v F nima končne dominacijske množice. Dokažemo
tudi, da je FP (F ,Kℵ) rešljiva, kadar kardinalnost družine F sovpada z redom in domi-
nacijskimi števili njenih grafov.
Za števne polne grafe dokažemo nekaj rezultatov o neobstoju, kadar so dominacijska
števila grafov iz družine F končna. Natančneje, pokažemo da se KN ne da faktorizirati
v kopije k-zvezd (oz. v točkovno disjunktno unijo k števnih zvezd), kadar je k = 1, 2,
medtem ko takšna faktorizacija obstaja, kadar je k ≥ 4, kar pomeni, da problem fakto-
rizacije za k = 3 ostaja odprt.
Določimo tudi zadostne pogoje za ureditev grafov dekompozicije v rešljivostne razrede.
Ključne besede: Problem faktorizacije, problem rešljivosti, Radojev graf, neskončni grafi.
Math. Subj. Class. (2020): 05C63, 05C70
*Avtorja sta hvaležno za podporo GNSAGA of Istituto Nazionale di Alta Matematica.
†Kontaktni avtor.
E-poštna naslova: simone.costa@unibs.it (Simone Costa), tommaso.traetta@unibs.it (Tommaso Traetta)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/