The Maximum degree of series-parallel graphs

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/13125

Título:	The Maximum degree of series-parallel graphs
Autor/a:	Drmota, Michael; Giménez Llach, Omer; Noy Serrano, Marcos
Otros autores:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. MD - Matemàtica Discreta; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
Abstract:	We prove that the maximum degree Δn of a random series-parallel graph with n vertices satisfies Δn/ log n → c in probability, and EΔn ∼ c log n for a computable constant c > 0. The same kind of result holds for 2-connected series-parallel graphs, for outerplanar graphs, and for 2-connected outerplanar graphs.
Abstract:	Peer Reviewed
Materia(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria -Graph theory -Combinatorial analysis -Grafs, Teoria de -Configuracions i dissenys combinatòrics -05C Graph theory -05B Designs and configurations
Derechos:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Tipo de documento:	Artículo - Versión publicada Artículo
Compartir: