Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-02T22:35:12.318Z Has data issue: false hasContentIssue false
  • English
  • Français

On certain cycles in graphs

Published online by Cambridge University Press:  20 January 2009

Douglas D. Grant
Douglas D. Grant
Affiliation:
Napier CollegeEdinburgh
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.

We show that every simple graph of order 2r and minimum degree ≧4r/3 has the property that for any partition of its vertex set into 2-subsets, there is a cycle which contains exactly one vertex from each 2-subset. We show that the bound 4r/3 cannot be lowered to r, but conjecture that it can be lowered to r + 1.

Type
Research Article
Information
Proceedings of the Edinburgh Mathematical Society , Volume 24 , Issue 1 , February 1981 , pp. 15 - 17
Copyright
Copyright © Edinburgh Mathematical Society 1981

References

REFERENCES

(1)Bollobás, B., Erdös, P. and Szémeredi, E., On Complete Subgraphs of r-chromatic Graphs, Discrete Math. 13 (1975), 97–107.CrossRefGoogle Scholar
(2)Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications, (Macmillan, London and Basingstoke, 1976).CrossRefGoogle Scholar
(3)Chvátal, V., On Hamilton's Ideals, J. Combinatorial Theory 12B (1972), 163–168.CrossRefGoogle Scholar
(4)Dirac, G. A., Some Theorems on Abstract Graphs, Proc. London Math. Soc. 2 (1952), 69–81.CrossRefGoogle Scholar
(5)Zelinka, B., Isomorphisms of Polar and Polarised Graphs, Czech. Math. J. 26 (1976), 339–351.CrossRefGoogle Scholar
(6)Zelinka, B., Analoga of Monger's Theorem for Polar and Polarised Graphs, Czech. Math. J. 26 (1976), 352–360.CrossRefGoogle Scholar
(7)Zelinka, B., Eulerian Polar Graphs, Czech. Math. J. 26 (1976), 361–364.CrossRefGoogle Scholar
(8)Zelinka, B., Self-derived Polar Graphs, Czech. Math. J. 26 (1976), 365–370.CrossRefGoogle Scholar