The Embedding of Annihilating-Ideal Graphs Associated to Lattices in the Projective Plane

Abstract

Let $(L,\wedge ,\vee )$ be a lattice with a least element 0. The annihilating-ideal graph of L, denoted by ${\mathbb {AG}}(L)$, is a graph whose vertex set is the set of all non-trivial ideals of L and, for every two distinct vertices I and J, I is adjacent to J if and only if $I\wedge J=\{0\}$. In this paper, we completely determine all finite lattices L with projective annihilating-ideal graphs ${\mathbb {AG}}(L)$.

1 Introduction

Recently, there has been considerable researches done on associating graphs with algebraic structures. For example, see [2, 4, 11,12,13]. The concept of a annihilating-ideal graph of a commutative ring R, denoted by ${\mathbb {AG}}(R)$, was introduced by Behboodi and Rakeei in [5] and [6]. Let ${\mathbb {A}}(R)$ be the set of annihilating-ideals of R, where a nonzero ideal I of R is called an annihilating-ideal, if there exists a nonzero ideal J of R such that $IJ=0$. The annihilating-ideal graph of R is a simple graph with vertex set ${\mathbb {A}}(R)$, and two distinct vertices I and J are adjacent if and only if $IJ=0$. The annihilating-ideal graph of a lattice L, denoted by ${\mathbb {AG}}(L)$, is defined by Khashyarmanesh et al in [1]. ${\mathbb {AG}}(L)$ is a graph whose vertex set is the set of all non-trivial ideals of L and, for every two distinct vertices I and J, I is adjacent to J, if and only if $I \wedge J=0$. In this work, we assume that L is a finite lattice and $A(L)=\{a_1,a_2,\dots ,a_n\}$ is the set of all atoms of L. In the second section of this paper, we completely characterize all finite lattices L with projective annihilating-ideal graphs ${\mathbb {AG}}(L)$.

First, we recall some definitions and notations on lattices. For basis facts concerning lattice, we refer to [9]. Recall that a lattice is an algebra $L=(L,\wedge ,\vee )$ with two binary operations $\wedge$ and $\vee$, satisfying the following conditions: for all $a,b,c \in L$,

• 1. $a\wedge a=a,\ a\vee a=a$,

• 2. $a\wedge b=b\wedge a,\ a \vee b=b \vee a$,

• 3. $(a\wedge b)\wedge c=a\wedge (b\wedge c),\ a \vee (b\vee c)=(a\vee b)\vee c,$ and

• 4. $a\vee (a\wedge b)=a\wedge (a\vee b)=a$.

By [15, Theorem 2.1], one can define an order $\le$ on L as follows: for any $a,b\in L$, we set $a\le b$ if and only if $a\wedge b=a$. Then $(L,\le )$ is an ordered set in which every pair of elements has a greatest lower bound $({\mathrm {g.l.b.}})$ and a least upper bound $({\mathrm {l.u.b.}})$. Conversely, let P be an ordered set such that, for every pair $a,b\in P$, ${\mathrm {g.l.b.}}(a,b)$ and ${\mathrm {l.u.b.}}(a,b)$ belong to P. For each a and b in P, we define $a\wedge b:={\mathrm {g.l.b.}}(a,b)$ and $a\vee b:={\mathrm {l.u.b.}}(a,b)$. Then $(P,\wedge ,\vee )$ is a lattice. A lattice L is said to be bounded if there are elements 0 and 1 in L such that $0\wedge a= 0$ and $a \vee 1=1$, for all $a\in L$. Clearly, every finite lattice is bounded. Let $(L,\wedge ,\vee )$ be a lattice with a least element 0 and I be a non-empty subset of L. We say that I is an ideal of L, denoted by $I\unlhd L$, if

• (i) For all $a,b\in I$, $a\vee b\in I$.

• (ii) If $0\le a\le b$ and $b\in I$, then $a\in I$.

For two distinct ideals I and J of a lattice L, we put $I \wedge J :=\{ x \wedge y ~~; ~~ x\in I, y\in J \}.$ In a lattice $(L,\wedge ,\vee )$ with a least element 0, an element a is called an atom if $a\ne 0$ and, for an element x in L, the relation $0\le x\le a$ implies that either $x=0$ or $x=a$. We denote the set of all atoms of L by A(L). Also, for an ideal I of L, A(I) denotes the set of all atoms contained in I.

