Random Oxford graphs

Published

Journal Article

Inspired by a concept in comparative genomics, we investigate properties of randomly chosen members of G1(m, n, t), the set of bipartite graphs with m left vertices, n right vertices, t edges, and each vertex of degree at least one. We give asymptotic results for the number of such graphs and the number of (i, j) trees they contain. We compute the thresholds for the emergence of a giant component and for the graph to be connected. © 2005 Elsevier B.V. All rights reserved.

Full Text

Duke Authors

Cited Authors

  • Blasiak, J; Durrett, R

Published Date

  • August 1, 2005

Published In

Volume / Issue

  • 115 / 8

Start / End Page

  • 1257 - 1278

International Standard Serial Number (ISSN)

  • 0304-4149

Digital Object Identifier (DOI)

  • 10.1016/j.spa.2005.03.008

Citation Source

  • Scopus