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.
2013
2011
MIUR (compresi PRIN FIRB,FISR)
PE1_5 Geometry
Esperti anonimi
Inglese
Internazionale
STAMPA
90
3
21
19
Preprint disponibile anche come http://arxiv.org/abs/1004.4127
Graph decompositions; metamorphoses; designs; embeddings
Ateneo di appartenenza
3
info:eu-repo/semantics/article
262
Benini, Anna; Giuzzi, Luca; Pasotti, Anita
1 Contributo su Rivista::1.1 Articolo in rivista
open
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