Non-existence of quasi-symmetric designs with restricted block graphs

Abstract

Quasi-symmetric designs (QSDs) with particular block graphs are investigated. We rule out the possibility of a QSD with block graph that has the same parameters as that of the Symplectic graph Sp(2t, q), where q is an odd prime power or its complement. We obtain support for Bagchi’s recent conjecture, which states that ‘For the existence of a quasi-symmetric 2-design with block graph $K_{m\times n}$, we must have $m \equiv n+ 1 \pmod {n^2}$’. Under certain conditions, we rule out the possibility of a QSD having a pseudo-Latin square or negative Latin square block graph.

1 Introduction

Let X be a finite set of v elements called points, and $\beta$ be a set of k-element subsets of X called blocks, such that each pair of points occur in $\lambda$ blocks, then the pair $\mathbf{D} = (X,\beta )$ is 2-$(v,k,\lambda )$ design. For a 2-$(v,k,\lambda )$ design D, the number of blocks containing $\alpha$ in X is r, which is independent of $\alpha$. The number of blocks in D is denoted by b.

An integer $\lambda _1$, $0\le \lambda _1<k$, is an intersection number of D if there exist $B,B'\in \beta$ such that $|B\cap B^{\prime }| = \lambda _1$. Symmetric designs have exactly one intersection number.

A 2-design with two intersection numbers is a quasi-symmetric design (QSD). Denote these intersection numbers by $\lambda _1$ and $\lambda _2$, where $0\le \lambda _1< \lambda _2<k$. We denote $\mu =\lambda _2-\lambda _1$, and call it as the defect of the QSD.

The parameters $(v,b,r,k,\lambda ;\lambda _1,\lambda _2)$ are the standard parameters of a QSD, which are said to be feasible if they satisfy all necessary conditions given in the Lemma 2.1. Complete parametric classification of QSDs with $\mu =1,2,3$ has been obtained in [4,5,6].

The block graph G of a QSD D has vertices that are blocks of D, where two distinct blocks $B,B^{\prime }$ are adjacent if and only if $|B\cap B'|=\lambda _2$. It was shown in [3, 11] that G is a strongly regular graph (SRG) with parameters (b, a, c, d). Here b is the number of vertices of G, i.e. the number of blocks of the design D, a its valency, any two adjacent vertices have exactly c common neighbors and any two non-adjacent vertices have exactly d common neighbors. We assume, as is customary, that a SRG is connected but is neither the null graph nor the complete graph.

The adjacency matrix of G is the $b \times b$ matrix A, with its rows and columns indexed by the vertices of G, such that, for vertices x, y, the (x, y)-th entry A(x, y) of A is 1 if x, y are adjacent in G, and A(x, y) = 0 otherwise. The spectrum spec(A) (i.e., the multi-set of eigenvalues of A, counting multiplicity) is also called the spectrum of G, and is denoted spec(G). A connected SRG G has exactly three distinct eigenvalues, which we shall denote by $a> \rho > \sigma$, with corresponding multiplicities 1, f, g. Here a is the degree of G and $f + g + 1 = b$. Since ${\text {trace}}(A) = 0$, we have $a = -f \rho - g\sigma .$ If G is non-complete then we have the following inequalities, known as the Krein Bounds, [10].

• 1. $(\rho + 1)(a + \rho + 2\rho \sigma ) \le (a + \rho )(\sigma + 1)^2$;

• 2. $(\sigma + 1)(a + \sigma + 2\rho \sigma ) \le (a + \sigma )(\rho + 1)^2.$

It is known to be a difficult problem to decide which SRGs are block graphs of QSDs. In [7, 8], it was established that several infinite families of SRGs are not block graphs of QSDs. In the recent paper [1], Bagchi obtained several restrictions on parameters of the block graph of a QSD in terms of its spectral parameters. Efforts were made to characterize QSDs associated with a particular class of SRGs. The following conjecture related to QSDs with block graph, the complete multi-partite graph $K_{m\times n} (m \ge 2, n \ge 2),$ was made.

Conjecture 1.1