Now we recall some definitions and notations on graphs. We use the standard terminology of graphs following [7]. In a graph G, for two distinct vertices a and b in G, the notation $a-b$ means that a and b are adjacent. For a positive integer r, an r-partite graph is one whose vertex set can be partitioned into r subsets so that no edge has both ends in any one subset. A completer-partite graph is one in which each vertex is joined to every vertex that is not in the same subset. The complete bipartite graph (2-partite graph) with part sizes m and n is denoted by $K_{m, n}$. A graph is said to be planar if it can be drawn in the plane so that its edges intersect only at their ends. A graph G is said to be contracted to a graph H if there exists a sequence of elementary contractions which transforms G into H, where an elementary contraction consists of deletion of a vertex or an edge or the identification of two adjacent vertices. A subdivision of a graph is any graph that can be obtained from the original graph by replacing edges by paths. A remarkable simple characterization of the planar graphs was given by Kuratowski in 1930. Kuratowski’s theorem says that a graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$ (cf. [7, p.153]). By a surface, we mean a connected compact two-dimensional manifold without boundary. If a disc is cut from a sphere and it is closed by a Möbius band, then the obtained surface is called projective plane. The projective plane can also be obtained by identifying every point of an open disc with its antipodal points. A graph G is embeddable in a surface S if the vertices of G are assigned to distinct points in S such that every edge of G is a simple arc in S connecting the two vertices which are joined in G. If G can not be embedded in S, then G has at least two edges intersecting at a point which is not a vertex of G. We say a graph G is irreducible for a surface S if G does not embed in S, but any proper subgraph of G embeds in S. The set of 103 irreducible graphs for the projective plane has been found by Glover et al. in [10], and Archdeacon in [3] proved that this list is complete. This list also has been checked by Myrvold and Roth in [14]. Hence a graph embeds in the projective plane, which is called a projective graph, if and only if it contains no subdivision of 103 graphs in [3]. Note that a complete graph $K_n$ is projective if $n=5$ or 6, and the only projective complete bipartite graphs are $K_{3,3}$ and $K_{3,4}$ (see [8]). Note that a planar graph is not considered as a projective graph.

The canonical representation of a projective plane

2 Projective Annihilating-Ideal Graphs of Lattices

In this section, we study the projectivity of the annihilating-ideal graph ${\mathbb {AG}}(L)$. We begin this section with the following notation, which is needed in the rest of the paper.

Notation 2.1

Let $i_{1}, i_{2},\dots , i_{n}$ be integers with $1\le i_{1}< i_{2}< \dots < i_{k}\le n$. The notation $U _{i_{1} i_{2} \dots i_{k}}$ stands for the following set:

$$\begin{aligned} \left\{ I\unlhd L ;~~ \left\{ a_{i_{1}}, a_{ i_{2}}, \dots , a_{ i_{k}} \right\} \subseteq I ~~and~~ a_{j}\notin I, \mathrm {for}~~ j\in \left\{ 1, \dots ,n\right\} {\setminus }\left\{ i_{1}, \dots ,i_{k}\right\} \right\} . \end{aligned}$$

Note that no two distinct elements in $U_{i_{1} i_{2} \ldots i_{k}}$ are adjacent in ${\mathbb {AG}}(L)$. Also if the index sets $\{i_{1}, i_{2},\dots ,i_{k}\}$ and $\{j_{1}, j_{2},\dots , j_{k'}\}$ of $U_{i_{1} i_{2} \dots i_{k}}$ and $U_{j_{1} j_{2} \dots j_{k'}}$, respectively, are distinct, then one can easily check that $U_{i_{1} i_{2} \dots i_{k}} \cap U_{j_{1} j_{2} \dots j_{k'}} = \emptyset$. Moreover, $V({\mathbb {AG}}(L))= \bigcup U_{i_{1} i_{2} \ldots i_{k}}$, for all $1\le i_{1}< i_{2}< \dots < i_{k}\le n$. Suppose that L has n atoms. Note that $U_{12\dots n}$ consist of isolated vertices. Clearly, the isolated points do not affect projectivity. Hence, we ignore the set $U_{12\dots n}$ from the vertex set of ${\mathbb {AG}}(L)$, and so we do not show these points in our figures.

In the following lemma, we determine an upper bound for the number of atoms of lattice L such that the graph ${\mathbb {AG}}(L)$ is projective.

Lemma 2.2

If ${\mathbb {AG}}(L)$ is a projective graph, then $2\le |A(L)|\le 6$.

Proof

Suppose on the contrary that $|A(L)|=1$ or $|A(L)|> 6$. In the first situation, ${\mathbb {AG}}(L)$ is a totally disconnected graph, and so it is planar. Hence it is not a projective graph. In the second situation, since the induced subgraph of ${\mathbb {AG}}(L)$ on vertex set $\{\{0,a_{i}\}\}$, for $1\le i\le 7$, is a complete graph, one can find a subgraph isomorphic to $K_{7}$. Therefore, the graph ${\mathbb {AG}}(L)$ is not projective. Hence we have $2\le |A(L)|\le 6$. $\square$

By Theorem 2.6 in [1], the graph ${\mathbb {AG}}(L)$ is complete bipartite if and only if $|A(L)|=2$. In the following theorem, we state a necessary and sufficient condition for the projectivity of ${\mathbb {AG}}(L)$, when $|A(L)|=2$.

Theorem 2.3

Suppose that $|A(L)|=2$. Then ${\mathbb {AG}}(L)$ is a projective graph if and only if $|U_2|=3$, or 4 whenever $|U_1|=3$.

Proof

Let the graph ${\mathbb {AG}}(L)$ be projective. Assume to the contrary that $|U_1|\le 2$ or $|U_2|\le 2$. By [16, Proposition 2.3], the graph ${\mathbb {AG}}(L)$ is planar, which is a contradiction. Also if $|U_1|>3$ and $|U_2|>3$, then the graph ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$. And if $|U_1|=3$ and $|U_2|>4$, then the graph ${\mathbb {AG}}(L)$ contains a subgraph isomorphic to $K_{3,5}$. Hence ${\mathbb {AG}}(L)$ is not a projective graph. Therefore, we have $|U_2|=3$, or 4 whenever $|U_1|=3$.

The converse statement is clear. $\square$

Now, we investigate the projectivity of ${\mathbb {AG}}(L)$, when $|A(L)|=3$. In the following four cases, we probe the projectivity of ${\mathbb {AG}} (L)$ in the case that $|\bigcup _{i=1}^3 U_i|\ge 5$. Additionally, in the rest of work, we do not consider the cases that ${\mathbb {AG}}(L)$ is planar. For planar cases see [16].

Case 1$|\bigcup _{i=1}^3U_i| = 5$.

Without loss of generality, we may assume that $|U_1|=1$ whenever $U_{12}$ and $U_{13}$ are non-empty. It is clear that ${\mathbb {AG}}(L)$ is projective. Also if $|U_1|=3$ and $0<|U_{23}|\le 2$, then one can easily check that ${\mathbb {AG}}(L)$ is projective. In addition, if $|U_1| = 3$ and $|U_{23} |\ge 3$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$. So the graph ${\mathbb {AG}}(L)$ is not projective.

Case 2$|\bigcup _{i=1}^3U_i| = 6$.

Without loss of generality, we may assume that $|U_1|=|U_2|=|U_3|=2$ whenever $U_{12}$, $U_{13}$ and $U_{23}$ are non-empty. Then it is not hard to see the graph ${\mathbb {AG}}(L)$ is projective. Also if $|U_1|=3$ and $|U_{23}|\le 1$, then we observe that ${\mathbb {AG}}(L)$ is projective. And we may assume that $|U_1|=4$ and $|U_{23}|=1$. Clearly, the graph ${\mathbb {AG}}(L)$ is projective. Finally, if $|U_1| = 3$ or 4 whenever $|U_{23}| \ge 2$, then we can find a copy of $K_{3,5}$ or $K_{4,4}$ in the structure of the contraction of ${\mathbb {AG}}(L)$, respectively. Hence ${\mathbb {AG}}(L)$ is not projective.

Case 3$|\bigcup _{i =1}^3 U_i| = 7$.

Without loss of generality, we may assume that $|U_1|\in \{3,4\}$ and $U_{23}=\varnothing$. Then one can easily see that the graph ${\mathbb {AG}}(L)$ is projective. Otherwise, if $U_{23}$ is non-empty, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$ or $K_{4,4}$. So the graph ${\mathbb {AG}}(L)$ is not projective. Also if $|U_1 |= |U_2| = 3$ and $U_{13}=U_{23}=\varnothing$, then it is not hard to see that the graph ${\mathbb {AG}}(L)$ is projective. Otherwise, if $U_{13}$ or $U_{23}$ is non-empty, then we have a subgraph isomorphic to $K_{3,5}$ in the contraction of ${\mathbb {AG}}(L)$. Hence the graph ${\mathbb {AG}}(L)$ is not projective. Additionally, if $|U_1|=5$ and $U_{23}= \varnothing$, then ${\mathbb {AG}}(L)$ is planar, which is not projective. And if $U_{23} \ne \varnothing$, then we can find a copy of $K_{3,5}$ in the structure of ${\mathbb {AG}}(L)$. So the graph ${\mathbb {AG}}(L)$ is not projective.

Case 4$|\bigcup _{i =1}^3U_i| \ge 8$.

Without loss of generality, we may assume that $|U_1|=|\bigcup _{i =1}^3U_i|{\setminus } 2$ and $U_{23}= \varnothing$. Then ${\mathbb {AG}}(L)$ is planar, which is not projective. And if $U_{23} \ne \varnothing$, then we can find a copy of $K_{3,5}$ in the structure of the contraction of ${\mathbb {AG}}(L)$. So the graph ${\mathbb {AG}}(L)$ is not projective. Also if none of the $U_i$’s has $|\bigcup _{i=1}^3U_i|{\setminus } 2$ elements, then the contraction of ${\mathbb {AG}}(L)$ contains a subgraph isomorphic to $K_{3,5}$ or $K_{4,4}$. Therefore, the graph ${\mathbb {AG}}(L)$ is not projective.

Now, by the above discussion, one can easily see that the following theorem holds.

Theorem 2.4

Let $|A(L)| = 3$. Then ${\mathbb {AG}}(L)$ is a projective graph if and only if one of the following conditions holds:

• (i) $|\bigcup _{i =1}^3 U_i| = 5$ and one of the following cases is satisfied:

  • (a) There is $U_i$ with $|U_i| = 3$ and $0 <|U_{jk}| \le 2$, for $1 \le i\ne j\ne k \le 3$.

  • (b) There is a unique $U_i$ with $|U_i| =1$ whenever $U_{ij}$ and $U_{ik}$ are non-empty sets, for $1 \le i\ne j\ne k\le 3$.

• (ii) $|\bigcup _{i=1}^3 U_i| = 6$ and one of the following cases is satisfied:

  • (a) There exists i with $1 \le i \le 3$, such that $|U_i| = 4$ and $|U_{jk} | = 1$, for $1 \le i\ne j\ne k \le 3$.

  • (b) There exists i with $1 \le i \le 3$, such that $|U_i| =3$ and $|U_{jk}| \le 1$, for $1 \le i\ne j\ne k \le 3$.

  • (c) $|U_i|= 2$, for all i with $1 \le i \le 3$, and $U_{jk} \ne \varnothing$, for all $1 \le j\ne k \le 3$.

• (iii) $|\bigcup _{i=1}^3U_i|= 7$ and one of the following cases is satisfied:

  • (a) $|U_i|\in \{3,4\}$, for some unique integer i with $1\le i \le 3$, such that and $U_{jk}$ is empty, for $1 \le i\ne j \ne k \le 3$.

  • (b) $|U_i|=|U_j| = 3$, for some integers i and j, with $1 \le i\ne j \le 3$ whenever $U_{ik}$ and $U_{jk}$ are empty, for $1\le i\ne j\ne k \le 3$.

In the sequel, we investigate the projectivity of ${\mathbb {AG}}(L)$, when $|A(L) |= 4$. Suppose that $|\bigcup _{i=1}^4U_i| \ge 8$. Then it is easy to see that ${\mathbb {AG}}(L)$ is not projective, because one can see that the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$ or $K_{4,4}$. And so it is not projective.

As a result of the above note, we have the following lemma.

Lemma 2.5

If ${\mathbb {AG}}(L)$ is projective, then $|\bigcup _{i =1}^4 U_i| \le 7$.

Theorem 2.6

Suppose that $|A(L)| = 4$. Then ${\mathbb {AG}}(L)$ is projective if and only if one of the following statements holds:

• (i) $|\bigcup _{i =1}^4 U_i |= 5$ and $|U_i|= 2$, for some unique integer i with $1 \le i \le 4$. If $U_{jk}=\varnothing$, then $|U_{jkl}|\ne \varnothing$, with $i,j,k\notin \{i\}$. And if the size of $U_{jk}$ is 1 or 2 whenever at most one of the $U_{jk}$’s has exactly two elements, where $1\le i\ne j\ne k \le 4$.

• (ii) $|\bigcup _{i=1}^4 U_i| = 6$ and one of the following cases holds:

  • (a) $|U_i|=3$, for some integer i with $1 \le i\le 4$. If $|U_{jkl}| = 1$, with $1\le i\ne j\ne k\ne l\le 4$, then $U_{jk}=\varnothing$, for all $j,k \notin \{i\}$. Also if $U_{jkl}=\varnothing$, with $1\le i\ne j\ne k\ne l\le 4$, then $|U_{jk}|\le 1$ and at most one of the $U_{jk}$’s has exactly one element, where $j,k \notin \{i\}$.

  • (b) $|U_i|=|U_j|=2$, for some integers i and j with $1\le i\ne j \le 4$ whenever $|U_{kl}| \le 1$, where $1\le k<l\le 4$ and $k,l \notin \{i,j\}$. Also $U_{i'_1i'_2}=\varnothing$ whenever $|U_{i_1i_2} |=1$, for all $1 \le i_1\ne i'_1\ne i_2\ne i'_2 \le 4$, with $\{i'_1,i'_2\} = \{1,2,3,4\} {\setminus } \{ i_1,i_2\}$. Moreover, if $|U_{ik}|, |U_{il}| \le 1$ or $|U_{jk}|, |U_{jl}|\le 1$, then $|U_{kl}| \le 1$. Also if $|U_{ik}| = |U_{jk}| = 1$ or $|U_{il} |= |U_{jl}| = 1$, then $U_{kl} = \varnothing$.

• (iii) $|\bigcup _{i=1}^4 U_i |= 7$ and one of the following cases holds:

  • (a) $|U_i|= 4$, for some integer i with $1 \le i \le 4$ and $U_{jkl}=U_{jk}= \varnothing$, where $1 \le i\ne j\ne k\ne l \le 4$.

  • (b) $|U_i| = 3$ and $|U_j| = 2$, for some integers i and j with $1 \le i\ne j \le 4$ and $U_{jkl}=\varnothing$, where $k,l\notin \{i,j\}$ whenever $U_{ii_1} = U_{ji_1}= \varnothing$, where $i_1 \notin \{i,j\}$, with $1 \le i_1 \le 4$, and $U_{kl} = \varnothing$, where $k,l\notin \{i,j\}$.

Proof

First, assume that ${\mathbb {AG}}(L)$ is projective. Suppose on the contrary that none of the conditions (i), (ii) or (iii) holds. If $|\bigcup _{i=1}^4 U_i|=5$ and the statement (i) does not hold, then one of the $U_i$’s, $1 \le i\le 4$, say $U_1$, has two elements whenever $U_{234}$, $U_{23}$, $U_{24}$ and $U_{34}$ are empty. So ${\mathbb {AG}}(L)$ is planar, which is not projective. Additionally, if $|U_{23}|, |U_{24}|$ or $|U_{34}|$ is at least three, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of the subdivision of $K_{3,5}$. Now, we may assume that at least two of the sets $U_{23}$, $U_{24}$ or $U_{34}$ have two elements, say $U_{24}$ and $U_{34}$. Then a subgraph of ${\mathbb {AG}}(L)$ is isomorphic to $E_5$, one of the listed graphs in [10], as shown in Fig. 1. In this figure, we have $\{0,a_1\},I_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $I_{24},I'_{24}\in U_{24}$ and $I_{34},I'_{34}\in U_{34}$.

Fig. 1

$\{0, a_1\}, I_1$$\in U_1, \{0, a_2\} \in U_2$, $\{0, a_3\}\in U_3$, $\{0, a_4\}\in U_4, I_{24}$, $I'_{24} \in U_{242}\, \mathrm{and}\, I_{34}, I'_{34} \in U_{34}$

If $|\bigcup _{i=1}^4 U_i | = 6$ and the statement (ii) does not hold, then there is only one of the $U_i$’s, say $U_1$, such that $|U_1| = 3$ whenever $|U_{234}|\ge 2$. Hence the contraction of ${\mathbb {AG}}(L)$ contains a subgraph isomorphic to $K_{3,5}$. If $|U_{234}| =1$ and at least one of the sets $U_{23}, U_{24}$ or $U_{34}$, say $U_{23}$, has one element, then ${\mathbb {AG}}(L)$ contains a copy of $E_{18}$, one of the listed graphs in [10] (see Fig. 2). In this figure, we have $\{0,a_1\},I_1,J_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $I_{23}\in U_{23}$ and $I_{234}\in U_{234}$.

Fig. 2

$\{0, a_1\}, I_1$, $J_1 \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\}\in U_3$, $\{0, a_4\} \in U_4, I_{23} \in U_{23} \, \mathrm{and}\, I_{234} \in U_{234}$

If at least one of the sets $U_{23}$, $U_{24}$ or $U_{34}$ have two elements, then we can see that the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$. Additionally, we may assume that at least two of the sets $U_{23}, U_{24}$ or $U_{34}$, say $U_{23}$ and $U_{24}$, have one element. Then it is easy to find a copy of $E_{18}$, one of the listed graphs in [10], in the graph ${\mathbb {AG}}(L)$. Now, suppose that $|\bigcup _{i =1}^4 U_i | = 6$ and there exist distinct i and j such that $|U_i|=|U_j|=2$. Without loss of generality, we may assume that $|U_1| = |U_2| = 2$. When $|U_{34}| \ge 2$, we can find a subdivision of $K_{4,4}$ in the structure of the contraction of ${\mathbb {AG}}(L)$. If $|U_{13} |= 2$, then the contraction of the sets $U_2 \cup U_4$ and $U_1 \cup U_3 \cup U_{13}$ induces a copy of $K_{3,5}$. Moreover, we may assume that $|U_{12}|=|U_{34}|=1$ or $|U_{14}|=|U_{23}|=1$. In this case, the contraction of the graph ${\mathbb {AG}}(L)$ contains a copy of $E_3$ or $E_{18}$, two of the listed graphs in [10], respectively. Finally, suppose that $U_{13}$, $U_{23}$ and $U_{34}$ have one element. Consider the graph $D_8$, one of the listed graphs in [10], as shown in Fig. 3. In this figure, we have $\{0,a_1\},I_1\in U_1$, $\{0,a_2\},I_2\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $I_{13}\in U_{13}$, $I_{23}\in U_{23}$ and $I_{34}\in U_{34}$.

Fig. 3

$\{0, a_1\}, I_1 \in U_1$, $\{0, a_2\}, I_{2} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4,$$I_{13} \in U_{13}$, $I_{23} \in U_{23}$ and  $I_{34} \in U_{34}$

Clearly, for the case that $|U_{14}| = |U_{24}| = |U_{34}| = 1$, we have the similar result.

Suppose that $|\bigcup _{i =1}^4 U_i| = 7$ and the statement (iii) does not hold. First, assume that there exists only one $U_i$, say $U_1$, such that $|U_1| = 4$. If $U_{234} \ne \varnothing$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$. If one of the sets $U_{23}, U_{24}$ or $U_{34}$ is not empty, then $K_{4,4}$ is isomorphic to a subgraph of ${\mathbb {AG}}(L)$. Now, assume that there is a unique $U_i$, say $U_1$, with $|U_1|=3$. If $U_{234} \ne \varnothing$, then one can obtain a subdivision of $K_{3,5}$ in the structure of the contraction of ${\mathbb {AG}}(L)$. Also, we may assume that $U_{13}$ or $U_{14}$ is not empty. Then it is easy to see a copy of $K_{4,4}$ as a subgraph of ${\mathbb {AG}}(L)$. Moreover, if at least one of the sets $U_{23}$, $U_{24}$ or $U_{34}$ is not empty, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$ or $K_{3,5}$. Finally, assume that only one of the $U_i$’s, where $1 \le i \le 4$, has one element, exactly. Then $A_2$, one of the listed graphs in [10], is isomorphic to a subgraph of ${\mathbb {AG}}(L)$, as shown in Fig. 4. In this figure, we have $\{0,a_1\},I_1\in U_1$, $\{0,a_2\},I_2\in U_2$, $\{0,a_3\},I_3\in U_3$ and $\{0,a_4\}\in U_4$.

Fig. 4

$\{0, a_1\}, I_1 \in U_1$, $\{0, a_2\}, I_2 \in U_2$, $\{0, a_3\}, I_3 \in U_3$ and $\{0, a_4\} \in U_4$

Therefore, in all of the above situations, we have that ${\mathbb {AG}}(L)$ is not projective, which is a contradiction.

Conversely, if one of the conditions (i), (ii) or (iii) holds, then one can easily check that the graph ${\mathbb {AG}}(L)$ embeds in a projective plane. So it is a projective graph and the proof is complete . $\square$

In the rest of this paper, we need to consider the cases that $|A(L)|=5$ and 6.

First, assume that $|A(L)|=5$. If $|\bigcup _{i=1}^5U_i|\ge 8$, then one can easily realize that the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$ or $K_{3,5}$, which is not projective. Therefore, we investigate the cases that $|\bigcup _{i=1}^5U_i|=5,6$, or 7.

We continue this discussion with the following theorem.

Theorem 2.7

Let $|\bigcup _{i=1}^5U_i|=5$. Then ${\mathbb {AG}}(L)$ is a projective graph if and only if $|U_{ij}|\le 2$, for all $1\le i,j\le 5$ and one of the following conditions holds:

• (i) There is only one of the $U_{ij}$’s, such that $|U_{ij}|=2$ whenever $U_{i'j'}=\varnothing$, for $\{i',j'\}=\{1,2,\dots ,5\}{\setminus }\{i,j\}$, and also, for some $k\in \{1,2,\dots ,5\}{\setminus }\{i,j\}$, the number of such sets $U_{ki}$ and $U_{kj}$ with exactly one element is at most two. Moreover, for the sets $U_{k_1i}$ and $U_{k_2j}$ with $\{k_1,i\}\cap \{k_2,j\}=\varnothing$, we have $U_{k_1i}=\varnothing$ or $U_{k_2j}=\varnothing$.

• (ii) There is no $U_{ij}$, such that $|U_{ij}|=2$, and there exist at most three distinct sets $U_{ij}$, $U_{ij'}$ and $U_{ij''}$ with exactly one element, where $1\le i,j,j',j''\le 5$ whenever at most there is one $U_{kl}$ with $|U_{kl}|\le 1$, where $1\le k,l \le 5$ and if $U_{kl}$ has a vertex, then it is adjacent to at most one of the vertices in the sets $U_{ij}$, $U_{ij'}$ or $U_{ij''}$.

Proof

First, suppose that the graph ${\mathbb {AG}}(L)$ is projective and to the contrary that none of the conditions of theorem holds. Without loss of generality, assume that $|U_{12}|\ge 3$. Then the contraction of ${\mathbb {AG}}(L)$ contains a subgraph isomorphic to $K_{3,5}$. If $|U_{12}|=|U_{23}|=2$, then the graph ${\mathbb {AG}}(L)$ contains a subgraph isomorphic to subdivision of $E_5$, one of the listed graphs in [10]. If $|U_{12}|=2$ and $|U_{34}|=1$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$. If $|U_{12}|=2$ and $|U_{13}|=|U_{24}|=1$, then ${\mathbb {AG}}(L)$ contains a copy of $F_1$, one of the listed graphs in [10] (see Fig. 5). In this figure, we have $\{0,a_1\}\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{12},I'_{12}\in U_{12}$, $I_{13}\in U_{13}$ and $I_{24}\in U_{24}$.

Fig. 5

$\{0, a_1\} \in U_1$, $\{0, a_2\} \in U_{2}$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\} \in U_5$, $I_{12}, I'_{12} \in U_{12}$, $I_{13} \in U_{13} \, \mathrm{and} \, I_{24} \in U_{24}$

If $|U_{13}|=|U_{24}|=1$ and $|U_{14}|=|U_{23}|=1$, then the graph ${\mathbb {AG}}(L)$ contains a copy of $F_1$, one of the listed graphs in [10]. If $|U_{12}|=|U_{13}|=|U_{14}|=1$ and $|U_{25}|=1$, then $F_1$, one of the listed graphs in [10], is isomorphic to subgraph of ${\mathbb {AG}}(L)$. If $|U_{12}|=|U_{13}|=|U_{14}|=1$ and $|U_{23}|=|U_{34}|=1$, then the graph ${\mathbb {AG}}(L)$ contains a copy of $F_5$, one of the listed graphs in [10] (see Fig. 6). In this figure, we have $\{0,a_1\}\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{12}\in U_{12}$, $I_{13}\in U_{13}$, $I_{14}\in U_{14}$, $I_{23}\in U_{23}$ and $I_{34}\in U_{34}$.

Fig. 6

$\{0, a_1\} \in U_{1}$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\} \in U_5$, $I_{12} \in U_{12}$, $I_{13} \in U_{13}$, $I_{14} \in U_{14}$, $I_{23} \in U_{23}$$\,\mathrm{and}\, I_{34} \in U_{34}$

If $|U_{12}|=|U_{13}|=|U_{14}|=|U_{15}|=1$, then ${\mathbb {AG}}(L)$ contains a copy of $E_{22}$, one of the listed graphs in [10] (see Fig. 7). In this figure, we have $\{0,a_1\}\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{12}\in U_{12}$, $I_{13}\in U_{13}$, $I_{14}\in U_{14}$ and $I_{15}\in U_{15}$.

Fig. 7

$\{0, a_1\} \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\} \in U_5$, $I_{12} \in U_{12}$, $I_{13} \in U_{13}$, $I_{14} \in U_{14}$  and  $I_{15} \in U_{15}$

So, by the above situations, the graph ${\mathbb {AG}}(L)$ is not projective, which is a contradiction.

Conversely, one can easily check that if one of the conditions (i) and (ii) holds, then ${\mathbb {AG}}(L)$ is a projective graph. $\square$

Now, suppose that $|\bigcup _{i=1}^5U_i|=6$. Then there is only one of the $U_i$’s, say $U_1$, such that $|U_1|=2$. It is clear that $U_2,U_3,U_4$ and $U_5$ have one element, exactly.

Theorem 2.8

Suppose that $|\bigcup _{i=1}^5U_i|=6$ and $|U_1|=2$ whenever $|U_{ijk}|\le 1$, for $2\le i,j,k\le 5$ and $|U_{ij}|\le 1$, for $1\le i,j\le 5$. Then ${\mathbb {AG}}(L)$ is a projective graph if and only if one of the following conditions holds:

• (i) There exist at most two distinct sets $U_{1i}$ and $U_{1j}$, where $2\le i,j\le 5$, such that $|U_{1i}|=|U_{1j}|=|U_{ij}|=1$.

• (ii) There exist at most two distinct sets with exactly one element $U_{ijk}$, $U_{i'j'k'}$, where $2\le i,i',j,j',k,k'\le 5$. Moreover, we have at most two sets $U_{1{j_1}}, U_{1{j_2}}$ with exactly one element such that $j_1, j_2 \in \{ i,j,k\} \cap \{i',j',k'\}$.

Proof

Suppose that the graph ${\mathbb {AG}}(L)$ is projective and on the contrary that none of the conditions of theorem holds. Without loss of generality, assume that $|U_{12}|=2$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$. If $|U_{23}|=2$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{4,4}$. If $|U_{13}|=|U_{24}|=1$, then $E_3$, one of the listed graphs in [10], is isomorphic to a subgraph of ${\mathbb {AG}}(L)$ (see Fig. 8). In this figure, we have $\{0,a\},I_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{13}\in U_{13}$ and $I_{24}\in U_{24}$.

Fig. 8

$\{0, a\}, I_1 \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\} \in U_5$, $I_{13} \in U_{13} \,\mathrm{and}\, I_{24} \in U_{24}$

If $|U_{23}|=|U_{24}|=1$, then the graph ${\mathbb {AG}}(L)$ contains a subgraph isomorphic to $E_3$, one of the listed graphs in [10]. If $|U_{12}|=|U_{13}|=|U_{14}|=1$, then the graph ${\mathbb {AG}}(L)$ contains a copy of $E_{22}$, one of the listed graphs in [10] (see Fig. 9). In this figure, we have $\{0,a_1\},I_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{12}\in U_{12}$, $I_{13}\in U_{13}$ and $I_{14}\in U_{14}$.

Fig. 9

$\{0, a_1\}, I_1 \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\}\in U_5$, $I_{12} \in U_{12}, I_{13} \in U_{13}\,\mathrm{and}\, I_{14} \in U_{14}$

