Journal article
Random graphs from a block-stable class
- Abstract:
- A class of graphs is called block-stable when a graph is in the class if and only if each of its blocks is. We show that, as for trees, for most $n$-vertex graphs in such a class, each vertex is in at most $(1+o(1)) \log n / \log\log n$ blocks, and each path passes through at most $5 (n \log n)^{1/2}$ blocks. These results extend to `weakly block-stable' classes of graphs.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 342.2KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.ejc.2016.05.005
Authors
- Publisher:
- Elsevier
- Journal:
- European Journal of Combinatorics More from this journal
- Volume:
- 58
- Pages:
- 96-106
- Publication date:
- 2016-06-11
- Acceptance date:
- 2016-05-15
- DOI:
- EISSN:
-
1095-9971
- ISSN:
-
0195-6698
- Keywords:
- Pubs id:
-
pubs:499851
- UUID:
-
uuid:ce5c9c3b-e5bc-4545-ac70-bd10298c3999
- Local pid:
-
pubs:499851
- Source identifiers:
-
499851
- Deposit date:
-
2016-07-09
Terms of use
- Copyright holder:
- Elsevier
- Copyright date:
- 2016
- Notes:
- © 2016 Elsevier Inc. All rights reserved. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: [10.1016/j.ejc.2016.05.005]
If you are the owner of this record, you can report an update to it here: Report update to this record