Bagchi, [1] For the existence of a quasi-symmetric 2-design with block graph $K_{m\times n}$, we must have $m \equiv n+ 1 \pmod {n^2}$.

In support of the Conjecture 1.1, we rule out the possibility of QSD’s with block graph $K_{m\times n}$, if $n=h \alpha , m=h \beta +1$ for positive integers $\alpha \ge 2,\beta$ such that $\gcd (n, m-1)=h$, and $1\le h<4 \alpha$ or $\gcd (h,\alpha -\beta )=1$.

In [1], several algebraic conditions are given on q, for Symplectic graphs Sp(2t, q), where $q>2$ a prime power and $t\ge 2$ to be a block graph of QSDs. It was hinted that for each fixed prime power $q > 2$, the graph Sp(2t, q) is a block graphs of QSDs for at most finitely many values of t. We continue with the proof of Corollary 2.6 of [1] and rule out the possibility of QSDs with block graph that has the same parameters as that of the Symplectic graph Sp(2t, q). To rule out the possibility of QSDs with associated graph that has the same parameters as that of the complement of Symplectic graph Sp(2t, q), we use the technique developed in [8].

Under certain conditions, we rule out the possibility of a QSD having a pseudo-Latin square or negative Latin square block graph.

We follow [1] for definitions and terminology. Symbolic calculations were made easy with the help of Mathematica [13].

2 Preliminaries

Lemma 2.1

[9, 12] Let D be a QSD with standard parameter set $(v,b,r,k,\lambda ;\lambda _1,\lambda _2)$. Then the following relations hold:

• 1. $vr=bk$ and $\lambda (v-1)=r(k-1)$.

• 2. $k(r-1)(\lambda _1+\lambda _2-1)-\lambda _1\lambda _2(b-1)=k(k-1)(\lambda -1).$

• 3. $\mu =\lambda _2-\lambda _1$ divides $k-\lambda _1$ and $r-\lambda$.

• 4. $-\sigma =\dfrac{k-\lambda _1}{\mu }>0$ and $\rho -\sigma =\dfrac{r-\lambda }{\mu } >0$.

Theorem 2.2

[8], Theorem 6 (iii)] Let D be a QSD with parameters $(v,b,r,k,\lambda ;\lambda _1,\lambda _2)$ and G be the strongly regular block graph with parameters (b, a, c, d) of D. Then, we have

$$\begin{aligned} \mu =\frac{\left( -a + c - d -\sigma - b\,\sigma \right) \,\left( b - s \right) \,s}{b\,\left( c - d - 2\,\sigma \right) \,\left( -a +\sigma - b\,\sigma \right) } \end{aligned}$$

(2.1)

for a positive integer $s=\dfrac{(-a +\sigma - b \sigma ) \mu }{(\lambda _1 -\sigma \mu )}$.

Corollary 2.3

[1], Corollary 2.6.] Let $q > 2$ be a prime power and let $t \ge 2$ be an integer. Then, a quasi-symmetric 2-design of defect $\mu$ with block graph Sp(2t, q) is parametrically feasible if and only if t is even, $q \equiv 3\pmod 8, \mu = (q^t - q + 2)/8$, and the pair (q, t) satisfies

$$\begin{aligned} \left( \frac{q^t-1}{q-1} \right) ^2 - q^t \left( \frac{q^{t-1}-1}{q-1} \right) = x^2 \end{aligned}$$

(2.2)

for some integer x.

3 QSDs with complete multipartite graphs

The complete multi-partite graph $K_{m\times n} (m \ge 2, n \ge 2)$ has mn vertices partitioned into m parts of size n each, where two vertices are adjacent if and only if they are in different parts. In other words, $K_{m\times n}$ is the complement of $mK_n$ (the disjoint union of m copies of the n-vertex complete graph $K_n$). In this section we rule out the possibility of QSDs with complete multi-partite block graph under certain conditions, which provide support to the Conjecture 1.1.

Theorem 3.1

Let D be a QSD whose block graph has the same parameters as that of the complete multipartite graphs with $m\ge 2$ classes of size $n\ge 2$, i.e.,

