For a connected graph \(G=(V,E)\) of order at least two, a \(u-v\) chordless path in \(G\) is a \(monophonic\) \(path\). The edge monophonic closed interval \(I_{em}[u,v]\) consists of all the edges lying on some \(u-v\) monophonic path. For \(S'\subseteq V(G),\) the set \(I_{em}[S']\) is the union of all sets \(I_{em}[u,v]\) for \(u,v\in S'.\) A set \(S'\) of vertices in \(G\) is called an \(edge\) \(monophonic\) \(set\) of \(G\) if \(I_{em}[S']=E(G).\) The edge monophonic number \({m_1}(G)\) of G is the minimum cardinality of its edge monophonic sets of \(G\). In this paper the monophonic number and the edge monophonic number of corona product graphs are obtained. Exact values are determined for several classes of corona product graphs.
By a \(graph\) \(G = \left(V, E\right)\) we mean a finite simple undirected connected graph. The \(order\) and \(size\) of G are denoted by \(p\) and \(q\), respectively. The best-known metric space in Graph Theory is (\(V(G)\),\(d_G\)), where \(V(G)\) is the vertex set of a graph \(G\) and the \(distance\) \(d_G(u, v)\) between two vertices \(u\) and \(v\) is the minimum number of edges lies on a \(u-v\) path. The \(open\) \(neighborhood\) of a vertex \(v\) is the set \(N(v)\) consisting of all the vertices \(u\) which are adjacent with \(v\). A vertex \(v\) is called an extreme vertex or a simplicial vertex of \(G\) if the subgraph induced by \(N(v)\) is complete. The \(degree\) of a vertex \(v\) in a graph \(G,\) denoted by \(deg(v),\) is the number of edges incident with \(v\). The \(maximum\) \(degree\) of \(G\), denoted by \(\Delta (G)\), is given by \(\Delta(G) = max\left\{deg(v) : v \in V(G)\right\}\). A vertex \(v\) is a semi-extreme vertex or a semi-simplicial vertex of \(G\) if the subgraph induced by its open neighborhood \(N(v)\) has a vertex with degree \(|N(v)|-1\). Every extreme vertex of \(G\) is a semi-extreme vertex of \(G,\) the converse need not be true. If \(G\) has order \(n\), then the corona product of \(G\) with the graph \(H\), denoted by \(G\odot H\), is the graph obtained by taking one copy of \(G\) and \(n\)-copies of \(H\) and joining the \(i^{\rm th}\) vertex of \(G\) with every vertex in the \(i^{\rm th}\) copy of \(H\).
A \(chord\) of a path \(u_0, u_1, u_2, …, u_n\) is an edge \(u_iu_j\), with \(j \geq i + 2\). A \(u-v\) chordless path in \(G\) is a \(monophonic\) \(path\). The monophonic closed interval \(I_{m}[u,v]\) consists of all the vertices lying on some \(u-v\) monophonic path. For \(S\subseteq V(G),\) the set \(I_{m}[S]\) is the union of all sets \(I_{m}[u,v]\) for \(u,v\in S.\) A set \(S\) of vertices in \(G\) is called a \(monophonic\) \(set\) of \(G\) if \(I_{m}[S]=V(G).\) The monophonic number \({m}(G)\) of G is the minimum cardinality of its monophonic sets. The monophonic number of a graph was introduced and studied in [2, 4, 5, 11]. There are useful applications of these concepts to protected facility location problems in real life situations, and also to security based communication network designs [12]. The edge monophonic closed interval \(I_{em}[u,v]\) consists of all the edges lying on some \(u-v\) monophonic path. For \(S'\subseteq V(G),\) the set \(I_{em}[S']\) is the union of all sets \(I_{em}[u,v]\) for \(u,v\in S'.\) A set \(S'\) of vertices in \(G\) is called an \(edge\) \(monophonic\) \(set\) of \(G\) if \(I_{em}[S']=E(G).\) The edge monophonic number \({m_1}(G)\) of G is the minimum cardinality of its edge monophonic sets of \(G\). The edge monophonic number of a graph was introduced and further studied in [6, 10]. The concepts of monophonic sets and edge monophonic sets have not been fully explored in the aspects of corona product graphs. This motivated us to the further study of monophonic sets in corona product graphs.
Throughout this paper, we use [1, 13] for terminology and notations. The following theorems will be used in the sequel.
Theorem 1.1. [11] Each extreme vertex of a connected graph \(G\) belongs to every monophonic set of \(G\). Moreover, if the set \(S\) of all extreme vertices of \(G\) is a monophonic set, then \(S\) is the unique minimum monophonic set of \(G\).
Theorem 1.2. [11] For the complete graph \(K_p(p \geq 2), m(K_p) = p.\)
Theorem 1.3. [11] No cutvertex of a connected graph \(G\) belongs to any minimum monophonic set of \(G\).
Theorem 1.4. [6] Each semi-extreme vertex of \(G\) belongs to every edge monophonic set of \(G.\) Moreover, if the set \(S\) of all semi-extreme vertices of \(G\) is an edge monophonic set, then \(S\) is the unique minimum edge monophonic set of \(G\).
Theorem 1.5. [6] No cutvertex of a connected graph \(G\) belongs to any minimum edge monophonic set of \(G.\)
Theorem 1.6. [6] For the complete graph \(K_p(p\geq2),\) \(m_1(K_p) = p.\)
Theorem 2.1. Let \(G\) and \(H\) be connected graphs of order \(r(r\geq 2)\) and \(s(s\geq 2)\) respectively. Then \(m(G \odot H) = rm(H)\), where \(m(H)\) is the monophonic number of \(H\).
Proof. Let \(S_i=\{v_{i,1}, v_{i,2}, \cdots, v_{i,m(H)}\}\) be a minimum monophonic set of \(H_i(1\leq i\leq r)\) and let \(v\) be a vertex in \(G\odot H\). Let \(S= \bigcup_{i}S_i(1\leq i\leq r)\). If \(v\in V(G)\) then \(v\) lies on a \(v_{i,1}-v_{j,1}(i\neq j)\) monophonic path for some \(v_{i,1},v_{j,1}\in S\). If \(v\in V(H_i)\), then \(v\) lies on a \(x-y\) monophonic path for some \(x,y\in S_i\), since \(S_i\) is a minimum monophonic set of \(H_i\). Hence \(S\) is a monophonic set of \(G\odot H\) and so \(m(G\odot H)\leq |S|=rm(H)\). It is easy to verify that any set \(S_1\subseteq V(G\odot H)\) with cardinality \(|S_1|<rm(H)\) is not a monophonic set of \(G\odot H\). Hence \(m(G \odot H) = rm(H)\). ◻
Theorem 2.2. Let \(G\) and \(H\) be connected graphs of order \(m(m\geq 2)\) and \(n(n\geq 2)\) respectively. Then \(m_1(G \odot H) = mn\).
Proof. Let \(V(G) = \left\{u_1, u_2, \cdots, u_{m}\right\}\) and \(V(H_i)= \left\{v_{i,1}, v_{i,2}, \cdots, v_{i,n}\right\},(1 \leq i \leq m)\) be the vertex sets of \(G\) and \(H_{i}(1 \leq i \leq m)\), respectively. Then it is clear that every vertex of \(m-\) copies of \(H\) is a semi-extreme vertex in \(G \odot H\) and every vertex of \(G\) is a cutvertex in \(G \odot H\). Let \(S= \bigcup_{i}V(H_i),(1 \leq i \leq m)\) be the set of all semi-extreme vertices of \(G \odot H\). By Theorem 1.4, every edge monophonic set of \(G \odot H\) contains \(S\). For any edge \(e\in E(G\odot H)\), there exist vertices \(v_{i,s}, v_{j,t}(1 \leq i,j \leq m\) and \(1 \leq s,t \leq n )\) in \(S\) such that \(e\in I_{em}[v_{i,s}, v_{j,t}]\) and hence it follows that \(S\) is the unique minimum edge monophonic set of \(G\odot H\). Hence, \(m_1(G \odot H) = |S| = mn\). ◻
Remark 2.3. In general, for any two connected graphs of order \(m(m\geq 2)\) and \(n(n\geq 2)\) respectively with \(m\neq n\), the graph of the corona products \(G \odot H\) and \(H \odot G\) are not same. The next theorem shows that \(m_1(G \odot H) = m_1(H \odot G)\).
Theorem 2.4. Let \(G\) and \(H\) be connected graphs of order \(m(m\geq 2)\) and \(n(n\geq 2)\) respectively. Then \(m_1(G \odot H) = m_1(H \odot G)=nm\).
Proof. Let \(V(H) = \left\{v_1, v_2, \cdots, v_{n}\right\}\) and \(V(G_i)= \left\{u_{i,1}, u_{i,2}, \cdots, u_{i,m}\right\},(1 \leq i \leq n)\) be the vertex sets of \(H\) and \(G_{i}(1 \leq i \leq n)\), respectively. In \(H \odot G\), it is clear that every vertex of \(n-\) copies of \(G\) is a semi-extreme vertex in \(H \odot G\) and every vertex of \(H\) is a cutvertex in \(H \odot G\). Let \(S_1= \bigcup_{i}V(G_i),(1 \leq i \leq n)\) be the set of all semi-extreme vertices of \(H \odot G\). By Theorem 1.4, every edge monophonic set of \(H \odot G\) must contain \(S_1\). For any edge \(e'\in E(H\odot G)\), there exist vertices \(u_{i,s}, u_{j,t}(1 \leq i,j \leq n\) and \(1 \leq s,t \leq m )\) in \(S_1\) such that \(e'\in I_{em}[u_{i,s}, u_{j,t}]\) and hence it follows that \(S_1\) is a minimum edge monophonic set of \(H\odot G\). Hence, \(m_1(H \odot G) = |S_1| = nm\). By Theorem 2.2, we have \(m_1(G \odot H)= mn\). Therefore, \(m_1(G \odot H)=m_1(H \odot G)\). ◻
Next, we explore some classes of graphs for which both monophonic number and edge monophonic number are equal. For this, let us consider the variants of silicate networks which are studied in [3, 7, 9]. In particular, let us consider a star of silicate network. We define the construction of a new star of a silicate network from the star of the David network [3, 8] as follows.
Step 1: To construct a star of David graph \(SDN\) of dimension \(n\), first consider the star of David graph \(H\) of dimension \(1\), as shown in Figure 1.
Step 2: Insert \(2n – 2\) vertices in every edge of \(H,\) and then divide each edge into \(2n – 1\) edges, as shown in Figure 2.
Step 3: Connect any two vertices \(u\) and \(v\) by an edge, if one is the mirror image of the other and if they are at an odd distance \(1, 3, 5, 7, \ldots , (6n – 1)\) from one corner vertices except the pairs at a distance \((2n – 1)\), as shown in Figure 3.
Step 4: Insert a new vertex at each new crossing of the edge. The resulting network is called the \(n-\)dimensional star of David network, which is denoted by \(SDN(n).\) The graph for the star of David network, \(SDN(2)\) is shown in Figure 4.
Step 5: Replace each \(K_3\) subgraph of \(SDN(n)\) with a tetrahedron. This network is known as the \(n-\)dimensional star of silicate network and is denoted by \(SSN(n).\) The graph for the star of silicate network, \(SSN(2)\) is shown in Figure 5.
Note 2.5. (i) The number of vertices and the number of edges of the star of David network \(SDN(n)\) are \(18n^2 -6n\) and \(36n^2 – 24n + 6\), respectively.
(ii) The number of vertices and the number of edges of the star of silicate network \(SSN(n)\) are \(30n^2 -18n + 6\) and \(42n^2 – 10n + 4\), respectively.
Theorem 2.6. For any star of David network \(G=SDN(n)\) of dimension \(n\geq 1\), \(m(G) = m_1(G)= 6\).
Proof. For \(n=1,\) \(G\) has only two types of vertices, namely a vertex of degree 2 and 4. For \(n \geq 2,\) it is easy to see that \(G\) has only three types of vertices, namely a vertex of degree 2, 3 and 4. In both cases, all the vertices of degree 2 in every six outer triangle of \(G\) is an extreme vertex of \(G\). Let \(S=\left\{u \in V(G)| deg(u) = 2\right\}\) be the set of all extreme vertices of \(G\). Note that every extreme vertex is a semi-extreme vertex. By Theorems 1.1 and 1.4, every monophonic set and every edge monophonic set of \(G\) contain \(S\). For any vertex \(x\in G\), there exist vertices \(u,v\) in \(S\) such that \(x\in I_m[u,v]\) so that \(S\) is a minimum monophonic set of \(G\). It is easy to verify that, for any edge \(e\in E(G)\), there exist vertices \(r,s\) in \(S\) such that \(e\in I_{em}[r,s]\) so that \(S\) is a minimum edge monophonic set of \(G\). Hence it follows from Theorems 1.1 and 1.4, \(S\) is the unique minimum monophonic set and unique minimum edge monophonic set of \(G\) and hence \(m(G) = m_1(G)=|S|=6\). ◻
Theorem 2.7. Let \(H\) be any connected graph of order \(m(m\geq 2)\) and \(G\) be the star of David network \(SDN(n)\) of dimension \(n\geq 1\). Then \(m_1(G\odot H)= 6mn(3n-1)\).
Proof. It follows from Theorem 2.4. ◻
Theorem 2.8. For any star of silicate network \(G=SSN(n)\) of dimension \(n\geq 1\), \(m(G)= m_1(G) = 12(n^2-n+1)\).
Proof. For \(n=1,\,G\) has only two types of vertices, namely a vertex of degree 3 and 6. For \(n \geq 2,\) it is easy to see that \(G\) has only three types of vertices, namely a vertex of degree 3, 4 and 6. In both cases, all the vertices of degree 3 in every tetrahedron and central vertices of each tetrahedron of \(G\) are extreme vertices. Let \(S'=\{u \in V(G)| deg(u) = 3\}\) be the set of all extreme vertices of \(G\). It is easy to see that \(S'\) comprises of 6 vertices of outer tetrahedrons and \(6(2n^2-2n+1)\) central vertices of each tetrahedron. Note that every extreme vertex is a semi-extreme vertex. By Theorems 1.1 and 1.4, every monophonic set and every edge monophonic set of \(G\) contain \(S'\). For any vertex \(x\in V(G)\), there exist vertices \(u,v\) in \(S'\) such that \(x\in I_m[u,v]\) so that \(S'\) is a minimum monophonic set of \(G\). It is easy to verify that, for any edge \(e'\in E(G)\), there exist vertices \(r,s\) in \(S'\) such that \(e'\in I_{em}[r,s]\) so that \(S'\) is a minimum edge monophonic set of \(G\). Hence it follows from Theorems 1.1 and 1.4, \(S'\) is the unique minimum monophonic set and unique minimum edge monophonic set of \(G\) and hence \(m(G) = m_1(G)=|S'|=12(n^2-n+1)\). ◻
Theorem 2.9. Let \(H\) be any connected graph of order \(m(m\geq 2)\) and \(G\) be the star of silicate network \(SSN(n)\) of dimension \(n\geq 1\). Then \(m_1(G\odot H)= 6m(5n^2 -3n + 1)\).
Proof. It follows from Theorem 2.4. ◻
Now, let us construct a triangular silicate network from a triangular grid graph.
Definition 2.10. [13] The triangular grid graph \(T_n\) is the graph on vertices \((i, j, k)\) with \(i, j, k\) being non-negative integers summing to \(n\) such that vertices are adjacent if the sum of absolute differences of the coordinates of two vertices is 2.
Remark 2.11. Triangular grid graph \(T_n\) has \(n + 1\) levels and each level \(i\)\((0 \leq i \leq n)\) contains \(i + 1\) vertices and \(i\) edges. Thus, \(T_n\) has \((n+1)(n+2) / 2\) vertices and \(3n(n+1) / 2\) edges, respectively. The \(diam(T_n) = n.\) For illustration, the triangular grid graph \(T_6\) is shown in Figure 6.
Replace each \(K_3\) subgraph of \(T_n\) with a tetrahedron. This network is known as the \(n-\)dimensional triangular silicate network [9]. An \(n-\) dimensional triangular silicate network is denoted by \(TSN(n).\) The graph triangular silicate network, \(TSN(3)\) is shown in Figure 2.9. The number of vertices in triangular silicate network \(TSN(n)\) is \(\left[\frac{(n-1)(n-2)}{2}\right] + 3n(n+1)\).
Theorem 2.12. For any triangular silicate network \(G=TSN(n)\) of dimension \(n\geq 1\), \(m(G) = m_1(G)= n^2+3\).
Proof. We prove this theorem by considering three cases.
Case 1. If \(n=1,\) then \(G\) is the complete graph of order 4 is shown in Figure 7. By Theorems 1.2 and Theorem 1.6, \(V(G)\) is the unique minimum monophonic as well as the unique minimum edge monophonic set of \(G\) and so \(m(G) ={m_1}(G) = \left|V(G) \right|=4=1^2+3\).
Case 2. If \(n=2,\) then \(G\) has only two types of vertices, namely a vertex of degree 3 and 7, the graph \(G\) is shown in Figure 8. All the vertices in \(G\) of degree 3 are extreme vertices. Let \(S=\left\{u \in V(G)|deg(u)=3\right\}\) be the set of all extreme vertices of \(G\). Note that every extreme vertex of \(G\) is a semi-extreme vertex. By Theorems 1.1 and 1.4, every monophonic set and every edge monophonic set of \(G\) contain \(S\). For any vertex \(x\in G\), there exist vertices \(u,v\) in \(S\) such that \(x\in I_m[u,v]\) so that \(S\) is a minimum monophonic set of \(G\). It is easy to verify that, for any edge \(e\in E(G)\), there exist vertices \(r,s\) in \(S\) such that \(e\in I_{em}[r,s]\) so that \(S\) is a minimum edge monophonic set of \(G\). Thus \(S\) is the unique minimum monophonic set and unique minimum edge monophonic set of \(G\) so that \(m(G) = m_1(G)=|S|=7=2^2+3\).
Case 3. If \(n\geq3,\) then \(G\) has only three types of vertices, namely a vertex of degree 3, 7 and 12, the graph \(G\) of dimension 3 is shown in Figure 9. Similar to previous case, \(S=\left\{u \in V(G)|deg(u)=3\right\}\) is the set of all extreme vertices of \(G\). Note that the set \(S\) comprises of \(n^2\) central vertices of every tetrahedron in \(G\) and the three corner vertices of \(G\). By Theorems 1.1 and 1.4, every monophonic set and every edge monophonic set of \(G\) contain \(S\). It is easy to verify that \(S\) is the unique minimum monophonic set and unique minimum edge monophonic set of \(G\) and hence \(m(G) = m_1(G)=|S|=n^2+3\). ◻
Theorem 2.13. Let \(H\) be any connected graph of order \(m(m\geq 2)\) and \(G\) be the triangular silicate network \(TSN(n)\) dimension \(n\geq 1\). Then \(m_1(G\odot H)= \left[\frac{m(n-1)(n-2)}{2}\right] + 3mn(n+1)\).
Proof. It follows from Theorem 2.4. ◻
Theorem 2.14. If \(K_n\) is the complete graph of order \(n(n \geq 2)\), then \(m(K_1\odot K_n)=m_1(K_1\odot K_n) = n+1\).
Proof. If \(G=K_1\odot K_n\), then \(G\) is a complete graph of order \(n+1\). By Theorems 1.2 and 1.6, we have \(m(K_1\odot K_n)=m_1(K_1\odot K_n) = n+1\). ◻
Theorem 2.15. If \(K_n\) is the complete graph of order \(n(n \geq 2)\) and if ‘\(e\)’ is a pendant edge, then \(m(K_n+e)=m_1(K_n + e) = n\).
Proof. Let \(V(K_n)=\{v_1,v_2,\ldots,v_n\}\) be the vertex set of \(K_n\) and let \(G = K_n + e\) with \(e=yv_i\) \((1 \leq i \leq n)\). It is clear that every vertex of \(G\) is an extreme vertex except the vertex \(v_i\), which is a cutvertex. Note that every extreme vertex of \(G\) is a semi extreme vertex. By Theorems 1.1, 1.3, 1.4 and 1.5, every monophonic set and every edge monophonic set of \(G\) contains \(S=V(G)-\left\{v_i\right\}\), \((1 \leq i \leq n)\). It is easy to verify that \(S\) is the unique minimum monophonic set and unique minimum edge monophonic set of \(G\) and hence \(m(G) = m_1(G)=|S|=n\). ◻
Theorem 2.16. If \(C_n\) is the cycle of order \(n(n \geq 3)\) and if ‘\(e\)’ is a pendant edge, then \[m(C_n + e) = m_1(C_n + e) = \begin{cases} 3 \text{~if~} n = 3,\\ 2 \text{~if~} n \geq 4. \end{cases}\]
Proof. Let \(C_n: v_1,v_2,v_3,\ldots,v_n,v_1\) be a cycle of length \(n\) and let \(G = C_n + e (n \geq 3)\) with \(e = v_1x\). If \(n=3\), then \(x,v_2,v_3\) are the only extreme vertices of \(G\). By Theorems 1.1 and 1.4, every monophonic set and every edge monophonic set of \(G\) contain \(S=\{x,v_2,v_3\}\). It is easy to see that \(S\) is the unique minimum monophonic set and unique minimum edge monophonic set of \(G\) and so \(m(G)=m_1(G) = 3\). If \(n\geq 4\), then \(x\) is the only extreme vertex of \(G\). By Theorems 1.1 and 1.4, the vertex \(x\) belongs to every monophonic set and every edge monophonic set of \(G\). Note that \(S = \{x, v_3\}\) is a minimum monophonic set as well as minimum edge monophonic set of \(G\) and so \(m(G)=m_1(G) = 2\). ◻