On Strongly Regular Graphs and the Friendship Theorem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916644106797056 |
|---|---|
| author | Sason, Igal |
| author_facet | Sason, Igal |
| contents | This paper presents an alternative proof of the celebrated friendship theorem, originally established by Erdős, Rényi, and Sós (1966). The proof relies on a closed-form expression for the Lovász $\vartheta$-function of strongly regular graphs, recently derived by the author. Additionally, the paper considers some known extensions of the theorem, offering discussions that provide insights into the friendship theorem, one of its extensions, and the proposed proof. Leveraging the closed-form expression for the Lovász $\vartheta$-function of strongly regular graphs, the paper further establishes new necessary conditions for a strongly regular graph to be a spanning or induced subgraph of another strongly regular graph. In the case of induced subgraphs, the analysis also incorporates a property of graph energies. Some of these results are extended to regular graphs and their subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13596 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Strongly Regular Graphs and the Friendship Theorem Sason, Igal Combinatorics 05C50, 05C60, 05E30 This paper presents an alternative proof of the celebrated friendship theorem, originally established by Erdős, Rényi, and Sós (1966). The proof relies on a closed-form expression for the Lovász $\vartheta$-function of strongly regular graphs, recently derived by the author. Additionally, the paper considers some known extensions of the theorem, offering discussions that provide insights into the friendship theorem, one of its extensions, and the proposed proof. Leveraging the closed-form expression for the Lovász $\vartheta$-function of strongly regular graphs, the paper further establishes new necessary conditions for a strongly regular graph to be a spanning or induced subgraph of another strongly regular graph. In the case of induced subgraphs, the analysis also incorporates a property of graph energies. Some of these results are extended to regular graphs and their subgraphs. |
| title | On Strongly Regular Graphs and the Friendship Theorem |
| topic | Combinatorics 05C50, 05C60, 05E30 |
| url | https://arxiv.org/abs/2502.13596 |