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 in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11379/44575
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact