The independence number of circulant triangle-free graphs

1.   Introduction

Erdös proposed the tenth problem in the Third Conference on discrete mathematics in Clemson University as follows: Whether there exists a regular triangle-free graph $G_n$ on $n$ vertices where the largest independent sets have a size equal to the degree of $G_n$ ^[5].

Bauer determined all $n,r,l$ such that there exists a $r$-regular $k_l$-free graph on $n$ vertices ^[1]. Bauer proposed the following structures: Suppose $n$ is even. Let the vertices in the two parts be labelled as:

Now connect each vertex $i$ to $(i+k)'$ mod $n/2$ for $0\leqslant k\leqslant r-1$. In this case, $\alpha(G) = n/2$ and the independence ratio is $1/2$. If $n$ is odd, then $r$ must be even and $5r/2\leqslant n\leqslant 3r-1$. Form the graph $G$ as in Figure 1. Each of parts $A,B,C,D,E$ are independent sets. The size of them are: $|B| = |C| = r/2,|A| = 3r-n, |D| = |E| = n-2r$. Each vertex of $B$ and $C$ is adjacent to each vertex of $A$. Then connect each vertex of $B$ to every vertex of $D$ and each vertex of $C$ to every vertex of $E$. Since $|D| = |E| = n-2r\geq r/2$, join any vertex of $D$ to some vertices of $E$ to make a $r/2$-regular bipartite graph. Note that $B\cup C$ is an independent set of size $r$ and $B\cup E$ is an independent set of size $(n-3r/2)$. If $n = 5r/2$, then $\alpha(G) = r$. Otherwise, $\alpha(G)>r$ and the independence ratio of this graph is at least $r/(3r-1)$ ^[1].

Sidorenko set some $2k$-regular triangle-free graphs such that their independence number are equal to their degree. It is obvious that the maximum degree of vertices is a lower bound for the independence number in triangle-free graphs. Sidorenko graphs are circulant graphs ^[6]. Brandt investigated the class $\mathcal{S}$ of triangle-free graphs where the neighbourhood of vertices are maximal independent sets ^[2]. The Sidorenko graphs are in $\mathcal{S}$ ^[2].

Punnim showed that the values of independence number of regular graphs cover a line segment of integer numbers, i.e., for all $n,r$ there exist $a\leqslant b\in \mathbb{N}$ such that the independence number of any $r$-regular graph on $n$ vertices is in $[a,b]$ and for every integer $c\in[a,b]$, there exists a $r$-regular graph on $n$ vertices with independence number equals to $c$. This interval is called the independence interval ^[4].

In this current work, the independence interval of $2$-regular graphs are determined in the second section. The maximum independent set for circulant $3$-regular triangle-free graphs will be determined in Section 2. Moreover, a subinterval of independence interval for $3$-regular graphs is determined in this section. Finally, it will be proved that the independence ratio of $3$-regular triangle-free graphs is at least $3/8$. Note that Staton proved that the independence ratio for $3$-regular triangle-free graphs is at least $5/14$ ^[7]. Heckman and Thomas give a new proof for this theorem and they design a linear-time algorithm to find the maximum independent set for cubic graphs ^[3].

On the last section, some class of regular triangle-free graphs with independence number equals to degree for odd degree will be determined. In this case the lower and upper bounds are close to the even case which determined by Sidorenko ^[6].

2.   $2$-regular & $3$-regular circulant triangle-free graphs

Let $G$ be a graph. The number of vertices of $G$ is denoted by $n(G)$. The independence number of $G$ is the maximum size of an independent set of $G$ and it is denoted by $\alpha(G)$. The independence ratio is defined by $i(G) = \frac{\alpha(G)}{n(G)}$.

Definition 2.1. Suppose $S\subset\{1,\dots,n-1\}$ is such that

The circulant graph produced by $S$ is defined as follows. The vertex set is $\{0,1,\dots,n-1\}$ and $x,y$ are adjacent if and only if $x-y\in S$. Trivially, if $x<y$, it means $n-(x-y)\in S$. The circulant graph produced by $S$ is denoted by $G[S]$. The circulant graph $G[S]$ is triangle-free if and only if

If $r = 2$, we could determine the minimum independence number, as follows.

Theorem 2.2. Let $G$ be a $2$-regular triangle-free circulant graph. If the set

