Subgraph counting identities and Ramsey numbers (Q1354725)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subgraph counting identities and Ramsey numbers |
scientific article |
Statements
Subgraph counting identities and Ramsey numbers (English)
0 references
20 August 1997
0 references
For each vertex \(v\) of a graph \(G\), the number of subgraphs of each isomorphism class which lie in the neighbourhood or complementary neighbourhood of \(v\) is considered. These numbers, summed over \(v\), are shown to satisfy a series of identities. Using these, it is shown that \(R(5,5)\leq 49\) and \(R(4,6)\leq 41\), where \(R(m,n)\) is the usual Ramsey number. The authors also give some experimental evidence to support their conjecture that \(R(5,5)= 43\).
0 references
Ramsey number
0 references