Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-17T22:18:47.950Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremal graphs of diameter 3

Published online by Cambridge University Press:  09 April 2009

L. Caccetta
L. Caccetta
Affiliation:
Department of Mathematics University of WaterlooOntario, N2L 3G1, Canada
Rights & Permissions [Opens in a new window]

Abstract

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.

This paper is concerned with graphs of order n and diameter at most 3 having the property that by deleting any s or fewer vertices (edges) the resulting subgraphs (partial graphs) have duameter at most. λ. A graph satisfying the above constraints and having minimum number of edges is said to be extramal. A characterization of extremal graphs is presented for the case s = 1.

Subject classification (Amer. Math. Soc. (MOS) 1970): 05 C 35.

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 28 , Issue 1 , August 1979 , pp. 67 - 81
Copyright
Copyright © Australian Mathematical Society 1979

References

Bollobás, B. (1968a), ‘A problem in the theory of communication networks’, Acta Math. Acad. Sci. Hungar. 19, 75–80.CrossRefGoogle Scholar
Bollobás, B. (1968b), ‘Graphs of given diameter’, in: Proceedings of Colloquium held at Tihany 1968 (ed. Erdos, P. and Katona, G.), pp. 29–36.Google Scholar
Bollooás, B. (1976), ‘Graphs with given diameter and minimal degree’, Ars Combinatoria 2, 3–9.Google Scholar
Bollobás, B. and Harary, F. (1976), ‘Extremal graphs with given diameter and connectivity’, Ars Combinatoria 1, 281–296.Google Scholar
Bondy, J. A. and Murty, U. S. R. (1976), Graph theory with applications (Macmillan, London).CrossRefGoogle Scholar
Caccetta, L. (1976a), ‘A problem in extremal graph theory’, Ars Combinatoria 2, 33–56.Google Scholar
Caccetta, L. (1976b), ‘Characterization of extremal graphs with given diameter and connectivity –part I’ (University of Waterloo Research Report CORR 76–42).Google Scholar
Caccetta, L. (1977), ‘On extremal graphs’, in: Proceedings of Eighth South-eastern Conference on Combinatorics, Graph Theory and Computing (Congressus Numerantium XIX) (ed. Hoffman, F. et al. ) (Utilitas Mathematica, Winnipeg), pp. 125–137.Google Scholar
Caccetta, L. (1978), Graph theory and graphical enumeration with applications to the physical sciences and social sciences (ed. Harary, F.) (New York Academy of Sciences), pp. 76–94.Google Scholar