Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-07T10:06:17.398Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangles in Regular Graphs with Density Below One Half

Published online by Cambridge University Press:  01 May 2009

ALLAN SIU LUN LO
ALLAN SIU LUN LO*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK (e-mail: allan.lo@cantab.net)
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.

Let k3reg(n, d) be the minimum number of triangles in d-regular graphs with n vertices. We find the exact value of k3reg(n, d) for d between $2n /5 + 12 \sqrt{n}/5$ and n/2. In addition, we identify the structure of the extremal graphs.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 3 , May 2009 , pp. 435 - 440
Copyright
Copyright © Cambridge University Press 2009

References

[1]Ahlswede, R. and Katona, G. O. H. (1978) Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar. 32 97–120.Google Scholar
[2]Andrásfai, B., Erdős, P. and Sós, V. T. (1974) On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8 205–218.Google Scholar
[3]Das, K. (2004) Maximizing the sum of the squares of the degrees of a graph. Discrete Math. 285 57–66.CrossRefGoogle Scholar
[4]de Caen, D. (1998) An upper bound on the sum of squares of degrees in a graph. Discrete Math. 185 245–248.CrossRefGoogle Scholar
[5]Lo, A. Cliques in graphs with bounded minimum degree. In preparation.Google Scholar
[6]Nikiforov, V. (2007) The sum of the squares of degrees: Sharp asymptotics. Discrete Math. 307 3187–3193.CrossRefGoogle Scholar
[7]Olpp, D. (1996) A conjecture of Goodman and the multiplicities of graphs. Austral. J. Combin. 14 267–282.Google Scholar
[8]Székely, L. A., Clark, L. H. and Entriger, R. C. (1992) An inequality for degree sequences. Discrete Math. 103 293–300.CrossRefGoogle Scholar