Premium
Constructing a bipartite graph of maximum connectivity with prescribed degrees
Author(s) -
Asano Takao
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199707)29:4<245::aid-net7>3.0.co;2-f
Subject(s) - bipartite graph , combinatorics , mathematics , edge transitive graph , vertex (graph theory) , discrete mathematics , sequence (biology) , graph , line graph , graph power , chemistry , biochemistry
A pair of nonnegative integer sequences { D 1 , D 2 } with D 1 = ( d 1,1 , d 1,2 , …, dnD 2 = ( d 2,1 , d 2,2 , …, dna bipartite graphical sequence, if there is a bipartite graph G with degrees{ D 1 , D 2 } (i.e., G has two independent vertex sets V 1 = { v 1,1 , v 1,2 , …, vnV 2 = { v 2,1 , v 2,2 , …, vnsuch that di , ji the degree of vertex v i, jiG for each i = 1, 2 and j i = 1, 2, …, n i ). In other words,{ D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 × n 2 matrix of 0's and 1's havingdjj 1 and djj 2 . The connectivity κ({ 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 κ({ D 1 , D 2 })‐connected bipartite graph with degrees { D 1 , D 2 } ( n = n 1 + n 2 ). © 1997 John Wiley & Sons, Inc.