Abstract | ||
---|---|---|
The bipartite regulation number br( G ) of a bipartite graph G with maximum degree d is the minimum number of vertices required to add to G to construct a d -regular bipartite supergraph of G . It is shown that if G is a connected m -by- n bipartite graph with m ⩽ n and n − m ⩾ d − 1, then br( G ) = n − m . If. however, n − m ⩽ d − 2, the br( G ) = n ⇔ m + 2 l for some l satisfying 0 ⩽ l ⩽ d − ( n − m ). Conversely, if l , k and d (>2) are integers such that 0 ⩽ l ⩽ k and 2 ⩽ k ⩽ d , then there is an connected m -by- n bipartite graph G of maximum degree d for which br( G ) = n − m + 2 l , for some m and n with k = d − ( n − m ). |
Year | DOI | Venue |
---|---|---|
1986 | 10.1016/0012-365X(86)90110-X | Discrete Mathematics |
Keywords | Field | DocType |
bipartite regulation number | Graph theory,Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Bipartite graph,Degree (graph theory),Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
62 | 2 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Y Alavi | 1 | 0 | 0.34 |
G Chartrand | 2 | 0 | 0.34 |
L Lesniak | 3 | 0 | 0.34 |
R Oellermann | 4 | 0 | 0.34 |