$$\begin{aligned} (nm, n(m-1), n(m-2), n(m-1) ). \end{aligned}$$

If $\gamma =\gcd (n m-m+1,n^2)$, then $\gamma \ge 4(n-1)$.

Proof

We find $\sigma =-n.$ We use Eq. (2.1) to find

$$\begin{aligned} \mu =\frac{s (n m-s) (n m-m+1)}{(n-1) n^2 m^2}. \end{aligned}$$

(3.1)

If $\gamma =\gcd (n m-m+1,n^2)$ then $(n-1) n^2 m^2$ divides $s (n m-s) \gamma$, write $s (n m-s) \gamma =e (n-1) n^2 m^2$ for some positive integer e and observe that the discriminant of this quadratic in s is $n^2 m^2 \gamma (\gamma -4 e (n-1))$, which is a perfect square. As $e\ge 1$, we get $\gamma \ge 4 (n-1)$. $\square$

Remark 3.2

• 1. As an application of the Theorem 2.3 of [1] one can show that $m-1\ge n$, where equality holds if and only if $\mu =1$ and D is a 2-$( n^2, n, 1)$ design, known as affine plane of order n.

• 2. The truthfulness of Conjecture 1.1 implies n divides $m-1$.

• 3. Suppose $m-1>n$ and $n=h \alpha , m=h \beta +1$ for positive integers $\alpha , \beta$ such that $\gcd (n, m-1)=h$. Then

  $$\begin{aligned} \gamma= & {} \gcd (n^2, n m-m+1) \\= & {} \gcd (h^2 \alpha ^2, h (h \beta \alpha +\alpha -\beta ) ) \\= & {} h \gcd (h \alpha ^2, h \beta \alpha +\alpha -\beta ) \\= & {} h \gcd (h, h \beta \alpha +\alpha -\beta ) \text { as } \gcd (\alpha , \beta )=1\\= & {} h \gcd (h, \alpha -\beta ). \end{aligned}$$

  We take $\gamma =hh'$, with $h'=\gcd (h , \alpha -\beta )$. As $\gamma \ge 4(n-1)$ and $h h' \ge 4 (h \alpha -1)$. Hence $h' \ge 4 (\alpha -1)$. If $h'< 4$ then $\alpha =1$, which implies n divides $m-1$.

In support of the Conjecture 1.1, we give the following results.

Corollary 3.3

There is no QSD whose block graph has the same parameters as that of the complete multipartite graph with $m\ge 2$ classes of size $n\ge 2$, with $\gcd (n,m-1)=1$.

Proof

We give proof with same notations as used in the Corollary 2.4 of [1]. Since $m= tn^2/\alpha + n+1$, this means that $\gcd (tn^2/\alpha , n) = 1$; also, since $n = l +l^* + 2\alpha$, $\alpha \le n/2$. Since $n^2$ divides $(tn^2/\alpha )(\alpha )$ and is co-prime to the first factor, it follows that $n^2$ divides $\alpha$, and so $\alpha \ge n^2$, which is a contradiction.

Alternately, if $\gcd (n,m-1)=1$, then $\gamma =\gcd (n m-m+1,n^2)=1$, which contradicts Theorem 3.1. $\square$

If $m \not \equiv n+1 \pmod {n^2}$, and $n=h \alpha , m=h \beta +1$ for positive integers $\alpha ,\beta$ such that $\gcd (n, m-1)=h$, then $\alpha \ge 2$.

Theorem 3.4

Let G be a SRG that has the same parameters as that of the complete multipartite graph with $m\ge 2$ classes of size $n\ge ~2$. Suppose $n=h \alpha , m=h \beta +1$ for positive integers $\alpha \ge 2, \beta$ such that $\gcd (n, m-1)=h$. If $1<h<4 \alpha$ or $\gcd (h,\alpha -\beta )=1$, then there is no QSD whose block graph is G.

Proof

We use Eq. (2.1) to find

