dc.contributor
Centre de Recerca Matemàtica
dc.contributor.author
McDiarmid, Colin
dc.date.accessioned
2008-07-09T16:50:38Z
dc.date.accessioned
2024-09-19T13:19:03Z
dc.date.available
2008-07-09T16:50:38Z
dc.date.available
2024-09-19T13:19:03Z
dc.identifier.uri
http://hdl.handle.net/2072/9069
dc.description.abstract
Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that
the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1, . . . , n}, then with probability tending to 1 as n → ∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components.
cat
dc.format.extent
201070 bytes
dc.format.mimetype
application/pdf
dc.publisher
Centre de Recerca Matemàtica
ca
dc.relation.ispartofseries
Prepublicacions del Centre de Recerca Matemàtica;722
dc.rights
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/)
cat
dc.subject.other
Grafs, Teoria dels
ca
dc.title
Random graphs on surfaces
ca
dc.type
info:eu-repo/semantics/preprint
ca