is non-empty, then $\min\alpha(G) = \frac{n-\max(x)}{2}$, else $\min\alpha(G) = \frac{n}{2}$ and the independence ratio is at least $2/5$.

Proof. Let $G = G[S]$ be a triangle-free circulant graph and $S = \{t,n-t\}$. Since $G$ is a $2$-regular graph, $G$ is a union of disjoint circles. If $gcd(n,t) = 1$, then $G[S]$ is a Hamiltonian circle and $\alpha(G[S]) = \lfloor n/2\rfloor$.

If $gcd(n,t) = d\neq 1$, then $G[S]\simeq G[d,n-d]$ and we have:

But the graph $G[S]$ is disjoint union of $d$ circles of size $n/d$ and $\alpha(G[S]) = d\lfloor n/2d\rfloor$. Since $n = dk$, we have two cases:

$(1).$ $k = 2s$ is an even integer. Then $\alpha(G[S]) = d\lfloor n/2d\rfloor = ds = n/2$.

$(2).$ $k = 2s+1$ is an odd integer. Then $\alpha(G[S]) = d\lfloor n/2d\rfloor = ds = (n-d)/2$.

Therefore, if $X = \left\{d;d\neq 1,d\vert n, d\neq n/3, n/d \ is\ odd\ \right\}$ is a non-empty set, then

Otherwise, $\min(\alpha(G[S])) = n/2$.

Since $\dfrac{n}{d}$ is an odd number and $d\neq n/3$, then $\dfrac{n}{d}\geqslant 5$ and consequently $d\leqslant\dfrac{n}{5}$. Therefore, the independence ratio is at least

Note that every $2$-regular graph $G$ is a disjoint union of circles, i.e., $G = C_1\cup\dots \cup C_k$. Thus $\alpha(G) = \sum\alpha(C_i)$. Suppose the size of $C_i$ is $n_i$. If $n_i$ is odd, $\alpha(C_i) = (n_i-1)/2$, otherwise $\alpha(C_i) = n_i/2$. Suppose $G = C_1\cup\dots\cup C_t\cup C_k$ and $C_1,\dots ,C_t$ are odd circles and $C_{t+1},\dot,C_k$ are even circles. Thus:

The independence ratio in this case is $1/2-t/2n$. Since $t\leqslant\frac{n}{3}$, then $i(G)\geqslant\frac{1}{3}$. In fact, the max/min of independence number is determined by the size of $t$ as follows.

Proposition 2.3. The independence interval for $2$-regular graphs is $\left[\lceil\frac{n}{3}\rceil,\lfloor\frac{n}{2}\rfloor\right]$. In fact, if $n>3$:

The max/min of independence number of $2$-regular triangle-free graphs is determined as follows.

Proposition 2.4. The independence interval for $2$-regular triangle-free graphs is $\left[\lceil\frac{2n}{5}\rceil,\lfloor\frac{n}{2}\rfloor\right]$. In fact, the minimum independence number for $2$-regular triangle-free graphs is as follows ($n\geqslant 5$):

If $r = 3$, $n$ must be an even number and $n/2\in S$. Note that $3$-regular circulant graph has a $2$-regular circulant as an induced subetaaph. In the rest of this section, the minimum independence number of $3$-regular triangle-free circulant graphs is determined.

Lemma 2.5. If $S = \{d,n/2,n-d\}$ and $G[S]$ is a triangle-free circulant graph and $gcd(n,d) = 1$, then

Proof. Since $G[S]$ is a triangle free circulant graph, we have:

Suppose $gcd(n,d) = 1$, then $G[S]$ has a Hamiltonian circle. If $kd\stackrel{n}{\equiv}\frac{n}{2}$ and $k\leqslant n$, then $k = \frac{n}{2}$ and therefore $G[S]\cong G[\{1,n/2,n-1\}]$. Note that $\alpha(G[S])\leqslant n/2$.

Suppose $n/2$ is an odd integer. Since the numbers $\{1,n/2,n-1\}$ are odd and any odd vertex is adjacent to 3 even vertices, then the set of all odd vertices is an independent set in $G[S]$ and $\alpha(G[S]) = n/2$.

