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

Connectivity: properties and structure
Balbuena Martínez, Maria Camino Teófila; Fàbrega Canudas, José; Fiol Mora, Miquel Àngel
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
Connectivity is one of the central concepts of graph theory, from both a theoret- ical and a practical point of view. Its theoretical implications are mainly based on the existence of nice max-min characterization results, such as Menger’s theorems. In these theorems, one condition which is clearly necessary also turns out to be sufficient. Moreover, these results are closely related to some other key theorems in graph theory: Ford and Fulkerson’s theorem about flows and Hall’s theorem on perfect matchings. With respect to the applications, the study of connectivity parameters of graphs and digraphs is of great interest in the design of reliable and fault-tolerant interconnection or communication networks. Since graph connectivity has been so widely studied, we limit ourselves here to the presentation of some of the key results dealing with finite simple graphs and digraphs. For results about infinite graphs and connectivity algorithms the reader can consult, for instance, Aharoni and Diestel [AhDi94], Gibbons [Gi85], Halin [Ha00], Henzinger, Rao, and Gabow [HeRaGa00], Wigderson [Wi92]. For further details, we refer the reader to some of the good textbooks and surveys available on the subject: Berge [Be76], Bermond, Homobono, and Peyrat [BeHoPe89], Frank [Fr90, Fr94, Fr95], Gross and Yellen [GrYe06], Hellwig and Volkmann [HeVo08], Lov ´asz [Lo93], Mader [Ma79], Oellermann [Oe96], Tutte [Tu66].
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
Graph theory
Graph Theory
Connectivity
Grafs, Teoria de
05C Graph theory
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/bookPart
CRC Press Taylor & Francis Group
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Balbuena Martínez, Maria Camino Teófila; Fàbrega Canudas, José; Fiol Mora, Miquel Àngel
Cámara Vallejo, Marc; Dalfó Simó, Cristina; Fàbrega Canudas, José; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Cámara Vallejo, Marc; Fàbrega Canudas, José; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Cámara Vallejo, Marc; Dalfó Simó, Cristina; Fàbrega Canudas, José; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest
Cámara Vallejo, Marc; Dalfó Simó, Cristina; Fàbrega Canudas, José; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest