Paths of specified length in random k-partite graphs

Abstract : Fix positive integers k and l. Consider a random k-partite graph on n vertices obtained by partitioning the vertex set into V_i, (i=1, \ldots,k) each having size Ω (n) and choosing each possible edge with probability p. Consider any vertex x in any V_i and any vertex y. We show that the expected number of simple paths of even length l between x and y differ significantly depending on whether y belongs to the same V_i (as x does) or not. A similar phenomenon occurs when l is odd. This result holds even when k,l vary slowly with n. This fact has implications to coloring random graphs. The proof is based on establishing bijections between sets of paths.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.133-138
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958953
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:52:33
Dernière modification le : mercredi 29 novembre 2017 - 10:26:19
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:04:05

Fichier

dm040206.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958953, version 1

Collections

Citation

C.R. Subramanian. Paths of specified length in random k-partite graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.133-138. 〈hal-00958953〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

80