Otherwise, suppose $n/2 = 2k$ is an even integer. Then for every odd number $2l+1<n/2$, the number $n/2-(2l+1) = 2(k-l)-1$ is an odd number less than $n/2$. Thus the set of odd integers is not an independent set in $G[S]$. Nevertheless, the set $\left\{1,\dots,2k-1,2k+2,\dots,4k-2\right\}$ is an independent set of size $2k-1$. Now suppose there exists an independent set $I$ of size $2k$. Since $\{a,n/2+a\}$ is an edge in $G[S]$ for arbitrary integer $0\leqslant a\leqslant n/2-1$, then $I$ have at most exactly one element from each of these pairs. Without less of generality, suppose $I$ has $0$. Then, $I$ must have $n/2+1$, and so on. Therefore, one could see

and it is a contradiction, because $n-1$ is adjacent to $0$.

Theorem 2.6. Suppose $n$ is an even number and $S = \{d,n/2,n-d; d\vert n\}$. If $G[S]$ is a triangle-free circulant graph, then

Proof. Note that $d\neq n/2,n/3,n/4$. Then we have two cases:

ⅰ) If $n/d$ is even, then $n = 2td$ and $G_0 = \{0,d,\dots,(2t-1)d\}$. Thus $n/2 = td$ is one of the vertices of $G_0$. Note that $G_0$ is a $n/d$-cycle with addition edges $\{kd,(k+t)d\}$ for $k = 0,1,\dots t-1$. If $n/2d$ is even, $\alpha(G_0) = \frac{n}{2d}-1 = t-1$. But $G[S]$ is $d$ copies of $G_0$. Therefore, $\alpha(G[s]) = d(t-1) = n/2-d$. Otherwise, if $n/2d$ is odd, $\alpha(G_0) = \frac{n}{2d}$ and $\alpha(G[s]) = n/2$.

ⅱ) If $n/d$ is odd, then $n = (2t+1)d$. Thus $n/2 = td+(d/2)$. Note that $d$ is an even divisor of $n$. Let $G_i = \{i,i+d,\dots,i+2td\}$, for $i = 0,\dots,d-1$. The graph $G_0$ is a $n/d$-cycle and every vertex of $G_i$ is adjacent to one and only one vertex of $G_{i+\frac{d}{2}}$ for $i = 0,\dots,d/2-1$. But $\alpha(G_i) = \lfloor\frac{n}{2d}\rfloor = t$ and therefore $\alpha(G[s]) = \frac{d}{2}(2t) = (n-d)/2$.

Theorem 2.7. Suppose $n$ is an even number and $1<d<n$. If $gcd(n,d) = t\neq 1$, then

Proof. Since $gcd(n,d) = t$, then $G[d,n-d]\cong G[t,n-t]$ and this graph is $t$ disjoint cycles of order $n/t$. We have two cases:

Case 1. $t\vert n/2$. Then $n = 2kt$ and $d = d't$. Therefore, $d'$ is an odd integer. Suppose $V(G_0) = \left\{0,d,\dots,(n/t-1)d\right\} = \left\{0,t,\dots,(n/t-1)t\right\}$. Thus $n/2\in V(G_0)$. $G_0$ is a $3$-regular triangle-free circulant graph on $n/t$ vertices and $S = \{1,n/2t,n/t-1\}$ and

Thus we have $\alpha(G[S]) = t\alpha(G_0)$ and

Case 2. $t\nmid n/2$. Thus $n/2\not\in V(G_0)$ and there exists $i<t$ such that $n/2\in V(G_i) = \{i,i+d,\dots,i+(n/t-1)d\}$. Note that $n = kt$ and $t\nmid n/2$. Therefore, $k$ is an odd number and $t$ is an even. But $0\in V(G_0)$ is adjacent to $n/2\in V(G_i)$ and for every $j = 0,1,\dots,n/t-1$, $jd$ is adjacent to $n/2+jd\in V(G_i)$. In fact, we have $t/2$ copies of graph such as the graph Figure 2 on $2n/t$ vertices.

The maximum independent set in these graphs has order $n/t-1$ as such as: $\{0,n/2+d,2d,n/2+3d,\dots,(n/t-3)d,n/2+(n/t-2)d\}$. This independent set is shown by black vertices in Figure 2. Then $\alpha(G[S])) = (n-t)/2$.

We summarize Theorems 2.6,2.7 and Lemma 2.5 as follows:

Theorem 2.8. Suppose $n$ is an even number and $1\leqslant d<n$. If $gcd(n,d) = t$ and $S = \{d,n/2,n-d\}$, then

