Geodesic
Random lifts of graphs are highly connected
Marcin Witkowski1
1Faculty of Mathematics and Computer Science Adam Mickiewicz University, ul. Umultowska 87, 61-614 Poznan, Poland
The electronic journal of combinatorics, Tome 20 (2013) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this note we study asymptotic properties of random lifts of graphs introduced by Amit and Linial as a new model of random graphs. Given a base graph $G$ and an integer $n$, a random lift of $G$ is obtained by replacing each vertex of $G$ by a set of $n$ vertices, and joining these sets by random matchings whenever the corresponding vertices of $G$ are adjacent. In this paper we study connectivity properties of random lifts. We show that the size of the largest topological clique in typical random lifts, with $G$ fixed and $n\rightarrow\infty$, is equal to the maximum degree of the core of $G$ plus one. A similar idea can be used to prove that for any graph $G$ with $\delta(G)\geq2k-1$ almost every random lift of $G$ is $k$-linked.
DOI : 10.37236/2783
Classification : 05C80, 05C40
Mots-clés : random graphs, lifts of graphs

Marcin Witkowski  1

1 Faculty of Mathematics and Computer Science Adam Mickiewicz University, ul. Umultowska 87, 61-614 Poznan, Poland 
@article{10_37236_2783,
     author = {Marcin Witkowski},
     title = {Random lifts of graphs are highly connected},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {2},
     doi = {10.37236/2783},
     zbl = {1266.05157},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2783/}
}
TY  - JOUR
AU  - Marcin Witkowski
TI  - Random lifts of graphs are highly connected
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2783/
DO  - 10.37236/2783
ID  - 10_37236_2783
ER  - 
%0 Journal Article
%A Marcin Witkowski
%T Random lifts of graphs are highly connected
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2783/
%R 10.37236/2783
%F 10_37236_2783
Marcin Witkowski. Random lifts of graphs are highly connected. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2783

Cité par Sources :