Premium
Extremal graphs in connectivity augmentation
Author(s) -
Jordán Tibor
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199907)31:3<179::aid-jgt3>3.0.co;2-7
Subject(s) - combinatorics , mathematics , vertex (graph theory) , undirected graph , connectivity , graph , vertex connectivity , discrete mathematics , integer (computer science) , computer science , programming language
Let A ( n, k, t ) denote the smallest integer e for which every k ‐connected graph on n vertices can be made ( k + t )‐connected by adding e new edges. We determine A ( n, k, t ) for all values of n, k , and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A ( n, k , 1) for all values of n and k . We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999