$$\begin{aligned} \mu =\frac{s (h \beta \alpha +\alpha -\beta ) \left( \alpha \beta h^2+\alpha h-s\right) }{h \alpha ^2 (h \alpha -1) (h \beta +1)^2}. \end{aligned}$$

As $\gcd (\alpha ,\beta )=1$, we get $\gcd (\alpha ^2 (h \alpha -1) (h \beta +1)^2, h \beta \alpha +\alpha -\beta )=1$, hence

$$\begin{aligned} \frac{s \left( \alpha \beta h^2+\alpha h-s\right) }{ \alpha ^2 (h \alpha -1) (h \beta +1)^2}=e, \end{aligned}$$

(3.2)

for some positive integer e. We consider the Eq. (3.2) as a quadratic in s and find the discriminant

$$\begin{aligned} \Delta =\alpha ^2 (h \beta +1)^2 \left( h^2-4 e \alpha h+4 e\right) . \end{aligned}$$

Observe that $h^2-4 e \alpha h+4 e\le h(h-4 \alpha ) +4$, which is negative for $1<h<4 \alpha$ and $\alpha \ge 2$. This a contradiction as s is a positive integer.

If $\gcd (h,\alpha -\beta )=1$, then we get $\gcd (h\alpha ^2 (h \alpha -1) (h \beta +1)^2, h \beta \alpha +\alpha -\beta )=1$, hence

$$\begin{aligned} \frac{s \left( \alpha \beta h^2+\alpha h-s\right) }{ h\alpha ^2 (h \alpha -1) (h \beta +1)^2}=e, \end{aligned}$$

(3.3)

for some positive integer e. As before, we consider the Eq. (3.3) as a quadratic in s and find the discriminant

$$\Delta =h \alpha ^2 (h \beta +1)^2 (h+e (4-4 h \alpha )).$$

Observe that $h+e (4-4 h \alpha )\le 4-h (4 \alpha -1)<0$, as $\alpha \ge 2$ and $h>1$, which is a contradiction. $\square$

4 QSDs with Symplectic graphs

Let $t \ge 2$ and let q be a prime power. Take a (2t)-dimensional vector space V over the field of order q with a non-degenerate symplectic bilinear form $< \cdot , \cdot>$ (such a form is unique up to linear isomorphisms). Let $P(V ) = PG(2t-1, q)$ be the corresponding projective space. For non-zero vectors $x \in V$, let [x] denote the point in P(V) with homogeneous co-ordinates x. The symplectic graph Sp(2t, q) has the points of $PG(2t - 1, q)$ as its vertices. Two points [x], [y] are adjacent in Sp(2t, q) if $<x, y>\ne 0$.

Theorem 4.1

Let $q>2$ be a prime power. Then there does not exist a QSD with block graph that has the same parameters as that of the Symplectic graph Sp(2t, q), with $t\ge 2$.

Proof

We show that the Eq. (2.2) have no integer solution and use Corollary 2.3 to complete the proof. The condition $q \equiv 3\pmod 8$ obtained in the Corollary 2.3 implies q must be an odd prime power. We assume the Eq. (2.2) has integer solutions and rewrite it as follows:

$$\begin{aligned} \left( q^t-1 \right) ^2 - q^t \left( q-1 \right) \left( q^{t-1}-1 \right) = y^2, \end{aligned}$$

where $y=x(q-1)$. Observe that $q^t \left( q^{t-1}+q-3 \right) =y^2-1$, which implies $q^t$ divides either $y-1$ or $y+1$, as q is an odd prime power. We take $y=uq^t+1$ and $y=uq^t-1$, for positive integer u to observe that

$$\begin{aligned} \left( q^t-1 \right) ^2 - q^t \left( q-1 \right) \left( q^{t-1}-1 \right) - y^2= & {} -q^{t-1} \left( -q^t-q^2+3q+u^2 q^{t+1}+2 u q \right) \\\le & {} -q^{t-1} \left( q^{t+1}-q^t-q^2+5 q\right) \\< & {} 0, \end{aligned}$$

and

