Anthony Bonato ; Jeannette Janssen - Infinite limits and folding

dmtcs:3410 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3410
Infinite limits and foldingArticle

Authors: Anthony Bonato 1; Jeannette Janssen 2

  • 1 Department of Mathematics, Wilfrid Laurier University
  • 2 Department of Mathematics and Statistics [Canada]

We study infinite limits of graphs generated by the duplication model for biological networks. We prove that with probability 1, the sole nontrivial connected component of the limits is unique up to isomorphism. We describe certain infinite deterministic graphs which arise naturally from the model. We characterize the isomorphism type and induced subgraph structure of these infinite graphs using the notion of dismantlability from the theory of vertex pursuit games, and graph homomorphisms.

https://doi.org/10.46298/dmtcs.3410
Source: HAL:hal-01184367v1
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: massive networks,duplication model,infinite random graph,folding,adjacency property,graph homomorphism,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Share and export

Consultation statistics

This page has been seen 169 times.
This article's PDF has been downloaded 168 times.