A survey on the generalized connectivity of graphs

2012/07/08 by Xueliang Li, Li, Xueliang, Yaping Mao +1 · 3 citations
Computer Science · Mathematics · #05C05 #05C35 #05C40 #05C70 #05C75 #05C76 #05C80 #05C85 #68M10 #68Q25 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C05 #msc:05C35 #msc:05C40 #msc:05C70 #msc:05C75 #msc:05C76 #msc:05C80 #msc:05C85 #msc:68M10 #msc:68Q25 #msc:68R10

paper · pdf · doi:10.48550/arxiv.1207.1838

51 pages. arXiv admin note: text overlap with arXiv:1303.3881 by other authors

openalex publication_date 2012/07/08 · arxiv created 2015/08/31 · arxiv updated 2015/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The generalized k-connectivity κ_k(G) of a graph G was introduced by Hager before 1985. As its a natural counterpart, we introduced the concept of generalized edge-connectivity λ_k(G), recently. In this paper we summarize the known results on the generalized connectivity and generalized edge-connectivity. After an introductory section, the paper is then divided into nine sections: the generalized (edge-)connectivity of some graph classes, algorithms and computational complexity, sharp bounds of κ_k(G) and λ_k(G), graphs with large generalized (edge-)connectivity, Nordhaus-Gaddum-type results, graph operations, extremal problems, and some results for random graphs and multigraphs. It also contains some conjectures and open problems for further studies.

Citations

• The minimal size of a graph with generalized connectivity κ₃ = 2
• The generalized 3-connectivity of random graphs
• The generalized 3-connectivity of Cartesian product graphs
• Note on packing of edge-disjoint spanning trees in sparse random graphs
• On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices
• �ber die Maximalzahl kreuzungsfreierH-Wege
• On extremal graphs with at most ℓ internally disjoint Steiner trees connecting any n-1 vertices
• Arboricity and spanning-tree packing in random graphs with an application to load balancing

Cited by

• Further hardness results on the generalized connectivity of graphs
• Graphs with large generalized (edge-)connectivity
• Path connectivity of line graphs

Related

• Graphs with large generalized (edge-)connectivity
• Further hardness results on the generalized connectivity of graphs
• On the generalized (edge-)connectivity of graphs
• Extremality and Sharp Bounds for the k-edge-connectivity of Graphs
• The generalized 3-(edge) connectivity of total graphs