Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T07:04:55.699Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs with 6-Ways

Published online by Cambridge University Press:  20 November 2018

John L. Leonard
John L. Leonard*
Affiliation:
University of Arizona, Tucson, Arizona
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.

In a finite graph with no loops nor multiple edges, two points a and b are said to be connected by an r-way, or more explicitly, by a line r-way a — b if there are r paths, no two of which have lines in common (although they may share common points), which join a to b. In this note we demonstrate that any graph with n points and 3n — 2 or more lines must contain a pair of points joined by a 6-way, and that 3n — 2 is the minimum number of lines which guarantees the presence of a 6-way in a graph of n points.

In the language of [3], this minimum number of lines needed to guarantee a 6-way is denoted U(n). For the background of this problem, the reader is referred to [3].

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 25 , Issue 4 , August 1973 , pp. 687 - 692
Copyright
Copyright © Canadian Mathematical Society 1973

References

1. Dirac, G. A., Extensions of the theorems of Turán and Zarankiewicz, Theory of graphs and its applications, Proceedings of the symposium held in Smolenice, Czechoslovakia, June, 1963 (Fiedler, M., ed., Academic Press, New York, 1964), 127–132.Google Scholar
2. Harary, F., Graph theory (Addison-Wesley, Reading, Mass., 1969).Google Scholar
3. Leonard, John L., On graphs with at most four line-disjoint paths connecting any two vertices, J. Combinational Theory Ser. B. 13 (1972), 242–250.Google Scholar