Constructing a bipartite graph of maximum connectivity with prescribed degrees

✍ Scribed by Asano, Takao

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 328 KB
• Volume: 29
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199707)29:4<245::aid-net7>3.0.co;2-f

✦ Synopsis

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets

In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and d 2j 2 1's in column j 2 . The connectivity k({D 1 , D 2 }) of a bipartite graphical sequence {D 1 , D 2 } is defined to be the maximum integer k such that there is a k-connected bipartite graph with degrees {D 1 , D 2 }. In this paper, we present a characterization of a k-connected bipartite graphical sequence and an O(n log log n) time algorithm, for a given bipartite graphical sequence { D 1 , D 2 }, to construct a k({D 1 , D 2 })-connected bipartite graph with degrees { D 1 , D 2 } (n Å n 1 / n 2 ).