Journal article icon

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:
Publisher copy:
10.1016/j.ejc.2016.05.005

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Statistics
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Publisher:
Elsevier Publisher's website
Journal:
European Journal of Combinatorics Journal website
Volume:
58
Pages:
96-106
Publication date:
2016-06-11
Acceptance date:
2016-05-15
DOI:
EISSN:
1095-9971
ISSN:
0195-6698
Source identifiers:
499851
Keywords:
Pubs id:
pubs:499851
UUID:
uuid:ce5c9c3b-e5bc-4545-ac70-bd10298c3999
Local pid:
pubs:499851
Deposit date:
2016-07-09

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP