Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-19T10:07:20.294Z Has data issue: false hasContentIssue false
  • English
  • Français

Three Remarkable Graphs

Published online by Cambridge University Press:  20 November 2018

Norman Biggs
Norman Biggs*
Affiliation:
University of London, Royal Holloway College, Surrey, England
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 the development of any mathematical theory it is often advisable to test the known theoretical results in particular cases, for in this way we are able to judge the state of the subject, its strengths and its weaknesses. It is the purpose of this paper to put forward three remarkable graphs which can be used to indicate the progress being made in research in graph theory. We shall undertake three tasks - the construction of the graphs themselves, the investigation of their properties (insofar as the theory allows), and the indication of possible lines for further enquiry.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 25 , Issue 2 , April 1973 , pp. 397 - 411
Copyright
Copyright © Canadian Mathematical Society 1973

References

1. Benson, C. T. and Losey, N. E., On a graph of Hoffman and Singleton, J. Combinatorial Theory 11 (1971), 67–79.Google Scholar
2. Biggs, N. L., Intersection matrices for linear graphs (In: Combinatorial Mathematics and its Applications, Academic Press, 1971).Google Scholar
3. Biggs, N. L., Finite groups of automorphisms, London Math. Soc. Lecture Notes Series 6 (Cambridge Univ. Press, Cambridge, 1971).Google Scholar
4. Biggs, N. L., Spanning trees of dual graphs, J. Combinatorial Theory 11 (1971), 127–131.Google Scholar
5. Biggs, N. L. and Smith, D. H., On trivalent graphs, Bull. Lond. Math. Soc. 3 (1971), 155–158.Google Scholar
6. Brooks, R. L., On colouring the nodes of a network. Proc. Cambridge Philos. Soc. 37 (1941), 194–197.Google Scholar
7. Conway, J. H., Three lectures on exceptional groups (In: Finite simple groups, Academic Press, 1971).Google Scholar
8. Damerell, R. M., On Moore graphs (to appear in Proc. Cambridge Philos. Soc).Google Scholar
9. Frucht, R., Die Gruppe der Petersen'schen Graphen und der Kantensystem der regularen Polyheder, Comment. Math. Helv. 9 (1937), 217–223.Google Scholar
10. Harary, F., Graph theory (Addison-Wesley, Reading, 1969).Google Scholar
11. Hoffman, A. J. and Singleton, R. R., On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960), 497–504.Google Scholar
12. Petersen, J., Die Theorie der regulären Graphen, Acta Math. 15 (1891), 193–220.Google Scholar
13. Read, R. C., An introduction to chromatic polynomials, J. Combinatorial Theory, 4 (1968), 52–71.Google Scholar
14. Sands, D. A., Dichromatic polynomials of linear graphs, Ph.D. Thesis, University of London, 1972.Google Scholar
15. Smith, D. H., On primitive and imprimitive graphs, Quart. J. Math. Oxford Ser. 22 (1971), 551–557.Google Scholar
16. Tutte, W. T., A non-Hamiltonian graph, Can. Math. Bull. 3 (1960), 1–5.Google Scholar
17. Tutte, W. T., Connectivity in graphs (University of Toronto Press, Toronto, 1966).Google Scholar
18. Tutte, W. T., A contribution to the theory of chromatic polynomials, Can. J. Math. 6 (1954), 80–91.Google Scholar
19. Tutte, W. T., Qn dichromatic polynomials, J. Combinatorial Theory 2 (1967), 301–320.Google Scholar
20. Vizing, V. G., On an estimate of the chromatic class of a p-graph (Russian), Diskret. Analiz. 3 (1964), 25–30.Google Scholar
21. Wong, W. J., Determination of a class of primitive permutation groups, Math. Z. 99 (1967), 235–246.Google Scholar