$$\begin{aligned} \left( q^t-1 \right) ^2 - q^t \left( q-1 \right) \left( q^{t-1}-1 \right) - y^2= & {} -q^{t-1} \left( -q^t+u^2 q^{t+1}-q^2-2 u q+3 q\right) \\\le & {} -(q-1) q^{t-1} \left( q^t-q\right) \\< & {} 0, \end{aligned}$$

respectively, which is a contradiction. $\square$

Theorem 4.2

There is no QSD whose block graph parameters are

$$\begin{aligned} \left( \frac{q^{2 t}-1}{q-1}, \frac{q \left( q^{2 t-2}-1\right) }{q-1}, \frac{\left( q^{2 t-4}-1\right) q^2}{q-1}+q-1, \frac{\left( q^{2 t-4}-1\right) q^2}{q-1}+q+1 \right) , \end{aligned}$$

which are same as that of the complement of Symplectic graph Sp(2t, q), where q is an odd prime power and $t\ge 2$.

Proof

We find $\sigma =-q^{t-1}-1.$ We use Eq. (2.1) to find

$$\begin{aligned} \mu= & {} \frac{ \left( q^t+q-2\right) s \left( q^{2 t}-1-s q+s\right) }{2 q^t \left( q^t-1\right) ^2 \left( q^{t-1}+1\right) }\\= & {} \frac{ \left( (q^t-1)+(q-1)\right) s \left( \left( q^t-1\right) \left( q^t+1\right) -(q-1) s\right) }{2q^t \left( q^t-1\right) ^2 \left( q^{t-1}+1\right) }\\= & {} \frac{(q^{t-1}+q^{t-2}+\cdots +q+2)((q^{t-1}+q^{t-2}+\cdots +q+1)(q^t+1) -s ) s}{2q^t (q^{t-1}+q^{t-2}+\cdots +q+1)^2 \left( q^{t-1}+1\right) }\\ \end{aligned}$$

Observe the following:

• 1. $q^t-1=(q-1)(q^{t-1}+q^{t-2}+\cdots +q+1)$;

• 2. $q^t+q-2=(q^t-1)+(q-1)= (q-1)(q^{t-1}+q^{t-2}+\cdots +q+2)$;

• 3. $\gcd (q^{t-1}+q^{t-2}+\cdots +q+2, q^t )=1;$

• 4. $\gcd (q^{t-1}+q^{t-2}+\cdots +q+2, q^{t-1}+q^{t-2}+\cdots +q+1 )=1;$

• 5. $\left( q^{t-1}+q^{t-2}+\cdots +q+2\right) -\left( q^{t-1}+1\right) =q^{t-2}+\cdots +q+1$;

• 6. $\left( q^{t-1}+1\right) -(q^{t-2}+\cdots +q+1)(q-1)=2$;

