Utilizad este identificador para citar o enlazar este documento: http://hdl.handle.net/2072/9069

Random graphs on surfaces
McDiarmid, Colin
Centre de Recerca Matemàtica
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.
11-2006
519.1 - Teoria general de l'anàlisi combinatòria. Teoria de grafs
Grafs, Teoria dels
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/)
Edición preliminar
Centre de Recerca Matemàtica
Prepublicacions del Centre de Recerca Matemàtica;722
         

Documentos con el texto completo de este documento

Ficheros Tamaño Formato
Pr722.pdf 201.0 KB PDF

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a