Hostname: page-component-7bb8b95d7b-495rp Total loading time: 0 Render date: 2024-09-12T08:54:32.455Z Has data issue: false hasContentIssue false
  • English
  • Français

The Exponents of Strongly Connected Graphs

Published online by Cambridge University Press:  20 November 2018

Edward A. Bender  and
Thomas W. Tucker
Edward A. Bender
Affiliation:
Institute for Defense Analyses, Princeton, New Jersey
Thomas W. Tucker
Affiliation:
Dartmouth College, Hanover, New Hampshire
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 directed graphG is a set of vertices V and a subset of V × V called the edges of G. A path in G of length k,

is such that (vi, vi+1) is an edge of G for 1 ≦ i ≦ k. A directed graph G is strongly connected if there is a path from every vertex of G to every other vertex. A circuit is a path whose two end vertices are equal. An elementary circuit has no other equal vertices. See (1) for a fuller discussion.

Let G be a finite, strongly connected, directed graph (fscdg). The kth power Gk of G is the directed graph with the same vertices as G and edges of the form (i, j) where G has a path of length k from i to j.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 21 , 1969 , pp. 769 - 782
Copyright
Copyright © Canadian Mathematical Society 1969

References

1. Berge, C., The theory of graphs and its applications (Wiley, New York, 1962).Google Scholar
2. Brauer, A. and Schockley, J. E., On a problem of Frobenius, J. Reine Angew. Math. 211 (1962), 215–220.Google Scholar
3. Dulmage, A. L. and Mendelsohn, N. S., Gaps in the exponent set of primitive matrices, Illinois J. Math. 8 (1964), 642–656.Google Scholar
4. Heap, B. R. and Lynn, M. S., The structure of powers of non-negative matrices. I. The index of convergence (National Physical Laboratory, Teddington, Middlesex, England, 1964), SIAM J. Appl. Math. 14 (1966), 610–639.Google Scholar
5. Norman, R. Z., private communication.Google Scholar
6. Ptâk, V. and Sedlâcek, J., On the index of imprimitivity of non-negative matrices, Czechoslovak Math. J. 8 (83) (1958), 496–501.Google Scholar
7. Roberts, J. B., Note on linear forms, Proc. Amer. Math. Soc. 7 (1956), 465–469.Google Scholar
8. Tucker, T. W., The exponent set of strongly connected graphs, Senior thesis, Harvard University, 1967.Google Scholar
9. Wielandt, H., Unzerlegbare, nicht negativen Matrizen, Math. Z. 52 (1950), 642–648.Google Scholar