By Theorem 2.7, one could determine the independence number for every $3$-regular circulant triangle-free graphs. The minimum independence number for these graphs are determined for $n\leqslant 44$ as follows:

Corollary 2.9. Suppose $n = 2p = 2(2k+1)$ and $p\geqslant 5$ is a prime number and $G[S]$ is a $3$-regular triangle-free circulant graph. Then $\min\alpha(G[S]) = p-1$ and

Corollary 2.10. The independence ratio of circulant $3$-regular triangle-free graphs is at least $\frac{3}{8}$ and this lower bound is sharp, i.e. there exists a $3$-regular triangle-free circulant graph on $8k$ vertices such that its independence number equals to $3k$, for all $k$.

Proof. Note that the minimum independence number is $\frac{n}{2}-d$ and $d$ must divide $n$ and $\frac{n}{2d}$ is even. Since $d\neq n/2,n/3,n/4$, then $d\leqslant\frac{n}{8}$. Thus $\alpha(G)\geqslant\frac{n}{2}-\frac{n}{8} = \frac{3n}{8}$ and therefore the independence ratio is at least $\frac{3}{8}$.

Suppose $d\vert 8k$ and $n/d$ is an even integer. Then the maximum value of $d$ is $k$. Therefore $S = \{k,4k,7k\}$ and $\alpha(G[S]) = 4k-k = 3k$ and consequently the independence ratio is $3/8$.

3.   $r$-regular circulant triangle-free graphs

In this section, the circulant triangle-free graphs with independence number equal to their degree are investigated. These graphs are denoted by $\mathcal{A}$-graph in this work. The first integer $n$ such that there exists a $r$-regular $\mathcal{A}$-graph with $n$ vertices is obviouse:

Proposition 3.1. The least number $n$ such that there exists a $r$-regular $\mathcal{A}$-graph on $n$ vertices is $2r$.

Proof. Suppose $G$ is a triangle-free $r$-regular graph on $n$ vertices, then $n$ is at least $2r$.

Suppose $n = 2r, V = \{0,1,\dots,2r-1\}$ and $S = \{2t-1;0\leqslant t\leqslant r\}$. Then $G[S] = K_{r,r}$ is a triangle-free circulant graph. The set of odd integers is an independent set of size $r$. If $I$ is a set of size $r+1$, then there exist two integers in $I$ with different parity like $a = 2k,b = 2l+1$. Since $a-b\in S$, then $a,b$ are adjacent vertices in $G[S]$ and it is a contradiction.

The above lower bound is trivial. But there does not exist $r$-regular $\mathcal{A}$-graphs for all $n\geqslant 2r$, as follows.

Proposition 3.2. There does not exist any $2r$-regular circulant triangle-free graph on $4r+1$ vertices.

Proof. Suppose $S = \{x_1<\dots<x_r\leqslant 2r<x_{r+1}<\dots<x_{2r}\}$. Since the graph $G[S]$ is triangle-free, then the set $\{x_r-x_{r-1},x_r-x_{r-2},\dots,x_r-x_1\}$ is disjoint from $\{x_1,\dots,x_r\}$. But $\{x_r-x_{r-1},x_r-x_{r-2},\dots,x_r-x_1\}\cup \{x_1,\dots,x_r\}\subset\{1,\dots,2r\}$. Therefore, we have two cases:

$(1).$ $x_r = 2r$. Then $4r+1-x_r = 2r+1\in S$. Therefore, $1 = 2r+1-2r\not\in S$. Thus

and

Moreover, the set $\{2r-x_{r-1},2r-x_{r-2},\dots,2r-x_1\}\not\in S$, too. Thus

Thus for every $i = 1,2,\dots,r-1$, there exists $j = 1,\dots,r$ such that $2r-x_i = 2r+1-x_j$. Therefore, $x_j = x_i+1$. Thus $2r-x_i = 2r+1-x_{i+1}$, for all $i$ and $S = \{r+1,\dots ,2r-1,2r,2r+1,\dots ,3r\}$. But $3r-(r+1) = 2r-1\in S$ and it is a contradiction.

