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 Connect in order to contact the contributor
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

Collections

Citation

C.R. Subramanian. Paths of specified length in random k-partite graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, Vol. 4 no. 2 (2), pp.133-138. ⟨10.46298/dmtcs.286⟩. ⟨hal-00958953⟩

Share

Metrics

Record views

35

Files downloads

503