Let $\Gamma'$ be a subgraph of a graph $\Gamma$. We define a \emph{down-link} from a $(K_v,\Gamma)$-design $\cB$ to a $(K_n,\Gamma')$-design $\cB'$ as a map $f:\cB\to \cB'$ mapping any block of $\cB$ into one of its subgraphs. This is a new concept, closely related with both the notion of \emph{metamorphosis} and that of \emph{embedding}. In the present paper we study down-links in general and prove that any $(K_v,\Gamma)$-design might be down-linked to a $(K_n,\Gamma')$-design, provided that $n$ is admissible and large enough. We also show that if $\Gamma'=P_3$, it is always possible to find a down-link to a design of order at most $v+3$. This bound is then improved for several classes of graphs $\Gamma$, by providing explicit constructions.

### Down-linking $(K_v,\Gamma)$-designs to $P_3$-designs

#### Abstract

Let $\Gamma'$ be a subgraph of a graph $\Gamma$. We define a \emph{down-link} from a $(K_v,\Gamma)$-design $\cB$ to a $(K_n,\Gamma')$-design $\cB'$ as a map $f:\cB\to \cB'$ mapping any block of $\cB$ into one of its subgraphs. This is a new concept, closely related with both the notion of \emph{metamorphosis} and that of \emph{embedding}. In the present paper we study down-links in general and prove that any $(K_v,\Gamma)$-design might be down-linked to a $(K_n,\Gamma')$-design, provided that $n$ is admissible and large enough. We also show that if $\Gamma'=P_3$, it is always possible to find a down-link to a design of order at most $v+3$. This bound is then improved for several classes of graphs $\Gamma$, by providing explicit constructions.
##### Scheda breve Scheda completa Scheda completa (DC)
2013
File in questo prodotto:
File

accesso aperto

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 510.9 kB
Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/44575