首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Maximally edge-connected and vertex-connected graphs and digraphs: A survey
Authors:Angelika Hellwig
Institution:a Institut für Medizinische Statistik, Universitätsklinikum der RWTH Aachen, Pauwelsstraße 30, 52074 Aachen, Germany
b Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany
Abstract:Let D be a graph or a digraph. If δ(D) is the minimum degree, λ(D) the edge-connectivity and κ(D) the vertex-connectivity, then κ(D)?λ(D)?δ(D) is a well-known basic relationship between these parameters. The graph or digraph D is called maximally edge-connected if λ(D)=δ(D) and maximally vertex-connected if κ(D)=δ(D). In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively.
Keywords:Connectivity  Edge-connectivity  Vertex-connectivity  Restricted connectivity  Conditional connectivity  Super-edge-connectivity  Local-edge-connectivity  Minimum degree  Degree sequence  Diameter  Girth  Clique number  Line graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号