If $|U_{234}|=2$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$.

If $|U_{234}|=|U_{235}|=|U_{245}|=1$, then the graph ${\mathbb {AG}}(L)$ contains a copy of $E_{20}$, one of the listed graphs in [10] (see Fig. 10). In this figure, we have $\{0,a\},I_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{234}\in U_{234}$, $I_{235}\in U_{235}$ and $I_{245}\in U_{245}$.

Fig. 10

$\{0, a\}, I_1 \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\} \in U_5$, $I_{234} \in U_{234}, I_{235} \in U_{235}\,\mathrm{and}\, I_{245} \in U_{245}$

If $|U_{235}|=|U_{35}|=1$ or $|U_{235}|=|U_{24}|=1$, then the graph ${\mathbb {AG}}(L)$ contains a copy of $E_3$ or $D_3$, two of the listed graphs in [10]. The second case is pictured in Fig. 11. In this figure, we have $\{0,a\},I_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $I_{24}\in U_{24}$ and $I_{235}\in U_{235}$.

Fig. 11

$\{0, a\}, I_1 \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$, $\{0, a_5\} \in U_5$, $I_{24} \in U_{24} \,\mathrm{and}\, I_{235} \in U_{235}$

Obviously, we conclude that in each of the above statements, the graph ${\mathbb {AG}}(L)$ is not projective, which is a contradiction.

