Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958953
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:52:33 PM
Last modification on : Saturday, August 11, 2018 - 11:22:01 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:04:05 PM

File

dm040206.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

112

Files downloads

637