Hostname: page-component-7b7567c8c-8tzhz Total loading time: 0 Render date: 2026-11-19T14:43:44.399Z Has data issue: false hasContentIssue false

The Exponents of Strongly Connected Graphs

Published online by Cambridge University Press:  20 November 2018

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.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1969