Conversely, it is not hard to see that if one of the conditions (i) and (ii) holds, then ${\mathbb {AG}}(L)$ is a projective graph. $\square$

Now, assume that $|\bigcup _{i=1}^5U_i|=7$. If $|U_i|=|U_j|=2$, for some $1\le i \ne j\le 5$, then the contraction of ${\mathbb {AG}}(L)$ is isomorphic to $B_1$, one of the listed graphs in [10] (see Fig. 12). In this figure, we have $\{0,a_1\},I_1\in U_1$, $\{0,a_2\},I_2\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$ and $\{0,a_5\}\in U_5$. In this situation, ${\mathbb {AG}}(L)$ is not projective.

Fig. 12

$\{0, a_1\}, I_1 \in U_1$, $\{0, a_2\}, I_2 \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_4$  and  $\{0, a_5\} \in U_5$

Therefore, it is enough to consider the case that $|U_i| = 3$, for some $1 \le i \le 5$. Without loss of generality, we may assume that $|U_1| = 3$. Hence, we have the following theorem.

Theorem 2.9

Suppose that $|\bigcup _{i=1}^5U_i|=7$ and $|U_1|=3$. Then ${\mathbb {AG}}(L)$ is a projective graph if and only if, for all $2\le i,j,k,l\le 5$, $U_{ijkl}=U_{ijk}=\varnothing$ whenever $U_{ij}=\varnothing$, for $1\le i,j\le 5$.