• 7. $\gcd (q^{t-1}+q^{t-2}+\cdots +q+2, q^{t-1}+1 )={\left\{ \begin{array}{ll} 1 &{}\text { if } t \text { is an even integer;}\\ 2 &{}\text { if } t \text { is an odd integer}. \end{array}\right. }$

As before we get

$$\begin{aligned} \frac{2((q^{t-1}+q^{t-2}+\cdots +q+1)(q^t+1) -s ) s}{q^t (q^{t-1}+q^{t-2}+\cdots +q+1)^2 \left( q^{t-1}+1\right) }=e, \end{aligned}$$

for some positive integer e.

We take $\alpha =q^{t-1}+q^{t-2}+\cdots +q+1$ and observe that

$$\begin{aligned} \frac{2(\alpha (q^t+1) -s ) s}{q^t \alpha ^2 \left( q^{t-1}+1\right) }=e, \end{aligned}$$

for some positive integer e.

Discriminant of the above quadratic is $4 \alpha ^2\Delta$, where $\Delta = \left( q^t+1\right) ^2-2 e q^t \left( q^{t-1}+1\right)$. Observe that $\Delta$ must be a perfect square. We take $\Delta =x^2$ for some positive integer x and, as q is an odd prime, observe that $q^t$ divides either $x-1$ or $x+1$.

If $x=q^t u+1$, for some positive integer u, then $\Delta -x^2=q^t\delta (u)$, where $\delta (u)=-2 e q^{t-1}+q^t-2 e+2-u \left( u q^t+2\right)$, which is a decreasing function of u. Hence $\delta (u)\le \delta (1)= -2 e \left( q^{t-1}+1\right) <0$, a contradiction.

If $x=q^t u-1$, for some positive integer u, then $\Delta -x^2=q^t\delta (u)$, where $\delta (u)=-2 e q^{t-1}+q^t-2 e+2-u \left( q^t u-2\right)$, which is a decreasing function of u. Hence $\delta (u)\le \delta (1)=-2 \left( e q^{t-1}+e-2\right) <0$, a contradiction. $\square$

5 QSDs with pseudo-Latin square and negative Latin square graphs

Given $m-2$ mutually orthogonal Latin squares of order n with $m-1<n$, the vertices of a Latin square graph $LS_m(n)$ are the $n^2$ cells; two vertices are adjacent if and only if they lie in the same row or column or they have same entry in one of the Latin squares. This graph is a SRG, with parameters $(n^2, m(n-1), n+m(m-3), m(m-1) )$. A SRG with these parameters is known as a pseudo-Latin square graph, denoted by $L_m(n)$. A Negative Latin square graph $NL_m(n)$, is obtained by replacing m and n by their negatives in the parameters of a $LS_m(n)$. Hence $NL_m(n)$ has parameters $(n^2, m(n + 1), m^2 + 3m - n, m(m + 1))$, where $n \le m^2 + 3m$, and equality holds if and only if the Krein bounds are met. In [2], Cameron, Goethals and Seidel characterized SRG’s attaining the Krein bounds in terms of Negative Latin square graph $NL_e(e^2 + 3e).$ In [8], the possibility of QSD’s whose block graph is $NL_e(e^2 + 3e),$ with $2 \le e$ or its complement was ruled out.

Theorem 5.1

Suppose $m=h \alpha +1,n=h \beta ,$ for positive integers $\alpha$ and $\beta$ such that $\gcd (n, m-1)=h$. If $1\le h^2<4 \alpha$ or $\gcd (h,\beta -\alpha )=1$, then there is no QSD whose block graph is a pseudo-Latin Square graph $L_m(n)$.

Proof

For a pseudo-Latin Square graph $\sigma =-m.$ As before, we use Eq. (2.1) to find

$$\begin{aligned} \mu =\frac{ (h \beta \alpha +\beta -\alpha ) \left( h^2 \beta ^2-s\right) s}{h^2 (h \alpha +1) \beta ^3 (h \beta -1)}. \end{aligned}$$

As $\gcd (\alpha ,\beta )=1$, we get the following:

• 1. $\gcd (h \beta \alpha +\beta -\alpha , \beta ^3)=1$;

• 2. $\gcd (h \beta \alpha +\beta -\alpha , (h \beta -1))=1$;

• 3. $\gcd (h \beta \alpha +\beta -\alpha , (h \alpha +1))=1$.

As before we get

$$\begin{aligned} \frac{ \left( h^2 \beta ^2-s\right) s}{(h \alpha +1) \beta ^3 (h \beta -1)}=e, \end{aligned}$$

for some positive integer e.

Discriminant of above quadratic is $\beta ^3\Delta$, where

$$\begin{aligned} \Delta= & {} \beta h^4+e (4-4 h (h \beta \alpha -\alpha +\beta ))\\\le & {} \beta h^4+ (4-4 h (h \beta \alpha -\alpha +\beta )) \\= & {} h \left( 4 (\alpha -\beta )+h \left( h^2-4 \alpha \right) \beta \right) +4. \end{aligned}$$

If $1\le h^2<4 \alpha$ then as $\alpha < \beta$, we get $\Delta <0$, which is contradiction.

If $\gcd (h,\beta -\alpha )=1$, then $\gcd (h \beta \alpha +\beta -\alpha ,h^2 (h \alpha +1) \beta ^3 (h \beta -1)) =1$. Hence

$$\begin{aligned} \frac{ \left( h^2 \beta ^2-s\right) s}{h^2(h \alpha +1) \beta ^3 (h \beta -1)}=e, \end{aligned}$$

for some positive integer e.

Discriminant of above quadratic is $h^2\beta ^3\Delta$, where

$$\begin{aligned} \Delta= & {} \beta h^2+e \left( -4 \alpha \beta h^2+4 (\alpha -\beta ) h+4\right) \\\le & {} \beta h^2+ \left( -4 \alpha \beta h^2+4 (\alpha -\beta ) h+4\right) \\= & {} -(4 \alpha -1) \beta h^2-4 (\beta -\alpha ) h+4. \end{aligned}$$

This implies $\Delta <0$, which is a contradiction. $\square$

Theorem 5.2

Suppose $m=h \alpha , n=h \beta$ for positive integers $\alpha$ and $\beta$ such that $\gcd (n, m)=h$. If $h^2<4(\beta -\alpha )$ or $\gcd (h,\alpha )=1$, then there is no QSD whose block graph is a negative Latin Square graph $NL_m(n)$.

Proof

For a negative Latin Square graph $\sigma =-(n-m).$ As before, we use Eq. (2.1) to find

$$\begin{aligned} \mu =\frac{ \left( h \beta ^2-h \alpha \beta -\alpha \right) \left( h^2 \beta ^2-s\right) s}{h^2 \beta ^3 (h \beta +1) (-h \alpha +h \beta -1)}. \end{aligned}$$

We observe the following:

• 1. As $\gcd (\alpha ,\beta )=1$, $\gcd (h \beta ^2-h \alpha \beta -\alpha ,\beta ^3)=1$;

• 2. $h \left( h \beta ^2-h \alpha \beta -\alpha \right) -(h \beta +1) (-h \alpha +h \beta -1)=1$;

• 3. $\gcd (h \beta ^2-h \alpha \beta -\alpha ,(h \beta +1) (-h \alpha +h \beta -1))=1$.

As before we have

$$\begin{aligned} \frac{s \left( h^2 \beta ^2-s\right) }{\beta ^3 (h \beta +1) (-h \alpha +h \beta -1)}=e, \end{aligned}$$

for some positive integer e.

Discriminant of above quadratic is $\beta ^3\Delta$, where

$$\begin{aligned} \Delta= & {} 4 (\alpha -\beta ) \beta h^2+\beta h^2+4 (h \alpha +1)\\\le & {} \left( h^2-4 (\beta -\alpha )\right) \beta h^2+4 (h \alpha +1) \end{aligned}$$

If $1<h^2<4 (\beta -\alpha )$ then as $\alpha < \beta$ we get $\Delta <0$, which is contradiction.

As $\gcd (h,\alpha )=1$, $\gcd (h \beta ^2-h \alpha \beta -\alpha ,h^2)=1$ we get

$$\begin{aligned} \frac{ \left( h^2 \beta ^2-s\right) s}{h^2 \beta ^3 (h \beta +1) (-h \alpha +h \beta -1)}=e; \end{aligned}$$

for some positive integer e. The discriminant of this quadratic in s is $h^2 \beta ^3\Delta$, where

$$\begin{aligned} \Delta= & {} \beta h^2+e \left( 4 (\alpha -\beta ) \beta h^2+4 (h \alpha +1)\right) \\\le & {} 4 (\alpha -\beta ) \beta h^2+(4 \alpha +h \beta ) h+4. \end{aligned}$$

As $h(\beta -\alpha )\ge 2$, we consider two cases (i) $h=1$ and $\beta \ge \alpha +2$; (ii) $h\ge 2$ and $\beta \ge \alpha +1$ to observe that $\Delta <0$, which is a contradiction. $\square$

Remark 5.3

Results similar to the Theorems 5.1 and 5.2 can be obtained for complements of pseudo-Latin square and negative Latin square graphs as these are also pseudo-Latin square and negative Latin square graphs respectively.