Graphs with 6-Ways
Canadian journal of mathematics, Tome 25 (1973) no. 4, pp. 687-692
Voir la notice de l'article provenant de la source Cambridge University Press
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].
Leonard, John L. Graphs with 6-Ways. Canadian journal of mathematics, Tome 25 (1973) no. 4, pp. 687-692. doi: 10.4153/CJM-1973-069-x
@article{10_4153_CJM_1973_069_x,
author = {Leonard, John L.},
title = {Graphs with {6-Ways}},
journal = {Canadian journal of mathematics},
pages = {687--692},
year = {1973},
volume = {25},
number = {4},
doi = {10.4153/CJM-1973-069-x},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1973-069-x/}
}
[1] 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] 2. Harary, F., Graph theory (Addison-Wesley, Reading, Mass., 1969). Google Scholar
[3] 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
Cité par Sources :