Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T07:26:48.859Z Has data issue: false hasContentIssue false
  • English
  • Français

Connectivity and Reducibility of Graphs

Published online by Cambridge University Press:  20 November 2018

Diane M. Johnson ,
A. L. Dulmage  and
N. S. Mendelsohn
Diane M. Johnson
Affiliation:
University of Manitoba
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.

Corresponding to every graph, bipartite graph, or directed bipartite graph there exists a directed graph which is connected if and only if the original graph is connected.

In this paper, it is shown that for every directed graph there exists a certain bipartite graph such that the directed graph is connected if and only if the bipartite graph is irreducible. Other connections between reducibility and connectivity are established.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 14 , 1962 , pp. 529 - 539
Copyright
Copyright © Canadian Mathematical Society 1962

References

1. Dulmage, A. L. and Mendelsohn, N. S., Coverings of bipartite graphs, Can. J. Math., 10 (1958), 517–534.Google Scholar
2. Dulmage, A. L. and Mendelsohn, N. S., A structure theory of bipartite graphs of finite exterior dimension, Trans. Roy. Soc. Can., Third Series, Section III, 53 (1959), 1–13.Google Scholar