Let \(A\) be a commutative ring with nonzero identity and \(n\geq 2\) be a positive integer. With the ring \(R=A\times\cdots\times A\) (\(n\) times), one can associate graphs \(TD(R)\) and \(ZD(R)\) respectively called the total dot product graph and the zero-divisor dot product graph of \(R\). In this paper, we study some topological properties of these two dot product graphs of \(R.\) In particular, it is shown that, the zero-divisor dot product graph \(ZD(R)\) is a projective graph if and only if \(R\) is isomorphic to \(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\) Moreover, we prove that no total dot product graph can be projective. With these observations, we classify all commutative rings for which dot product graphs \(ZD(R)\) and \(TD(R)\) have crosscap two.
The idea of associating a graph to a ring has been started by Beck [8]. In the literature, there are many ways of assigning graphs to commutative rings. In these constructions, graphs are constructed with elements of a ring or a set of substructures of the ring as vertices or and adjacency is defined by using some algebraic conditions on the elements of the vertex set. This motivated the study on the relationship between the algebraic properties of rings and properties of corresponding graphs. Till then, lot of researches [1, 3, 7, 17, 26, 11, 10, 12, 13] have worked on graph structures from various algebraic structures. One can refer [2] for the entire literature on graphs from rings. One of the most important topological properties of a graph is its genus. Finding the genus of a given graph is a difficult problem. The problem of finding the genus of various classes of graphs associated with rings have been attempted by many authors; see [5, 6, 9, 14, 28, 16, 17, 19, 23, 24, 27, 29, 30] etc. The present work extends the efforts revealed through these papers.
Throughout this paper, unless stated otherwise all rings \(R\) are assumed to be commutative rings with identity \(1\neq 0\). Let \(A\) be a commutative ring with nonzero identity, \(Z(A)\) denotes the set of all zero-divisors of \(A\) and \(Z(A)^{*}=Z(A)\setminus\{0\}.\) By the zero-divisor graph of \(A\), we mean the simple undirected graph \(\Gamma(A)\) with \(Z(A)^{*}\) as the vertex set and such that there is an (undirected) edge between two distinct vertices \(a\) and \(b\) if and only if \(ab=0\) [3]. For a commutative ring \(A\) and a positive integer \(n\geq 2,\) let \(R=A\times A\times\cdots\times A\) (\(n\) times). Badawi [7] introduced the total dot product graph of \(R\), denoted by \(TD(R)\) as the simple undirected graph with elements of \(R^*= A^n\setminus\{(0,0,\ldots,0)\}\) as vertices, and two distinct vertices \(x=(x_1,\ldots,x_n)\) and \(y=(y_1,\ldots,y_n)\) \(\in R\) are adjacent if and only if the dot product \(x\cdot y=\sum\limits_{i=1}^nx_iy_i=0\). Then the zero-divisor dot product graph of \(R\) is the induced subgraph \(ZD(R)\) of \(TD(R)\) with vertices \(Z(R)^{*}.\)
We now summarize some notations and concepts from graph theory that are used in what follows. By a graph \(G = (V,E)\), we mean an undirected simple graph with the vertex set \(V\) and the edge set \(E\). A graph in which each pair of distinct vertices is joined by an edge is called a complete graph. We denote the complete graph on \(n\) vertices by \(K_n.\) An \(r\)-partite graph is a graph whose vertex set can be partitioned into \(r\) nonempty-subsets so that no edge has both ends in the same subset. A complete \(r\)-partite graph is an \(r\)-partite graph 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 \(G\) is said to be a tree if it is a connected acyclic graph. A clique in a graph is a set of pairwise adjacent vertices. The clique number of a graph \(G\), written as \(\omega(G),\) is the maximum size of a clique in \(G.\) An independent set in a graph is a set of pairwise nonadjacent vertices. Any undefined notation or terminology is standard, as in [31].
The main objective of topological graph theory is concerning the embeddings graphs in surfaces. It is well-known that every non-orientable compact surface is a connected sum of finite copies of projective planes, see [20]. Let \(\mathbb{N}_k\) denote the surface formed by connected sum of \(k\) projective planes, where \(k\) is a nonnegative integer, that is, \(\mathbb{N}_k\) is an non-orientable surface of crosscap \(k\). A simple graph which is embedded in \(\mathbb{N}_k\) but not in \(\mathbb{N}_{k-1}\) is called a graph of crosscap \(k.\) The crosscap (non-orientable genus) of a graph \(G\) is denoted by \(\overline{\gamma}\left(G\right).\) The graphs \(G\) with \(\overline{\gamma}(G) = 0\) are in fact planar graphs. A graph \(G\) with \(\overline{\gamma}\left(G\right)=1\) is called a projective graph whereas a graph \(G\) with \(\overline{\gamma}\left(G\right)=2\) is called a bi-projective graph. Note that, the surface \(\mathbb{N}_1\) is the projective plane and the surface \(\mathbb{N}_2\) is the Klein bottle. A minor of \(G\) is the graph obtained from \(G\) by contracting edges in \(G\) and isolated vertices in \(G.\) For \(xy\in E(G),\) we denote the contracted edge by the vertex \([x,y].\) It is can be seen that if \(G^{\prime}\) is a minor of \(G\), then \(\overline{\gamma}(G^\prime)\leq\overline{\gamma}(G).\) Further if \(H\) is a subgraph of \(G\) and \(H^{\prime}\) is a minor of \(H\), then we say \(H^{\prime}\) is a minor subgraph of \(G.\) It may be noted that the crosscap of a graph is the sum of crosscaps of its blocks. An embedding of a graph \(G\) on the surface \(S\) is called 2-cell embedding if each connected component of \(S-G\) is homeomorphic to an open disc. For details on the notion of 2-cell embedding of graphs in surfaces, see [4, 14, 22, 24, 32]. It is easy to observe that \(\overline{\gamma}\left(H\right)\leq\overline{\gamma}\left(G\right)\) for all subgraphs \(H\) of \(G.\) For more information, we recommend the interested reader to [21].
We denote the characteristic of a ring \(R\) by \(ch(R).\) As usual, we denote the ring of integers modulo \(n\) by \(\mathbb{Z}_n.\) Further, \(C_n\) denotes the cycle on \(n\) vertices. For any real number \(x\), \(\left\lceil x\right\rceil\) denotes the least integer which is greater than or equal to \(x.\) In figures drawn in this paper, we denote an element \(x=(x_1,x_2,\ldots,x_n)\in A\times A\times\cdots\times A\) by \(x_1x_2\ldots x_n.\) In [7], Badawi established an interplay between commutative rings and corresponding total dot product graphs (resp. zero-divisor dot product graphs). In [25], Selvakumar et al. characterized all commutative rings for which \(TD(R)\) (resp. \(ZD(R)\)) has genus zero or one or two. As a continuation of this work, we aim in this paper on embeddings of \(TD(R)\) (resp. \(ZD(R)\)) in non-orientable compact surfaces. With this as our main goal, we discuss the crosscap of total dot product graphs as well as zero-divisor dot product graphs of commutative rings. In particular, we characterize, up to isomorphism, all commutative rings \(R\) whose \(ZD(R)\) is projective and bi-projective. Further, we show that no projective graph can be realized as a total dot product graph. At last, we classify all commutative rings for which \(TD(R)\) is of crosscap two. In Section 2, we study the clique number of \(TD(R).\) In Section 3, we discuss some basic graph-theoretic properties of \(ZD(R).\) Finally, in Section 3, we investigate zero-divisor dot product graphs as well as total dot product graphs with crosscap one and two.
In this section, first we obtain the clique number of \(TD(R)\). For this purpose, we recall the following lemma in [18].
Lemma 2.1. [18] Let \(R\) be a finite commutative ring and \(\mathfrak{m}\) be a maximal ideal of \(R\). Then there exists some nonzero \(x\in \mathfrak{m}\) such that \(x\mathfrak{m}=0.\)
From Lemma 2.1, whenever \(R\) is a local ring with maximal ideal \(\mathfrak{m}\), then we observe that there exists a nonzero element \(x\in \mathfrak{m}\) such that \(ann(x)=\mathfrak{m}.\) This fact plays a key role in the proof of the following theorem. Actually we characterize all commutative rings \(R\) for which the clique number of the total dot product graph \(TD(R)\) is 3.
Theorem 2.2. Let \(A\) be a finite Artinian commutative ring with identity \(1\) with \(ch(A)\leq 3\). Let \(2\leq n\le \infty\) be an integer, \(R = A\times \cdots\times A=A^n\) and \(TD(R)\) be the total dot product graph of \(R.\) Then \(\omega(TD(R))=3\) if and only if \(R\) is isomorphic to one of the the following 4 rings:
\(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\), \(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\), \(\mathbb{Z}_4\times\mathbb{Z}_4\), \(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}.\)
Proof. Assume that \(\omega(TD(R))\) = \(3\). Suppose \(n\geq 4.\) Then the subgraph of \(TD(R)\) induced by \(\{(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)\}\subseteq V \left(T(R)\right)\) is isomorphic to \(K_4\), which is a contradiction. Hence \(n\leq 4.\)
Suppose that \(n=3.\) Suppose \(|A|\geq 4.\) Let \(a,b, c\in A^{*}.\) If \(ch(A)=2\), then subgraph induced by \(\left\{ (a,a,0),(b,b,0),(c,c,0),(0,0,a)\right\}\) is isomorphic to \(K_4\), a contradiction. If \(ch(A)=3\), then the subgraph induced by \(\left\{ (a,a,a), (b,b,b), (c,c,c), (a,-a,0) \right\}\) is isomorphic to \(K_4,\) a contradiction to \(\omega(TD(R))= 3.\) Hence \(|A|\leq 3\) and \(A\) is a field. From this we get that \(A\cong\mathbb{Z}_2\) or \(A\cong\mathbb{Z}_3\) and hence \(R\) is either \(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\) or \(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3.\)
Suppose that \(n=2.\) Let us assume that \(A\) is a non-local ring. Since \(A\) is Artinian, \(A=A_1\times\cdots\times A_m, (m\geq 2)\), where each \(A_i,(1\leq i\leq m)\) is a local ring. From this we get that \(R\cong A_1^{2}\times\cdots\times A_m^2.\) Now the subgraph of \(TD(R)\) induced by vertices \((1,0,0,0,0,\ldots,0), (0,1,0,0,0,\ldots,0), (0,0,1,0,0,\ldots,0)\) and \((0,0,0,1,0,\ldots,0)\) forms \(K_4\subseteq TD(R)\). This gives a contradiction. Hence \(A\) must be a local ring. Let \(\mathfrak{m}\) be a maximal ideal of \(A.\) If \(|\mathfrak{m}^{*}|\geq 2,\) then there exists \(a,b\in \mathfrak{m}^{*}\) such that \(ab=0\) and \(ann(a)=\mathfrak{m}\) (see Lemma 2.1). Now, the subgraph of \(TD(R)\) induced by \(\{(a,a), (b,0), (0,b),(a,0)\}\) is isomorphic to \(K_4\), a contradiction. Thus \(|\mathfrak{m}^{*}|=1\) and hence \(A\cong\mathbb{Z}_4\) or \(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}.\) From this \(R\) is either \(\mathbb{Z}_4\times\mathbb{Z}_4\) or \(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle} \times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}.\)
Conversely, assume that \(R\cong\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2.\) One can check that \(TD\left(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\right)\) contains \(K_3\) as a maximal complete subgraph and hence \(\omega(TD\left(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\right))=3\)
Now let us assume that \(R\cong\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\). Let \(V_1\), \(V_2\) and \(V_3\) be subsets of the vertex set of \(TD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right)\) as given below. \[\begin{aligned} V_1=&\left\{(a,b,c): a,b,c \in\mathbb{Z}_3 \text{ and exactly one of $a,b,c$ is nonzero}\right\},\\ V_2=&\left\{(x,y,z): x,y,z \in\mathbb{Z}_3 \text{ and exactly two of $x,y,z$ are nonzero}\right\},\\ V_3=&\left\{(u,v,w): u,v,w \in\mathbb{Z}_3^{*} \right\}. \end{aligned}\]
It is clear that \(V\left(TD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right)\right)=V_1\cup V_2\cup V_3\) and \(V_1\cap V_2\cap V_3=\phi.\) Observe that the subgraph induced by \(V_1\) contains 8 cliques of \(TD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right).\) The subgraph induced by \(V_2\) is isomorphic to 3 copies of \(C_2\) and the graph induced by \(V_3\) is isomorphic to 4 copies of \(K_2.\) It is easy to check that no vertex in \(V_2\) and \(V_3\) can be adjacent to all other vertices of \(V_1.\) It follows that \(\omega\left(TD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right)\right)=3.\)
Assume that \(R\cong\mathbb{Z}_4\times\mathbb{Z}_4.\) Consider the vertex subsets \(V_1,\dots,V_6\) of the vertex set of \(TD\left(\mathbb{Z}_4\times\mathbb{Z}_4\right)\) given by \(V_1=\left\{(0,2),(2,2),(2,0)\right\}\), \(V_2=\left\{(1,1),(1,3),(2,2)\right\}\), \(V_3=\left\{(1,1),(3,1),(2,2)\right\}\), \(V_4=\left\{(1,3),(2,2),(3,3)\right\}\), \(V_5=\left\{(0,1),(1,0),(0,3),(3,0)\right\}\) and \(V_6=\left\{(1,2),(2,1),(2,3),(3,2)\right\}.\) Then, for \(1\leq i\leq 4\), the subgraph of \(TD\left(\mathbb{Z}_4\times\mathbb{Z}_4\right)\) induced by \(V_i\) is isomorphic to \(K_3\) and, for \(5\leq j\leq 6\), the subgraph induced of \(TD\left(\mathbb{Z}_4\times\mathbb{Z}_4\right)\) induced by \(V_j\) is isomorphic to \(C_4.\) For \(1\leq i,j\leq 6\) and \(i\neq j\), no vertex in \(V_i\setminus V_j\) is adjacent to all other vertices in \(V_j.\) So we conclude that \(\omega\left(TD\left(\mathbb{Z}_4\times\mathbb{Z}_4\right)\right)=3.\)
One can prove that \(TD\left(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\right)\) has clique number 3 in a similar way. ◻
Now, we study certain graph theoretical aspects of \(ZD(R)\). At first, we characterize all finite commutative rings \(R\) for which zero-divisor dot product graphs are split graphs. Recall that a graph \(G\) is a split graph if its vertex set is the disjoint union of two sets \(K\) and \(S\) where \(K\) induces a complete subgraph and \(S\) is an independent set. Here we recall a characterization for split graphs and the same is given below.
Lemma 2.3. [15] A graph \(G\) is a split graph if and only if it does not have an induced subgraph isomorphic to \(C_4\) or \(C_5\) or two copies of \(K_2.\)
We are now prepared to classify the class of all finite commutative rings \(R\) whose \(ZD(R)\) to be a split graph in the following theorem.
Theorem 2.4. Let \(A\) be a commutative ring with identity 1, \(2\leq n<\infty\) be an integer and \(R=A\times\cdots\times A=A^n.\) Then \(ZD(R)\) is a split graph if and only if \(R\) is isomorphic to \(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\) or \(\mathbb{Z}_2\times\mathbb{Z}_2.\)
Proof. Assume that \(ZD(R)\) is a split graph. Suppose that \(n\geq 4\). Then the vertices \((1,1,0,0,0,\ldots,0)\), \((0,0,1,1,0,\ldots,0)\), \((1,0,1,0,0,\cdots,0)\) and \((0,1,0,1,0,\ldots,0)\in V(ZD(R))\) induce a subgraph of \(ZD(R)\) isomorphic to two copies of \(K_2.\) Here we get contradiction through Lemma 2.3. Hence \(n=2\) or \(3\).
Case 1. \(n=3\). Suppose that \(|A|\geq 3\). If \(ch(A)\neq 2\), then the subgraph of \(ZD(R)\) induced by the set \(\left\{(1,-1,0),(1,1,0),(1,0,0),(0,1,0)\right\}\) is isomorphic to \(2K_2\) which is a contradiction to Lemma 2.3. On the other hand, assume that \(ch(A)=2\). As \(|A|\geq3\), there exists \(a\in A^{*}\) such that \(a\neq 1.\) Now, the subgraph of \(ZD(R)\) induced by \(\left\{(1,a,0),(a,1,0),(1,0,0),(0,1,0)\right\}\) is isomorphic to 2 copies of \(K_2,\) again a contradiction to Lemma 2.3. Thus \(|A|=2\) and hence \(A\) is ring isomorphic to \(\mathbb{Z}_2\). This gives that \(R\cong\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2.\)
Case 2. \(n=2.\) Let us assume that \(|A|\geq 3\). If \(ch(A)\neq 2\), then \(1\neq -1.\) This causes that the subset \(\{(1,1),(1,-1),(-1,-1),(-1,1)\}\subseteq ZD(R)\) induces a subgraph isomorphic to \(C_4,\) a contradiction. Suppose that \(ch(A)=2.\) Since \(|A|\geq 3\), consider an element \(a\in A^{*}\) such that \(a\neq 1.\) Then vertex subset \(\{(1,a),(a,1),(1,0), (0,1)\}\) of \(ZD(R)\) induces 2 copies of \(K_2,\) a contradiction. So we conclude that \(A\cong\mathbb{Z}_2.\) This gives that \(R\cong\mathbb{Z}_2\times\mathbb{Z}_2.\)
For other direction, when \(R\cong\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\), we see that the subset of vertices \(\{(1,0,0),(0,1,0),(0,0,1)\}\) induces a clique whereas \(\{(0,1,1),(1,0,1),(1,1,0)\}\) is an independent set of \(ZD(R)\). Therefore, \(ZD(R)\) is a split graph. One can check that \(ZD\left(\mathbb{Z}_2\times\mathbb{Z}_2\right)\) is obviously a split graph. ◻
Next, we deal with the unicyclic property of \(ZD(R)\) in the following theorem.
Theorem 2.5. Let \(A\) be a commutative ring with identity, \(2\leq n<\infty\) be an integer and \(R=A\times\cdots\times A=A^n.\) Then \(ZD(R)\) is unicyclic if and only if \(R\) is isomorphic either \(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\) or \(\mathbb{Z}_3\times\mathbb{Z}_3.\)
Proof. Assume that \(ZD(R)\) is unicyclic. Suppose that \(n\geq 4.\) Consider the vertices
\(x_1=(1, 0, 0, 0, 0, \ldots,0)\),
\(x_2=(0,1,0,0,0,\ldots,0)\), \(x_3=(0,0,1,0,0,\ldots,0)\) and \(x_4=(0,0,0,1,0,\ldots,0)\) of \(ZD(R)\). Then \(x_i\cdot x_j=0\) for \(i\neq j\) and therefore \(ZD(R)\) is isomorphic to \(K_4.\) This contradicts the hypothesis that
\(ZD(R)\) is unicyclic. Hence \(n=2\) or \(3\).
First, assume that \(n=3\). Suppose that \(|A|\geq 3\). Let \(a,b\in A^{*}\). Observe that \((a,0,0)-(0,a,0)-(0,0,a)-(a,0,0)\) and \((b,0,0)-(0,b,0)-(0,0,b)-(b,0,0)\) are two distinct cycles of \(ZD(R)\), a contradiction. Thus \(|A|=2\) and so \(A\cong\mathbb{Z}_2\). In this case \(R\cong \mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2.\)
Next, let us assume that \(n=2\). If \(|A|\geq 4,\) one can select six vertices such that they induce a subgraph of \(ZD(R)\) which is isomorphic to \(K_{3,3},\) a contradiction. Thus \(|A|= 2\) or \(3\). If \(|A|=2\), it is easy to observe that \(ZD(R)\cong K_2\), a contradiction. Thus \(|A|=3\) and hence \(A\) is ring isomorphic to \(\mathbb{Z}_3.\) In this case \(R\cong \mathbb{Z}_3\times\mathbb{Z}_3.\)
Converse follows from Figure 1.
Now, we obtain a characterization for \(ZD(R)\) to be a tree.
Theorem 2.6. Let \(A\) be a commutative ring with identity, \(2\leq n<\infty\) be an integer and \(R=A\times\cdots\times A=A^n.\) Then \(ZD(R)\) is a tree if and only if \(R\) is isomorphic to \(\mathbb{Z}_2\times\mathbb{Z}_2\).
Proof. Assume that \(ZD(R)\) is a tree. Suppose that \(n\geq 3.\) Observe that \((1,0,0,0, \ldots,0)-(0,1,0,0,\ldots,0)-(0,0,1,0,\ldots,0)-(1,0,0,0,\ldots,0)\) is a cycle in \(ZD(R),\) a contradiction to the assumption. Thus \(n=2\). Suppose that \(|A|\geq 3.\) Let \(a,b\in A^{*}.\) If \(ab=0\), then \((0,a)-(a,0)-(b,0)-(0,a)\) is a cycle of length \(3\) in \(ZD(R),\) a contracition. On the other hand when \(ab\neq 0\), \((0,a)-(a,0)-(0,b)-(b,0)-(0,a)\) is a cycle of \(ZD(R)\) of length 4 in \(ZD(R),\) which is again a contradiction. Hence \(|A|=2\) and therefore \(R\) is ring isomorphic to \(\mathbb{Z}_2\times\mathbb{Z}_2\).
The converse is straightforward. ◻
In what follows, we determine the isomorphism class of all commutative rings \(R\) whose zero-divisor dot product graphs \(ZD(R)\) are of crosscap one and two. Furthermore, we obtain a characterization of all rings for which total dot product graphs are bi-projective graphs. To accomplish this, we use the insertion and deletion argument in an embedding of \(TD(R)\) on the non-orientable surface. First, let us state the following results on the non-orientable genus of a graph.
Proposition 3.1. [21, Ringel and Youngs] Let \(m,n\geq2\) be positive integers. Then
\(\overline{\gamma}\left(K_{m,n}\right)=\left\lceil \frac{(m-2)(n-2)}{2}\right\rceil.\)
In particular, \(\overline{\gamma}(K_{3,3})=\overline{\gamma}(K_{3,4})=1.\)
Lemma 3.2. [21] Let \(G\) be a connected graph with \(n\geq 3\) vertices and \(q\) edges. If \(G\) contains no cycle of length \(3\), then \(\overline{\gamma}(G)\geq \left\lceil \frac{q}{2}-n+2\right\rceil.\)
Lemma 3.3. [21, Euler’s formula] Let \(\phi:G\rightarrow \mathbb{N}_k\) be a \(2-\)cell embedding of a connected graph \(G\) to the non-orientable surface \(\mathbb{N}_k\). Then \(v-e+f=2-k,\) where \(v,~e\) and \(f\) are the number of vertices, edges, and faces that \(\phi(G)\) has respectively, and \(k\) is the crosscap of \(\mathbb{N}_k.\)
Next, we recall the following results about the planarity of \(ZD(R)\) and \(TD(R)\) which is essential to examine their embeddings on the projective plane and the Klein bottle.
Theorem 3.4. [25, Theorem 3.4] Let \(A\) be a commutative ring with identity, \(2\leq n <\infty\) be an integer, and \(R = A\times \cdots\times A=A^n.\) Then \(TD(R)\) is planar if and only if \(R\) is isomorphic to one of rings: \(\mathbb{Z}_2\times\mathbb{Z}_2\), \(\mathbb{Z}_3\times\mathbb{Z}_3\), \(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2.\)
Corollary 3.5. [25, Corollary 3.5] Let \(A\) be a commutative ring with identity, \(2\leq n <\infty\) be an integer, and \(R = A\times \cdots\times A=A^n\) \((n\) times\()\). Then \(ZD(R)\) is planar if and only if \(R\) is isomorphic to one of the rings: \(\mathbb{Z}_2\times\mathbb{Z}_2\), \(\mathbb{Z}_3\times\mathbb{Z}_3\), \(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2.\)
Now we are ready to prove the main theorem of this section. First of all, we have the following lemma which will be repeatedly used in the sequel of this section.
Lemma 3.6. Let \(R\cong\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\) or \(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3.\) Then \(\overline{\gamma}(ZD(R))\geq3.\)
Proof. Consider \(R\cong\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\). By contracting the edges \((1,1,0,0)-(0,0,1,1)\), \((1,0,1,0)-(0,1,0,1)\), and \((1,0,0,1)-(0,1,1,0)\), we obtain a minor of the graph \(ZD\left(\mathbb{Z}_2\times\right.\left.\mathbb{Z}_2\times \mathbb{Z}_2\times\mathbb{Z}_2\right)\) as in Figure 2. This minor has 11 vertices and 23 edges and its girth is 4. Substituting these in Proposition 3.1, we get that the crosscap of the minor is at least \(\left\lceil \frac{5}{2}\right\rceil\), and hence \(\geq 3\).
Let \(G=ZD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right).\) Consider the vertices \(v_1=\left(1,0,0\right)\), \(v_2=\left(2,0,0\right)\), \(v_3=\left(0,1,0\right)\), \(v_4=\left(0,2,0\right)\), \(v_5=\left(0,0,1\right)\), \(v_6=\left(0,0,2\right)\), \(v_7=\left(0,1,1\right)\), \(v_8=\left(0,1,2\right)\), \(v_9=\left(0,2,1\right)\), \(v_{10}=\left(0,2,2\right)\), \(v_{11}=\left(1,0,1\right)\), \(v_{12}=\left(1,0,2\right)\), \(v_{13}=\left(2,0,1\right)\), \(v_{14}=\left(2,0,2\right)\), \(v_{15}=\left(1,1,0\right)\), \(v_{16}=\left(1,2,0\right)\), \(v_{17}=\left(2,1,0\right)\) and \(v_{18}=\left(2,2,0\right)\in V\left(G\right).\)
Let \(G^{\prime}=G-\{v_1v_8,v_1v_9,v_2v_7,v_2v_{10},v_5v_{16},v_5v_{17},v_6v_{15},v_6v_{18}, v_1v_3,v_2v_3,v_2v_5, v_2v_6,v_4v_5,v_4v_6 \}\) and \(G^{\prime\prime}=G^{\prime}-\left\{v_{11},v_{12},v_{13},v_{14}\right\}.\) Then it is easy to see that \(G^{\prime\prime}\) contains two copies of \(K_{3,3}.\) By Proposition 3.1, \(\overline{\gamma}(G^{\prime\prime})\geq 2.\) If \(\overline{\gamma}(G^{\prime\prime})\geq 3\), then trivially \(\overline{\gamma}(G)\geq 3.\) So let us consider the case that \(\overline{\gamma}(G^{\prime\prime})=2.\)
Now, we proceed to prove \(\overline{\gamma}(G)\geq 3\) by deletion and insertion method. Suppose that \(\overline{\gamma}(G)=2.\) Since \(G^{\prime\prime}\subseteq G^{\prime}\subseteq G,\) \(\overline{\gamma}(G^{\prime})=2.\) Note that \(\left|V\left(G^{\prime}\right)\right|=18\), \(\left|E\left(G^{\prime}\right)\right|=34\), \(\left|V\left(G^{\prime\prime}\right)\right|=14\) and \(\left|E\left(G^{\prime}\right)\right|=22.\) By Lemma 3.3, the 2-cell embedding of \(G^{\prime}\) on the non-orientable surface \(\mathbb{N}_2\) must contain 16 faces.
Fix a representation of \(G^{\prime}\) and let \(\left\{F_1^{\prime},\ldots,F_{16}^{\prime}\right\}\) be the set of faces corresponding to this representation. Since \(\overline{\gamma}(G^{\prime\prime})=2,\) by applying Lemma 3.3, we see that \(G^{\prime\prime}\) has 8 faces in a drawing of \(G^{\prime\prime}\) on \(\mathbb{N}_2.\) Let \(F_1^{\prime\prime},\ldots, F_8^{\prime\prime}\) be the faces of \(G^{\prime\prime}\) obtained by deleting \(v_{11},v_{12},v_{13},v_{14}\) and all the edges incident with \(v_{11},v_{12},v_{13}\) and \(v_{14}\) from the representation of \(G^{\prime}.\) Again \(\left\{F_1^{\prime},\ldots,F_{16}^{\prime}\right\}\) can be recovered by inserting \(v_{11},v_{12},v_{13}\) and \(v_{14}\) into the representation corresponding to \(\left\{F_1^{\prime\prime},\ldots, F_8^{\prime\prime}\right\}\). Note that \(v_3v_i\) and \(v_3v_i\in E\left(G^{\prime}\right)\) for \(11\leq i\leq 14\). Let \(F_m^{\prime\prime}\) be any face of \(G^{\prime\prime}\) containing vertices \(v_3\) and \(v_4\) as boundary vertices during the recovery process from \(G^{\prime\prime}\) to \(G^{\prime}.\) Since \(v_{11},v_{12},v_{13}\) and \(v_{14}\) form a cycle of length 4 in \(G^{\prime}\), we shall have an edge crossing if \(v_{11},v_{12},v_{13}\) and \(v_{14}\) lie on different faces of \(G^{\prime\prime}\). Hence \(v_{11},v_{12},v_{13}\) and \(v_{14}\) must be inserted to the same face of \(F_m^{\prime\prime}\) of \(G^{\prime\prime}\).
Let \(e_1=v_{11}v_{12}\), \(e_2=v_{11}v_{13}\), \(e_3=v_{13}v_{14}\), \(e_4=v_{12}v_{14}\), \(e_5=v_{3}v_{11}\), \(e_6=v_{3}v_{12}\), \(e_7=v_{4}v_{13}\), \(e_8=v_{4}v_{14}\), \(e_9=v_{3}v_{13}\), \(e_{10}=v_{3}v_{14}\), \(e_{11}=v_{4}v_{11}\) and \(e_{12}=v_{4}v_{12}.\) Then we obtain Figure 3 after inserting \(e_1,\ldots,e_8\) into \(F_m^{\prime\prime}.\) However from Figure 3, one cannot insert \(e_9, e_{10},e_{11}\) and \(e_{12}\) into \(F_m^{\prime\prime}\) without crossings. Hence it is concluded that \(\overline{\gamma}(G)\geq 3.\) ◻
Now we are in position to determine a commutative ring for which \(ZD\left(R\right)\) has crosscap one.
Theorem 3.7. Let \(A\) be a commutative ring with identity, \(2\leq n <\infty\) be an integer, and \(R = A\times \cdots\times A=A^n.\) Then \(ZD(R)\) is a projective graph if and only if \(R\) is ring isomorphic to \(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\)
Proof. Assume that \(ZD(R)\) is projective. Suppose that \(n\geq 4\). By contracting the edges \((1,1,0,0)-(0,0,1,1)\), \((1,0,1,0)-(0,1,0,1)\), and \((1,0,0,1)-(0,1,1,0)\) in \(ZD(R),\) we obtain a minor of the graph \(ZD\left(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\right)\) as in Figure 2. This minor has 11 vertices and 23 edges and its girth is 4. Substituting these in Proposition 3.1, we get that the crosscap of the minor is at least \(\left\lceil \frac{5}{2}\right\rceil\), and hence \(\geq 3\). From this, crosscap of \(\overline{\gamma}(ZD(R))\geq 3\) which is a contradiction. Hence \(n=2\) or \(3.\)
Suppose that \(n=3.\) If \(|A|=2\), then Corollary 3.5 implies \(ZD(R)\) is a planar graph. When \(|A|\geq 3,\) \(ZD(R)\) contains a subgraph isomorphic to \(ZD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right)\) and so by Lemma 3.6, \(\overline{\gamma}(ZD(R))\geq 3,\) which is a contradiction to the assumption that \(ZD(R)\) is projective.
Now let us assume that \(n=2.\) If \(|A|=2\) or \(3\), by Corollary 3.5 \(ZD(R)\) is planar, which is a contradiction. Hence \(|A|\geq 4.\) If \(|A|\geq 5\), then one can realize that there exists a subgraph of \(ZD(R)\) which is isomorphic to \(K_{4,4}\). By Proposition 3.1, \(ZD(R)\) cannot be a projective graph. Hence \(|A|=4\) and hence \(A\) would be ring isomorphic to one of the rings: \(\mathbb{Z}_2\times\mathbb{Z}_2, \mathbb{Z}_4, \frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}, \frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\)
When \(A=\mathbb{Z}_2\times\mathbb{Z}_2\), by Lemma 3.6, we get \(\overline{\gamma}(ZD(R))\geq 2.\)
Since \(ZD(\mathbb{Z}_4\times\mathbb{Z}_4)\cong ZD\left(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\right)\), it is enough to consider \(R\cong\mathbb{Z}_4\times\mathbb{Z}_4.\) Let \(u_1=(0,1), u_2=(0,2), u_3=(0,3), v_1=(1,0), v_2=(2,0), v_3=(3,0), w_1=(1,2), w_2=(2,1)\), \(w_3=(2,3), w_4=(3,2)\) and \(z=(2,2)\in V(ZD(R)).\) Observe that \(u_i.v_j=0\) for every \(i,j,\) so that \(K_{3,3}\subseteq ZD(R).\) Therefore \(\overline{\gamma}(ZD(R))\geq \overline{\gamma}(K_{3,3})=1.\)
Consider \(G=ZD(R),\) \(G^{\prime}=G-\{z\}\) and \(G^{\prime\prime}=G^{\prime}-\{w_1,w_2,w_3,w_4\}.\) Then it is easy to see that \(G^{\prime\prime}\cong K_{3,3}.\) Suppose that \(\overline{\gamma}(G)=1.\) Since \(1=\overline{\gamma}(G^{\prime\prime})\leq\overline{\gamma}(G^{\prime})\leq\overline{\gamma}(G)=1\) we get that \(\overline{\gamma}(G^{\prime})=1.\) Let \(V(G^{\prime})=\{u_1,u_2,u_3,v_1,v_2,v_3,w_1,w_2,w_3\}.\) Then \(E(G^{\prime})=\{u_iv_j:~1\leq i,j\leq 3\}\cup\{w_3w_4,w_2w_4,w_2w_1,w_1w_3,u_2w_4,u_2w_6,v_2w_2,v_2w_3\}.\) Since \(\left|V(G^{\prime})\right|=9\) and \(\left|E(G^{\prime})\right|=17\), by Lemma 3.3, any \(2\)-cell embedding of \(G^{\prime}\) on \(\mathbb{N}_1\) has \(9\) faces. Let \(\{F_1^{\prime},\ldots,F_9^{\prime}\}\) be the faces of a representation of \(G^{\prime}\) in \(\mathbb{N}_1.\) We observe that \(G^{\prime\prime}\cong K_{3,3}\) and hence this graph has \(4\) faces whose boundaries are three \(4\)-cycles and one \(6\)-cycle. Let \(F_1^{\prime\prime},\ldots,F_4^{\prime\prime}\) be the faces of \(G^{\prime\prime}\) obtained by deleting \(w_1,w_2,w_3,w_4\) and all the edges incident with \(w_1,w_2,w_3,w_4\) from the representation of \(G^{\prime}.\) Then \(\{F_1^{\prime},\ldots,F_9^{\prime}\}\) can be recovered by inserting \(w_1,w_2,w_3,w_4\) and all the edges incident with \(w_1,w_2,w_3,w_4\) into the representation corresponding to \(\{F_1^{\prime},\ldots,F_9^{\prime}\}.\)
Let \(F_m^{\prime\prime}\) denote the face of \(G^{\prime\prime}\) into which \(w_1,w_2,w_3\) and \(w_4\) are inserted during the recovering process from \(G^{\prime\prime}\) to \(G^{\prime}.\) We note that the vertices \(w_1,w_2,w_3\) and \(w_4\) form a cycle of length \(4\) in \(G^{\prime}.\) If \(w_1,w_2,w_3\) and \(w_4\) lie on different faces of \(2\)-cell embedding of \(G^{\prime}\) in \(\mathbb{N}_1,\) then there shall be an edge crossing. Hence \(w_1,w_2,w_3\) and \(w_4\) should be inserted in the same face \(F_m\) of \(G^{\prime\prime}\) to avoid crossings. Since \(u_2w_1,u_2w_4\in E(G^{\prime})\) and \(v_2w_2,v_2w_3\in E(G^{\prime})\), \(u_2\) and \(v_2\) are boundary vertices of the face \(F_m^{\prime\prime}.\) Let \(e_1=u_2w_4\), \(e_2=v_2w_2\), \(e_3=u_2w_1\) and \(e_4=v_2w_3.\) After inserting \(w_1,w_2,w_3,w_4\) and \(e_1,e_2\) into \(F_m^{\prime\prime}\), we obtain Figure 4 as shown below. However it is easy to see from Figure 4, there is no way to insert \(e_3\) and \(e_4\) into \(F_m^{\prime\prime}\) without crossings, a contradiction. Therefore, we conclude that \(\overline{\gamma}(G)\geq 2.\) Hence \(A\) is ring isomorphic to the field \(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\) Hence \(R\cong \frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times \frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\)
As \(ZD\left(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\right)\) is isomorphic to \(K_{3,3}\), the converse follows directly from Proposition 3.1. ◻
Now, we classify all commutative rings \(R\) whose \(ZD(R)\) is of crosscap two (bi-projective graph).
Theorem 3.8. Let \(A\) be a commutative ring with identity, \(2\leq n <\infty\) be an integer, and \(R = A\times \cdots\times A=A^n.\) Then \(ZD(R)\) is a bi-projective graph if and only if \(R\) is ring isomorphic to one of the \(3\) rings: \(\mathbb{Z}_4\times\mathbb{Z}_4\), \(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\), \(\mathbb{Z}_5\times\mathbb{Z}_5.\)
Proof. Assume that \(ZD(R)\) is a bi-projective graph. i.e., \(\overline{\gamma}\left(ZD(R)\right)=2.\) If \(n\geq 4\), then \(ZD\left(R\right)\) contains a subgraph isomorphic to \(ZD\left(\mathbb{Z}_2^4\right)\). By Lemma 3.6, \(\overline{\gamma}\left(ZD(R)\right)\geq 3,\) a contradiction. Hence \(n=2\) or 3.
Suppose that \(n=2.\) If \(|A|=2,\) by Corollary 3.5, \(ZD\left(R\right)\) is planar which contradicts the assumption. If \(\left|A\right|\geq 3\), then \(ZD\left(R\right)\) has a subgraph isomorphic to \(ZD\left(\mathbb{Z}_3\times\mathbb{Z}_3\times\mathbb{Z}_3\right).\) By Lemma 3.4, we see that \(\overline{\gamma}\left(ZD(R)\right)\geq 3.\) again a contradiction.
Suppose that \(n=2\) and \(\left|A\right|\geq 6.\) It can be shown that \(ZD\left(R\right)\) contains \(K_{5,5}\) as its subgraph. By Proposition 3.1, the crosscap of \(ZD(R)\) is at least 5, which is a contradiction. Hence \(\left|A\right|\) must be 4 and 5. If \(\left|A\right|=4,\) then \(R\) is isomorphic to following 4 rings:
\(\mathbb{Z}_4\times\mathbb{Z}_4\), \(\left(\mathbb{Z}_2\times\mathbb{Z}_2\right)\times \left(\mathbb{Z}_2\times\mathbb{Z}_2\right)\),\(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\), \(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\)
By Lemma 3.6, the crosscap of \(ZD\left(\mathbb{Z}_2^4\right)\) is at least
3 and by Theorem 3.7,
\(ZD\left(\frac{Z_2\left[x\right]}{\left\langle
x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle
x^2+x+1\right\rangle}\right)\) is a projective graph. Hence \(R\) is isomorphic to \(\mathbb{Z}_4\times\mathbb{Z}_4\) or \(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle
x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle
x^2\right\rangle}.\) When \(\left|A\right|=5\), \(R\) is isomorphic to \(\mathbb{Z}_5\times\mathbb{Z}_5.\)
Converse follows from the embeddings provided in Figure 5.
Next, we turn our attention to embeddings of \(TD(R)\) in non-orientable surfaces. At first, we show that there does not exist a projective total dot product graph for any commutative ring \(R\) in the following theorem.
Theorem 3.9. Let \(A\) be a commutative ring with identity, \(2\leq n <\infty\) be an integer, and \(R = A\times \cdots\times A=A^n.\) If \(TD(R)\) is non-planar, then \(\overline{\gamma}(TD(R))>1\).
Proof. We know that \(ZD(R)\) is a subgraph of \(TD(R).\) Hence by Theorem 3.4 and Theorem 3.7 it is enough to consider case that \(n=2\) and \(|A|\geq5.\) When \(|A|\geq 6\), \(TD(R)\) contains a subgraph which is isomorphic to \(K_{5,5}\) and hence by Proposition 3.1, \(\overline{\gamma}(TD(R))\geq5.\) If \(|A|=5\), then \(A\) is ring isomorphic to \(\mathbb{Z}_5\) and then \(R\cong\mathbb{Z}_5\times\mathbb{Z}_5.\) One can check that \(TD(\mathbb{Z}_5\times\mathbb{Z}_5)\supseteq K_{4,4}.\) According to Proposition 3.1\(, \overline{\gamma}(TD(R))\geq2.\) This completes the proof. ◻
Now, we have a characterization of commutative rings \(R\) whose \(ZD(R)\) is of crosscap two.
Theorem 3.10. Let \(A\) be a commutative ring with identity, \(2\leq n <\infty\) be an integer, and \(R = A\times \cdots\times A=A^n.\) Then \(\overline{\gamma}\left(TD(R)\right)=2\) if and only if \(R\) is ring isomorphic to one of the \(3\) rings: \[\mathbb{Z}_4\times\mathbb{Z}_4, \frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}, \frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\]
Proof. Since \(ZD(R)\) is a subgraph of \(TD(R)\), as in the proof of the Theorem 3.8, it is enough to consider the case that \(n=2\) and \(|A|= 4\) or \(5.\) Consider \(\left|A\right|=5.\) Then \(R\cong\mathbb{Z}_5\times\mathbb{Z}_5.\) One can easily check that \(TD\left(\mathbb{Z}_5\times\mathbb{Z}_5\right)\) contains a copy of \(K_{4,4}\) together with a copy of \(K_{3,3}.\) By Proposition 3.1, \(\overline{\gamma}\left(TD(R)\right)\geq 3,\) a contradiction. Consider \(\left|A\right|=4.\) Then \(A\) is isomorphic to one of the following rings: \[\mathbb{Z}_2\times\mathbb{Z}_2, \mathbb{Z}_4, \frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}, \frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}.\]
Since \(R=A\times A\), we get that \(ZD\left(\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\right)\subseteq TD(R)\) when \(A\cong \mathbb{Z}_2\times\mathbb{Z}_2\). As \(ZD(R)\) is a subgraph of \(TD(R)\), by applying Example 3.6, \(\overline{\gamma}\left(TD(R)\right)\geq3,\) a contradiction. Hence \(R\) is isomorphic to the rings given in statement of Theorem 3.10.
Conversely, since \(TD\left(\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\times\frac{Z_2\left[x\right]}{\left\langle x^2+x+1\right\rangle}\right)\) contains 2 copies of \(K_{3,3}\) and \(C_3\) shown in Figure 6 and by applying Proposition 3.1, we directly show that its crosscap is 2. Also the embedding of \(TD\left(\mathbb{Z}_4\times\mathbb{Z}_4\right)\) and \(TD\left(\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\times\frac{\mathbb{Z}_2\left[x\right]}{\left\langle x^2\right\rangle}\right)\) is given in Figure 7.
The research of V. Ramanathan is supported by Dr. D.S. Kothari Postdoctoral Fellowship (No.F.4-2/2006 (BSR)/MA/17-18/0045), University Grants Commission, Government of India. For this research work, T. Tamizh Chelvam is supported by CSIR Emeritus Scientist Scheme of Council of Scientific and Industrial Research (No.21(1123)/20/EMR-II), Government of India.