Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An invariant for minimum triangle-free graphs
Stockholm University, Faculty of Science, Department of Mathematics.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We study the number of edges, e(G), in triangle-free graphs with a prescribed number of vertices, n(G), independence number, α(G), and number of cycles of length four, N(C₄;G). We in particular show that 3e(G) - 17n(G) + 35α(G) + N(C₄;G) ≥ 0 for all triangle-free graphs G. We also characterise the graphs that satisfy this inequality with equality.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-151216OAI: oai:DiVA.org:su-151216DiVA, id: diva2:1172267
Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-01-09
In thesis
1. On minimal triangle-free Ramsey graphs
Open this publication in new window or tab >>On minimal triangle-free Ramsey graphs
2017 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

A graph G is called a minimal Ramsey (3, k; n)-graph if it has the least amount of edges, e(3, k; n), possible given that G is triangle-free, has independence number α(G) < k an has n vertices. The numbers e(3, k; n) and the minimalRamsey graphs are directly related to the Ramsey numbers R(3, k).This licentiate thesis studies minimal Ramsey graphs, graphs that are closeto being minimal Ramsey graphs and the edge numbers e(3, k; n) from several different aspects. Lower bounds on e(3, k; n) are lower bounds on the numberof edges in triangle-free graphs. In Paper I we show the bound

e(G) ≥ (1/3)(17n(G) − 35α(G) − N(C 4 ; G)),

where N(C4 ; G) that is number of cycles of length four in G. We also classifyall triangle-free graphs which satisfy this bound with equality.

In Paper II we study constructions of minimal Ramsey graphs, and graphsG such that e(G) − e(3, k; n) is small. We use a way to describe some of these graphs in terms of “patterns” and a recursive procedure to construct them. We also present the result of computer calculations where we have actually performed such constructions of Ramsey graphs and compare these lists to other computations of Ramsey graphs.

Place, publisher, year, edition, pages
Department of Mathematics, 2017. p. 108
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:su:diva-151219 (URN)
Presentation
2018-01-16, Room 306, House 6, Kräftriket 6, 104 05, Stockholm, 15:15 (English)
Opponent
Supervisors
Available from: 2018-01-11 Created: 2018-01-09 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

By organisation
Department of Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf