Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-29T03:30:07.187Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs without cycles of even length

Published online by Cambridge University Press:  17 April 2009

Thomas Lam
Thomas Lam
Affiliation:
School of Mathematics, The University of New South Wales, Sydney NSW 2052, Australia
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.

Dedicated to George Szekeres on his ninetieth birthday

In this paper we prove that a bipartite graph with parts of sizes M and N, having no cycles of even length less that or equal to 2(2k + 1), where k is a positive integer, has at most (NM)(k+1)/(2k+1) + Dk(N + M) edges, where Dk only depends on k.

In particular, we show that when k = 1, D1 = 1 is possible.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 63 , Issue 3 , June 2001 , pp. 435 - 440
Copyright
Copyright © Australian Mathematical Society 2001

References

[1]Benson, C., ‘Minimal regular graphs of girths eight and twelve’ Canad. J. Math. 26 (1966), 1091–1094.Google Scholar
[2]Bondy, J.A. and Simonovits, M., ‘Cycles of even lengths in graphs’, J. Combin. Theory Ser. B 16 (1974), 97–105.Google Scholar
[3]Erdös, P., ‘Extremal problems in graph theory’, in Theory of Graphs and its Applications, Proc. Sympos. Smolenice, 1963 (Publ. House Czechoslovak Acad. Sci., Prague, 1965), pp. 29–36.Google Scholar
[4]Katz, N. and Tao, T., ‘Bounds on arithmetic progressions and applications to the Kakeya conjecture’, Math. Res. Lett. 6 (1999), 625–630.CrossRefGoogle Scholar
[5]Wenger, R., ‘Extremal Graphs with no C 4,s, C 6,s, or C 10,s’, J. Combin. Theory Ser. B 52 (1991), 113–116.Google Scholar