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
BENINI, Anna;GIUZZI, Luca;PASOTTI, Anita
2013-01-01
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.File | Dimensione | Formato | |
---|---|---|---|
down-link.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
DRM non definito
Dimensione
510.9 kB
Formato
Adobe PDF
|
510.9 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.