Let G be a simple graph. A G-design of order n is a pair (X, B) where B is a collection of subgraphs (blocks), each isomorphic to G, which partitions the edge set of the complete undirected graph K_n with vertex set X. The G-design (X_1,B_1) is said to be embedded in the G-design (X_2,B_2) provided X_2 and B_2 containe X_1 and B_2, respectively ((X_1,B_1) is also said a subdesign of (X_2,B_2)). Let N(G) denote the set of integers n such that there exists a G-design of order n. A natural question to ask is: given n,m in N(G), with m > n, and a G-design (X, B) of order n, does exists a G-design of order m containing (X, B) as subdesign? Doyen and Wilson were the first to pose this problem for G = K_3 (Steiner triple systems) and in 1973 they showed that given n,m in N(K_3) then any Steiner triple system of order n can be embedded in a Steiner triple system of order m if and only if m > 2n + 1 or m = n. Over the years, any such problem has come to be called a "Doyen-Wilson problem". Here a complete solution of the Doyen-Wilson problem is given for kite systems.

The Doyen-Wilson theorem for kite systems

LO FARO, Giovanni;TRIPODI, Antoinette
2006-01-01

Abstract

Let G be a simple graph. A G-design of order n is a pair (X, B) where B is a collection of subgraphs (blocks), each isomorphic to G, which partitions the edge set of the complete undirected graph K_n with vertex set X. The G-design (X_1,B_1) is said to be embedded in the G-design (X_2,B_2) provided X_2 and B_2 containe X_1 and B_2, respectively ((X_1,B_1) is also said a subdesign of (X_2,B_2)). Let N(G) denote the set of integers n such that there exists a G-design of order n. A natural question to ask is: given n,m in N(G), with m > n, and a G-design (X, B) of order n, does exists a G-design of order m containing (X, B) as subdesign? Doyen and Wilson were the first to pose this problem for G = K_3 (Steiner triple systems) and in 1973 they showed that given n,m in N(K_3) then any Steiner triple system of order n can be embedded in a Steiner triple system of order m if and only if m > 2n + 1 or m = n. Over the years, any such problem has come to be called a "Doyen-Wilson problem". Here a complete solution of the Doyen-Wilson problem is given for kite systems.
2006
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/11570/1677968
 Attenzione

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

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