$(2).$ $x_r = 2r-1$. Thus $4r+1-x_r = 2r+2\in S$ and $2r+2-(2r-1) = 3\not\in S$. Therefore $x_1<x_2<\dots <x_r = 2r-1\in S$ and $2r+2-(2r-1) = 3<2r+2-x_{r-1}<\dots<2r+2-x_1\leqslant 2r+1\not\in S$. If $x_1 = 1$, then $2\not\in S$ and $\{2\}\not\in\{1 = x_1,x_2,\dots,x_r = 2r-1\}\dot{\cup}\{3,2r+2-x_{r-1},\dots,2r\}$. Therefore, there exists $x_i\in S$ such that $2r = 2r+2-x_i$. Thus $x_i = 2$ and it is a contradiction. If $x_1 = 2$, then $\{2 = x_1<x_2<\dots<x_r = 2r\}\dot{\cup}\{3<2r+2-x_{r-1}<\dots<2r\}$ is a set of size $2r$ and this set is a subset of $\{1,2,\dots,2r\}$. It is a contradiction. Thus $x_1\neq 1,2,3$. Then $x_1\geqslant 4$ and $2r+2-x_1\leqslant 2r-2$. Therefore the set

is a set of size $2r$ and it is a subset of $\{3,4,\dots,2r-1\}$. It is a contradiction too.

There exists similar result for circulant graphs with odd regularity:

Proposition 3.3. Let $r>1$. There does not exist any $(2r+1)$-regular circulant triangle-free graph on $4r+4$ vertices.

Proof. Suppose $S = \{x_1<x_2<\dots<x_r<x_{r+1} = 2r+2<x_{r+2}<\dots<x_{2r+1}\}$ and $G[S]$ is a $(2r+1)$-regular circulant triangle-free graph. Therefore $2r+2-x_1,2r+2-x_2,\dots,2r+2-x_r\not\in S$.

Note that $r+1\not \in S$ and it is not adjacent to $2r+2$, too. Moreover, $x_r>r+1$. Otherwise, $S = \{1,2,\dots,r\}$ and $G[S]$ is not a triangle-free graph. If $x_r<2r$, then the set $\{x_r+1,\dots,2r+1\}$ is disjoint from $S$. Thus these elements are in the form $2r+2-x_1,2r+2-x_2,\dots$. Thus $x_1 = 1,x_2$ and $G[S]$ is not triangle-free graph.

Now suppose $x_r = 2r$. Then $2r+1\not\in S$ and $2r+1 = 2r+2-x_1$. Thus $x_1 = 1$. Since $G[S]$ is triangle-free graph, $2 = (2r+2)-2r\not\in S$. Moreover, $(4r+4)-2r = 2r+4\in S$. Similary, since $G[S]$ is triangle-free graph, $4 = (2r+4)-2r\not\in S$.

If $4 = r+1$, then $r = 3$ and $2,4,5\not\in S$ and $1,3,6\in S$ and $G[S]$ is not triangle-free graph. If $4\neq r+1$, then $4 = (2r+2)-x_{r-1}$ and $x_{r-1} = 2r-2$ and $x_{r+3} = (4r+4)-(2r-2) = 2r+6$. Since $G[S]$ is triangle-free graph, then $6,8\not\in S$. One could continue this process. If $r = 2t-1$ is an odd element, then $2r,2r-2,2r-4,\dots,r+3\in S$. But $2r+6,r+3\in S$, then $G[S]$ is not a triangle-free graph.

If $r$ is an even element, then $2,4,6,\dots\not\in S$, but $2r\in S$ and it is a contradiction.

Now the main family of $\mathcal{A}$-graphs are presented as follows.

Definition 3.4. Suppose $S = \{\pm k,\pm(k+1),\dots,\pm(2k-1)\}$. The graph $G[S]$ is denoted by $G_{n,k}$.

The graphs $G_{n,k}$ are triangle-free graph if and only if $n\geqslant 6k-2$.