Proof

First, assume that ${\mathbb {AG}}(L)$ is a projective graph and to the contrary that $U_{ijkl}\ne \varnothing$, $U_{ijk}\ne \varnothing$, for $2 \le i,j,k,l\le 5$ or $U_{ij}\ne \varnothing$, for $1 \le i,j \le 5$. If $U_{ijkl}\ne \varnothing$, for $2 \le i,j,k,l \le 5$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$. Also if $U_{ijk}\ne \varnothing$, for $2\le i,j,k \le 5$, then $K_{4,4}$ is isomorphic to a subgraph of the contraction of ${\mathbb {AG}}(L)$. Finally, if $U_{ij}\ne \varnothing$, for $1\le i,j \le 5$, then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$. Therefore, it is not projective, which is a contradiction.

Conversely, assume that $U_{ijkl}=U_{ijk}=\varnothing$, for all $2\le i,j,k,l\le 5$, and $U_{ij}=\varnothing$, for $1 \le i,j \le 5$. Then one can easily check that the graph ${\mathbb {AG}}(L)$ is isomorphic to Fig. 13, which is projective. In this figure, we have $\{0,a_1\},I_1,J_1\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$ and $\{0,a_5\}\in U_5$. The proof is complete. $\square$

Fig. 13

$\{0, a_1\}, I_1, J_1 \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_{4}$ and  $\{0, a_5\} \in U_5$

