For an undirected graph G and a natural number n, a G-design of order n is an edge partition of the complete graph Kn with n vertices into subgraphs G1;G2; : : : ; each isomorphic to G. A set T V(Kn) is called a blocking set if it meets the vertex set V (Gi)of each Gi in the decomposition, but contains none of them. In a previous paper [J. Combin. Designs 4 (1996), 135{142] the rst and third authors proved that if G is a cycle, then there exists a G-design without blocking sets. Here we extend this theorem for all graphs G,moreover we prove that for every G and every integer k 2 there exists a non-k-colorable G-design.
G-designs without blocking sets
MILICI, Salvatore;
2014-01-01
Abstract
For an undirected graph G and a natural number n, a G-design of order n is an edge partition of the complete graph Kn with n vertices into subgraphs G1;G2; : : : ; each isomorphic to G. A set T V(Kn) is called a blocking set if it meets the vertex set V (Gi)of each Gi in the decomposition, but contains none of them. In a previous paper [J. Combin. Designs 4 (1996), 135{142] the rst and third authors proved that if G is a cycle, then there exists a G-design without blocking sets. Here we extend this theorem for all graphs G,moreover we prove that for every G and every integer k 2 there exists a non-k-colorable G-design.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.