On structural properties of some probable $R(3, 10)$-critical graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918275253796864 |
|---|---|
| author | Pandey, Dinesh Ravi, Peruvemba Sundaram |
| author_facet | Pandey, Dinesh Ravi, Peruvemba Sundaram |
| contents | The Ramsey number $R(s, t)$ is the smallest positive integer $n$ such that every graph on $n$ vertices contains either a clique of size $s$ or an independent set of size $t$. An $R(s,t)$-critical graph is a graph on $R(s,t)-1$ vertices that contains neither a clique of size $s$ nor an independent set of size $t$. It is known that $40\leq R(3, 10)\leq 42$. We study the structure of a $R(3,10)$-critical graphs by assuming $R(3, 10)=42$. We show that if such a graph exists then its minimum degree and vertex connectivity are the same and is $6, 7$ or $8$. Then we find all the possible degree sequences of such graphs. Further, we show that if such a graph exists, then its diameter is either $2$ or $3$, and if it has diameter $2$ and minimum degree $6$, then it has only $21$ choices for its degree sequence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03572 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On structural properties of some probable $R(3, 10)$-critical graphs Pandey, Dinesh Ravi, Peruvemba Sundaram Combinatorics 05C30, 05D10 The Ramsey number $R(s, t)$ is the smallest positive integer $n$ such that every graph on $n$ vertices contains either a clique of size $s$ or an independent set of size $t$. An $R(s,t)$-critical graph is a graph on $R(s,t)-1$ vertices that contains neither a clique of size $s$ nor an independent set of size $t$. It is known that $40\leq R(3, 10)\leq 42$. We study the structure of a $R(3,10)$-critical graphs by assuming $R(3, 10)=42$. We show that if such a graph exists then its minimum degree and vertex connectivity are the same and is $6, 7$ or $8$. Then we find all the possible degree sequences of such graphs. Further, we show that if such a graph exists, then its diameter is either $2$ or $3$, and if it has diameter $2$ and minimum degree $6$, then it has only $21$ choices for its degree sequence. |
| title | On structural properties of some probable $R(3, 10)$-critical graphs |
| topic | Combinatorics 05C30, 05D10 |
| url | https://arxiv.org/abs/2601.03572 |