Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T06:12:23.312Z Has data issue: false hasContentIssue false
  • English
  • Français

A Note on the Stochastic Rank of a Bipartite Graph

Published online by Cambridge University Press:  20 November 2018

A.L. Dulmage  and
N.S. Mendelsohn
A.L. Dulmage
Affiliation:
University of Manitoba
N.S. Mendelsohn
Affiliation:
University of Manitoba
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A bipartite graph is a system consisting of two sets of vertices S and T and a set of edges K, each edge joining a vertex of S to a vertex of T. A set U of edges of K is said to be independent if no two edges of U have a vertex in common. The largest possible number of independent edges has been variously called the exterior dimension [3], term rank [4, 5, 7], etc. This number is the same as the smallest number of vertices in a set W such that each edge of K has at least one of its vertices in W. The edges of a finite bipartite graph can be represented as a set of cells in a matrix as follows. If S = a1, a2, …, an T = b1, b2, … bm, the edges of K are represented by some of the cells of an n by m matrix as follows: if K contains the edge joining ai to bj then the (i, j)th cell of the matrix represents this edge. It is convenient sometimes to represent the set K by a matrix A with real entries aij where aij = 0 if ai is not joined to bj in K and aij > 0 if ai is joined to bj in K. Any non-null graph K will have infinitely many matrix representations.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 2 , Issue 3 , 01 September 1959 , pp. 159 - 162
Copyright
Copyright © Canadian Mathematical Society 1959

References

1. Konig, D., Theorie der endlichen und unendlichen Graphen, (New York, 1950).Google Scholar
2. Dulmage, A.L. and Halperin, I., On a theorem of Frobenius-- Konig and J. von Neumann's game of hide and seek, Trans. Roy. Soc. Can. Ser. III, 49 (1955), 23-29.Google Scholar
3. Dulmage, A.L. and Mendelsohn, N.S., Coverings of bipartite graphs, Can. J. Math. 10 (1958), 517-534.Google Scholar
4. Dulmage, A.L. and Mendelsohn, N.S., The term and stochastic ranks of a matrix, Can. J. Math. 11 (1959), 269-279.Google Scholar
5. Ore, O., Graphs and matching theorems, Duke Math. J. 22 (1955), 625-639.Google Scholar
6. Ryser, H.J., Combinatorial properties of matrices of zeros and ones, Can. J. Math. 9 (1957), 371-377.Google Scholar
7. Ryser, H.J., The term rank of a matrix, Can. J. Math. 10 (1957), 57-65.Google Scholar