Infinite limits and folding
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....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3410/pdf |
| _version_ | 1797270377700786176 |
|---|---|
| author | Anthony Bonato Jeannette Janssen |
| author_facet | Anthony Bonato Jeannette Janssen |
| author_sort | Anthony Bonato |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:18Z |
| format | Article |
| id | doaj.art-c9529f75492543c19cf7f3508c883887 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:18Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-c9529f75492543c19cf7f3508c8838872024-03-07T14:41:15ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AE,...Proceedings10.46298/dmtcs.34103410Infinite limits and foldingAnthony Bonato0Jeannette Janssen1Department of Mathematics, Wilfrid Laurier UniversityDepartment 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://dmtcs.episciences.org/3410/pdfmassive networksduplication modelinfinite random graphfoldingadjacency propertygraph homomorphism[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Anthony Bonato Jeannette Janssen Infinite limits and folding Discrete Mathematics & Theoretical Computer Science 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] |
| title | Infinite limits and folding |
| title_full | Infinite limits and folding |
| title_fullStr | Infinite limits and folding |
| title_full_unstemmed | Infinite limits and folding |
| title_short | Infinite limits and folding |
| title_sort | infinite limits and folding |
| topic | 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] |
| url | https://dmtcs.episciences.org/3410/pdf |
| work_keys_str_mv | AT anthonybonato infinitelimitsandfolding AT jeannettejanssen infinitelimitsandfolding |