On the clique behavior and Hellyness of the complements of regular graphs

We have that $T$ is a triangle in $\overline{G}$ and so $\hat{T}$, its extended triangle in $\overline{G}$, is a cone, by Theorem 2.1. Since $\overline{G}$ is $(n-k-1)$-regular, considering the apex of the cone we obtain that $|\hat{T}|\leq n-k$. This means that there must be at least $k$ vertices that are neighbors to one or none of the vertices of $T$ in $\overline{G}$. Such vertices are adjacent to $T$. ∎

Let $x\in G$, as in our hypothesis. We prove first that if there is an edge $e=\{a,b\}$ in $N=N_{G}(x)$, we can perform a 2-switch on $G$, obtaining a graph $G^{\prime}$, where $a$ and $b$ are no longer adjacent, no new edges appear between vertices of $N$, and $x$ is adjacent to at least the same amount of cotriangles in $G^{\prime}$ as it was in $G$.

The edges in $G$ that cannot be switched with $\{a,b\}$ are of the form $\{r,s\}$, and where both $r,s$ are neighbors of either $a$ or $b$; or one of $\{r,s\}$ is a neighbor of both $a,b$.

Consider then the edge $e=\{a,b\}$ in $N_{G}(x)$. Let $C$ be the set of common neighbors of the vertices $a,b$ different from $x$. Suppose that $|C|=t$. Let $Z$ be the set of vertices that are at distance at least 2 from $x$, and let $Z_{1}\subseteq Z$ be the vertices in $Z$ that are not neighbors of either $a,b$. Then in $Z_{1}$ there are at least $4k-[t+2(k-t-2)+k+1]=k+t+3$ vertices. We claim that there is an edge from a vertex in $Z_{1}$ to a vertex that is not in $C\cup N\cup\{x\}$. If not, then all edges incident with $Z_{1}$ have one end in $Z_{1}$ and the other in $C\cup N$. In this case, there are at least $(k+t+3)k$ edges incident with $Z_{1}$ and at most $t(k-2)+(k-2)(k-1)$ possible edges from $C\cup N$ to $Z_{1}$. If the former number was actually less than the latter, we would have that $6k+2t\leq 2$, which is impossible. Therefore, there is an edge joining a vertex $r\in Z_{1}$ to a vertex $s\not\in N$ that is not a neighbor of at least one among $a,b$. Without loss, assume that $s$ is not a neighbor of $b$.

We perform a 2-switch to $G$ removing the edges $\{a,b\}$, $\{r,s\}$ and adding the edges $\{a,r\},\{b,s\}$, obtaining the graph $G^{\prime}$. Since neither of $r,s$ is in $N$, the graph $G^{\prime}$ has one less edge in $N$ than $G$. We claim that $x$ is adjacent to no less cotriangles in $G^{\prime}$ than it was in $G$. Suppose that $T=\{u,v,w\}$ was a cotriangle in $G$ but is not a cotriangle in $G^{\prime}$. The only way that can happen is if exactly one of the new edges involves two vertices from $T$. Suppose $u=a,v=r$. Then $w$ could have been any of the other elements in $N$ different from $a$ and $b$ and not a neighbor of $r$. That is, in the process of going from $G$ to $G^{\prime}$, the vertex $x$ loses at most $k-2$ adjacent cotriangles. On the other hand, any set of the form $\{a,b,z\}$ with $z\in Z_{1}-\{r,s\}$ was not a cotriangle in $G$ but is a cotriangle in $G^{\prime}$. This means that the vertex $x$ gains at least $k+t+1$ new adjacent cotriangles in the process of going from $G$ to $G^{\prime}$.

Because of the argument of the previous paragraph, we may now assume that the $k$-regular graph $G$ is such that there are no edges among the vertices in $N=N_{G}(x)$. Then $x$ is adjacent to exactly $\binom{k}{3}$ cotriangles where the three vertices of the cotriangle are contained in $N$. We will estimate the amount of cotriangles adjacent to $x$ where exactly two vertices of the cotriangle are elements of $N$. For each pair $ab$ of vertices of $N$, denote by $n_{ab}$ the number of common neighbors of $a,b$ different from $x$. Then there are $2k-2-n_{ab}$ vertices different from $x$ that are neighbors of either $a$ or $b$. Hence there are $n-(2k-2-n_{ab})-k-1=n-3k+1+n_{ab}$ vertices that can be used to extend the set $\{a,b\}$ to a cotriangle adjacent to $x$ of the required form. Summing over all pairs of vertices of $N$ we get $S=\binom{k}{2}(n-3k+1)+\sum n_{ab}$. We have that $\binom{k}{2}(n-2k)-S=\binom{k}{2}(k-1)-\sum n_{ab}$. Since $0\leq n_{ab}\leq k-1$ for each pair $a,b$, this expression is non-negative, proving our first claim. It is equal to zero if and only if $n_{ab}=k-1$ for each pair $a,b$ of vertices of $N$. If this were the case, then the open neighborhood of each of the vertices in $N$ consists of the same vertices, therefore the connected component that contains $x$ is isomorphic to $K_{k,k}$. ∎

Let $k>1$ and $n$ as in the hypothesis of the Theorem. Then $n>4k$. Let $G$ be a $k$-regular graph with $n$ vertices such that $\overline{G}$ is Helly. Let $B$ be the bipartite graph where one part is the set of vertices of $G$ and the other part is the set of cotriangles of $G$. In $B$, a vertex corresponding to a vertex in $G$ is a neighbor to the vertex corresponding to a cotriangle whenever the vertex is adjacent to the cotriangle. Denote with $e(B)$ the amount of edges of $B$. We will estimate $e(B)$ from below and from above.

In the graph $G$, each vertex is in at most $\binom{k}{2}$ triangles. Therefore, there are at most $\frac{n\binom{k}{2}}{3}=\frac{1}{6}nk(k-1)$ triangles. Since we have that $t(G)+t(\overline{G})=\binom{n}{3}-\frac{1}{2}nk(n-1-k)$ by Lemma 4.1 , there are at least

cotriangles in $G$. By Lemma 4.2, since each cotriangle is adjacent to at least $k$ vertices, we have that $kC_{n,k}\leq e(B)$.

On the other hand, by Lemma 4.3, the maximum amount of cotriangles adjacent to any fixed vertex in $G$ is $T_{n,k}=\binom{k}{2}(n-2k)+\binom{k}{3}$. Therefore, $e(B)\leq nT_{n,k}$.

It follows that $kC_{n,k}\leq e(B)\leq nT_{n,k}$. Now, the difference $nT_{n,k}-kC_{n,k}$ is equal to $-\frac{kn}{6}\,a(n,k)$, where $a(n,k)=n^{2}-6kn+(7k^{2}+k)$. Hence, we must have $a(n,k)\leq 0$. Fixing $k$, and considering $a(n,k)$ as a quadratic polynomial on $n$, its roots are $3k\pm\sqrt{2k^{2}-k}$. From this, the theorem follows. ∎