Theorem 3.5. (Sidorenko's Theorem)- If $6k-2\leqslant n\leqslant 8k-3$, then $G_{n,k}$ is a $2k$-regular $\mathcal{A}$-graph, ^[6].

Note that if one add $n/2$ to $S$, then $G[S]$ has triangle, because $n/2\in S-S = [n-4k+2,n-2k]$. Thus for odd degree, we must define new structures:

Theorem 3.6. Suppose $n = 8k$, let $S = \{\pm 1,\pm 3,\cdots\pm (2k-1)\}\cup\{4k\}$. Then $G[S]$ is a $(2k+1)$-regular $\mathcal{A}$-graph on $8k$ vertices.

Proof. Since $4k-(2k-1) = 2k+1$, then $(8k-(2k-1))-4k = 2k+1$ and it is obviously triangle-free graph. Let $V = \{0,1,\dots,8k-1\}$.

Suppose $0<t_1<\dots<t_{2k+2}<8k$ is an independent set of size $2k+2$. If all $t_i$'s are odd integers. Suppose $t_i<4k<t_{i+1}$. Note that $t_j-t_i$ are even, for all $j>i$. Thus $t_j$ is adjacent to $t_i$ if and only if $t_j-t_i = 4k$. Since there are $2k$ odd elements less than $4k$, one must choose at most one element from each $\{t_i,t_i+4k\}$, for all $t_i<4k$. It is a contradiction.

If all $t_i$'s are even, there are at most $2k-1$ even numbers less than $4k$. if $t_j>t_i$, $t_j$ is adjacent to $t_i$ if and only if $t_j-t_i = 4k$. One must choose at most one element from each $\{t_i,t_i+4k\}$, for all $t_i<4k$. But there are $2k-1$ set of $\{t_i,t_i+4k\}$ and it is a contradiction.

Now suppose some $t_i$'s are odd and some of them are even. Let $s_i = t_{i+1}-t_i$, $i = 1,\dots,2k+1$, $s_{2k+2} = 8k-t_{2k+2}+t_1$. Then $s_1+\dots+s_{2k+2} = 8k$. There are some odd $s_i$ and some even $s_i$. Since the sum of $s_i$'s are even, the number of odd $s_i$'s are even.

Let the number of odd $s_i$'s is $r$. If $s_i$ is an odd element, then $2k+1\leqslant s_i<6k+1$. But $s_1+\dots+s_{2k+2} = 8k$, then $r<4$. Thus we have two cases. If $r = 0$ is solved before.Now suppose $r = 2$. Then $s_i\geqslant 2, s_1+\dots+s_{2k+2}\geqslant (2k)\times 2+2\times (2k+1) = 4k+4k+2 = 8k+2$ and it is a contradiction.

The above theorem is an upper bound for odd regularity. A non-trivial lower bound for these numbers is as follows:

Theorem 3.7. Suppose $n = 6k+2$ and $S = \{ 3t+1; 0\leqslant t\leqslant 2k\}$. Then $G[S]$ is a $(2k+1)$-regular $\mathcal{A}$-graph on $6k+2$ vertices.

Proof. It is obviouse that $G[S]$ is a triangle-free circulant graph on $6k+2$ vertices.

Now suppose we have an independent set $I$ of size $2k+2$. Let $0\in I$. Thus the other elements of $I$ are elements of $S_0 = \{3t; 1\leqslant t\leqslant 2k\}$ and $S_2 = \{3t+2; 0\leqslant t\leqslant 2k-1\}$. But $|S_0| = |S_2| = 2k$. Then $I\cap S_0, I\cap S_2\neq \emptyset$. Suppose $a = 3t\in S_0, b = 3s+2\in S_2$.

We have two cases: If $a>b$, then $a-b = 3t-3s-2\in S$. Otherwise, every element of $I\cap S_0$ is less than every element of $I\cap S_2$. Suppose $3s$ is the greatest element of $I\cap S_0$, then $|I\cap S_0|\leqslant s$ and for all element $3t+2\in I\cap S_2$, $3t+2>3s$. Therefore $t\geqslant s$ and $I\cap S_2\subseteq\{3t+2; s\leqslant 2k-1\}$. Thus $|I\cap S_2|\leqslant 2k-s$ and $|(I\cap S_0)\cup(I\cap S_2)|\leqslant 2k$. It is a contradiction.

According to the above theorems, we have the following conjecture:

Conjecture 3.8. Suppose $6k+2\leqslant n\leqslant 8k$ and $n$ is an even number. There exists a $(2k+1)$-regular $\mathcal{A}$-graph on $n$ vertices.

4.   Conclusion

Some of the well-known examples for $(s,t,n)$-graphs are circulant graphs. Thus $t$-regular triangle-free circulant graphs must be some good lower bounds for $R(3,t+1)$ if their independence number is $t$. Thus it is better to find some $\mathcal{A}$-graphs with the maximum number of vertices. The algebraic properties of these graphs will be helpful to find their minimum independence number.

Conflict of interest

The authors declare no conflict of interest.