Now, by Theorems 2.7, 2.8 and 2.9, we completely characterized the projectivity of ${\mathbb {AG}}(L)$ in the case that $|A(L)| = 5$.

In order to complete the study of the projectivity of ${\mathbb {AG}}(L)$, we assume that $|A(L)|=6$. First, suppose that $|\bigcup _{i=1}^6U_i|\ge 7$. Then ${\mathbb {AG}}(L)$ contains a copy of $B_1$, one of the listed graphs in [10], and so it is not projective. Hence, we may assume that $|\bigcup _{i=1}^6U_i|=6$. Clearly, for all $1\le i\le 6$, we have $|U_i|=1$.

Theorem 2.10

Suppose that $|\bigcup _{i=1}^6U_i|=6$ and $|U_{ijk}|\le 1$ whenever $U_{ij}=\varnothing$, for all $1\le i\ne j\ne k \le 6$. Then ${\mathbb {AG}}(L)$ is a projective graph if and only if one of the following conditions holds:

• (i) If $|U_{ijk}|=1$, then $U_{i'j'k'}=\varnothing$, where $\{i',j',k'\}=\{1,2,\dots ,6\}{\setminus } \{i,j,k\}$.

• (ii) There exist at most two distinct sets $U_{ijk}$ and $U_{ijk'}$ with one element, exactly, where $1 \le i\ne j\ne k\ne k'\le 6$.

• (iii) There exist at most five distinct sets $U_{ijk}$ with one element, exactly, where $1\le i\ne j\ne k\le 6$, such that the intersection of all the sets at their indices has one element, exactly.

Fig. 14

$\{0, a_1\} \in U_1$, $\{0, a_2\} \in U_2$, $\{0, a_3\} \in U_3$, $\{0, a_4\} \in U_{4}$, $\{0, a_5\} \in U_5$, $\{0, a_6\} \in U_6$, $I_{123} \in U_{123},$$I_{156} \in U_{156}, I_{134} \in U_{134}$, $I_{126} \in U_{126}\,\mathrm{and}\, I_{145} \in U_{145}$

Proof

Suppose that the graph ${\mathbb {AG}}(L)$ is projective and on the contrary that none of the conditions of theorem holds. Without loss of generality, assume that $|U_{123}|\ge 2$. Then the contraction of ${\mathbb {AG}}(L)$ contains a copy of $K_{3,5}$. Also if $U_{12}$ is non-empty, then ${\mathbb {AG}}(L)$ contains a copy of $B_1$, one of the listed graphs in [10]. In addition, if $|U_{156}|=|U_{234}|=1$, then $E_{18}$, one of the listed graphs in [10], is isomorphic to a subgraph of ${\mathbb {AG}}(L)$. Moreover, if $|U_{123}|=|U_{124}|=|U_{125}|=1$, then ${\mathbb {AG}}(L)$ contains a copy of $E_{22}$, one of the listed graphs in [10]. In each of the above situations, the graph ${\mathbb {AG}}(L)$ is not projective, which is a contradiction.

Conversely, by considering the embedding of the graph ${\mathbb {AG}}(L)$ in a projective plane in Fig. 14, we conclude that it is projective graph. In this figure, we have $\{0,a_1\}\in U_1$, $\{0,a_2\}\in U_2$, $\{0,a_3\}\in U_3$, $\{0,a_4\}\in U_4$, $\{0,a_5\}\in U_5$, $\{0,a_6\}\in U_6$, $I_{123}\in U_{123}$, $I_{156}\in U_{156}$, $I_{134}\in U_{134}$, $I_{126}\in U_{126}$ and $I_{145}\in U_{145}$. $\square$