Data di Pubblicazione:
2012
Abstract:
Suppose $\Gamma'$ to be a subgraph of a graph $\Gamma$.
We define a \emph{sampling} of a $\Gamma$-design ${\fB}=(V,B)$ into a
$\Gamma'$-design ${\fB'}=(V,B')$ as a surjective map $\xi:B\to B'$
mapping each block of $B$ into one of its subgraphs.
A sampling will be called {\it regular} when the number of
preimages of each block of $B'$ under $\xi$ is a constant.
This new
concept is closely related with the classical notion of
\emph{embedding}, which has been extensively studied,
for many classes of graphs,
by several authors; see, for example, the survey \cite{Q2002a}.
Actually, a sampling $\xi$ might induce several embeddings
of the design $\fB'$ into $\fB$, although the converse is not
true in general.
In the present paper we study in more detail the behaviour of
samplings of $\Gamma$--complete designs of order $n$ into
$\Gamma'$--complete designs of the same order and show how
the natural necessary condition for the existence of a
regular sampling is actually sufficient. We also provide
some explicit constructions of samplings, as well as
propose further generalizations.
We define a \emph{sampling} of a $\Gamma$-design ${\fB}=(V,B)$ into a
$\Gamma'$-design ${\fB'}=(V,B')$ as a surjective map $\xi:B\to B'$
mapping each block of $B$ into one of its subgraphs.
A sampling will be called {\it regular} when the number of
preimages of each block of $B'$ under $\xi$ is a constant.
This new
concept is closely related with the classical notion of
\emph{embedding}, which has been extensively studied,
for many classes of graphs,
by several authors; see, for example, the survey \cite{Q2002a}.
Actually, a sampling $\xi$ might induce several embeddings
of the design $\fB'$ into $\fB$, although the converse is not
true in general.
In the present paper we study in more detail the behaviour of
samplings of $\Gamma$--complete designs of order $n$ into
$\Gamma'$--complete designs of the same order and show how
the natural necessary condition for the existence of a
regular sampling is actually sufficient. We also provide
some explicit constructions of samplings, as well as
propose further generalizations.
Tipologia CRIS:
1.1 Articolo in rivista
Keywords:
Graphs; complete designs; sampling
Elenco autori:
Giuzzi, Luca; Pasotti, Anita
Link alla scheda completa:
Link al Full Text:
Pubblicato in: