Graph Theory was started by Euler after solving the famous Konigsberg bridge problem. The Graph Coloring is among one of the famous topic for research since it has many beautiful theorems on optimization and its applications in numerous fields of science. The Pi coloring is the coloring of graph parts without a recurring pattern. As a result, it is defined as a function from a set of graph elements with similar properties to the power set of colors, so that each set receives a different color set from the power set. In consequence, Incident Vertex Pi coloring of a graph is defined as the coloring of incident vertices for every single edge with Pi coloring. Incident Vertex Pi coloring of the complete graph is \(n\), wheel graph, star graph and double star graph is \(n+1\), diamond, friendship graphs is \(\Delta +1\), and double fan graph is \(\Delta +2\). In this research, we derived the Incident Vertex PI coloring of Star and Double Star graph’s Middle graph, Total graph, Line graph, and Splitting graph.
Graph coloring is the most significant topic, and this was started with the famous Four Color Problem in Graph Theory. Let \(G\) be a simple graph, with its vertex and edge sets are \(V(G)\) and \(E(G)\) respectively. The vertex coloring is a function from a set of vertices \(V(G)\) to the color set \(C\) that satisfies the condition that no two adjacent vertices receive the same color [6, 19, 4, 11, 15]. Similarly, edge coloring is a function from a set of edges \(E(G)\) to the color set \(C\) that satisfies the condition that no two contiguous edges receive the same color [7, 11, 20]. In 1965, Behzad [2, 3, 1] introduced the Total coloring of a graph, in which color is applied to both vertices and edges together such that two neighboring elements are colored differently. There are various coloring methods introduced by many mathematicians. Bhapkar and Bhange [5] introduced the Perfect coloring of a graph, which is the proper coloring of vertices, edges, and regions of a graph altogether. There are many applications of graphs and its coloring methods. For details of the survey please refer [7, 11, 20]. Thakare and Bhapkar [17] introduced the \(\pi\)-Coloring, Incident Vertex \(\pi\)-Coloring of Graphs. The least number of colors required for \(\pi\)-Coloring, Incident Vertex \(\pi\)-Coloring are called the Pi Chromatic number and Incident Vertex Pi Chromatic number respectively. This coloring function is defined from a set of elements of a graph having some common properties to the power set of colors such that every subset is colored differently.
The vertex coloring of families \(S_{1,n}\) and \(S_{1,n,n}\) is 2 [11]. The edge coloring of family \(S_{1,n}\) and \(S_{1,n,n}\) is \(n\) [11]. The Total coloring of families \(S_{1,n}\) and \(S_{1,n,n}\) is \(n+1\) [3] [1]. The Incident Vertex PI coloring of the star (\(S_{1,n}\)) and Double Star (\(S_{1,n,n}\)) graph is \(n+1\) [17]. The vertex coloring of Complete graph \((K_n)\) is \(n\), the edge coloring of a Complete graph \((K_n)\) is \(n\), if \(n\) is odd and \(n-1\), if \(n\) is even. Total coloring of Complete graph \((K_n)\) is \(n\), if \(n\) is an odd number, and \(n+1\), if \(n\) is an even number [1]. The Incident Vertex PI coloring of a complete graph \((K_n)\) is \(n\) [17].
In the paper, we have considered a star graph \(S_{1,n}\) with a vertex set is \(\{u, u_{1}, u_{2},\) \(… u_{n}\}\) and an edge set is \(\{(u, u_{1}), (u, u_{2}), (u, u_{3}),… (u, u_{n})\}\). Similarly, a double star graph \(S_{1,n,n}\) with a vertex set is \(\{u, u_{1}, u_{2}, u_{3},…\), \(u_{n}, v_{1}, v_{2}, v_{3},… v_{n}\}\) and an edge set is \(\{(u, u_{1}),\) \((u, u_{2}), (u, u_{3}), … (u, u_{n}), (u_1, v_{1})\), \((u_2, v_{2}), (u_3, v_{3}),… (u_n, v_{n}) \}\).
Definition 2.1. (Complete Graph). This is the graph with \(n\) vertices such that each vertex is adjacent to all the remaining vertices. It is symbolized by \(K_n\). There are \(n(n-1)/2\) edges [19].
Definition 2.2. (Star graph). This is the graph on \(n+1\) vertices such that one vertex joins the rest of all \(n\) vertices. It is symbolized by \(S_{1,n}\). The common adjacent vertex is called the central vertex, and there are \(n\) pendant vertices. It has \(n\) edges [19].
Definition 2.3. The double star graph \(S_{1,n,n}\) is constructed from the star graph \(S_{1,n}\) by adding new \(n\) pendant vertices to each existing pendant vertex of the star graph. It has \(2n+1\) vertices and \(2n\) edges [19].
Definition 2.4. The middle graph for a simple graph is \(G\) represented as \(M(G)\); it a graph on the vertex set \(V(M(G))=V(G) \cup E(G)\). The vertices \(u, v\) from the vertex set \(V(M(G))\) are adjacent in \(M(G)\) if one of the following conditions is met.
(i) If \(u, v \in E(G)\), and \(u, v\) are adjacent in \(G\).
(ii) If \(u \in V(G)\) and \(v \in E(G)\) and \(u, v\) are incident in \(G\) [9, 14, 10, 8].
Definition 2.5. The total graph for a simple graph \(G\) is represented as \(T(G)\); it is a graph on the vertex set \(V(T(G))=V(G) \cup E(G)\). The vertices \(u, v\) from the vertex set \(V(T(G))\) are adjacent in \(T(G)\) if one of the following conditions is met.
(i) If \(u, v \in E(G)\), and \(u, v\) are adjacent in \(G\).
(ii) If \(u, v \in V(G)\), and \(u, v\) are adjacent in \(G\).
(iii) If \(u \in V(G)\) and \(v \in E(G)\), and \(u, v\) are incident in \(G\) [9, 14, 10, 8].
Definition 2.6. The line graph for a simple graph \(G\) is represented as \(L(G)\); it is the graph with its vertex set as the edges of \(G\) and there is an edge between two vertices of \(L(G)\) if and only if the respective edges of \(G\) are adjacent [19, 14].
Definition 2.7. The splitting graph \(S(G)\) is constructed from the graph \(G\) by adding a new vertex \(v\) for each vertex \(u \in V(G)\) such that the neighborhood of \(u\) and \(v\) is the same [13, 18, 12].
Definition 2.8. (Pi Coloring). Let \(G=(V, E)\) be a simple connected graph where \(V\) is a vertex set, \(E\) is an edge set, and \(X\) is a collection of subsets of elements of graph \(G\) having some common properties. If there exists a function \(f: X \longrightarrow P(C)\), where \(C\) is a set of colors and \(P(C)\) is its power set, ensures h that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\), then it is called Pi coloring of a graph \(G\) [17].
Definition 2.9. (Incident Vertex Pi Coloring). Let \(G=(V, E)\) be a simple connected graph where \(V\) is a vertex set, \(E\) is an edge set, and \(X\) is a collection of ordered pairs of incident vertices of every single edge \(e\) in \(E(G)\). Define a function \(f: X\longrightarrow P(C)\), where \(C\) is a set of colors and \(P(C)\) is its power set, ensures that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\), it is called Incident Vertex Pi Coloring of graph G [15, 16, 17].
In this paper, we derived the Incident Vertex Pi coloring of the Middle graph, Total graph, Line graph, and Splitting graph for the Star graph \(S_{1,n}\) and Double Star graph \(S_{1,n,n}\) families.
Theorem 3.1. If \(M(S_{1,n})\) is the middle graph of Star graph \(S_{1,n}\), then \[IVPI(M(S_{1,n}))=n+2.\]
Proof. Consider \(S_{1,n}\) be a Star graph with the vertex set \(V=\{u, u_{1}, u_{2}, u_{3},… u_{n}\}\) and an edge set is \(E=\{e_1=(u, u_{1}), e_2=(u, u_{2}), e_3=(u, u_{3}),… e_n=(u, u_{n})\}\). Then, by definition of the middle graph, we have a graph \(M(S_{1,n})\) with its vertex set is \(V(M(S_{1,n}))=\{u, u_{1}, u_{2}, u_{3}… u_{n}, e_{1}, e_{2}, e_{3}… e_{n} \}\). We observe that in this graph, there is a clique on the vertices \(\{u, e_{1}, e_{2}, e_{3}… e_{n}\}\). Therefore, its edge set consists of edges of a complete subgraph on \(n+1\) vertices, namely, \(\{u, e_{1}, e_{2}, e_{3}… e_{n}\}\) and the edges with \(n\) pendant vertices \(\{u_{1}, u_{2}, u_{3}… u_{n}\}\) namely \(\{(e_1, u_{1}), (e_2, u_{2}), … (e_n, u_{n})\}\).
Thus, \(E(M(S_{1,n}))=\{(u, e_1), (u, e_2), …(u, e_n); (e_i, e_j),\) for \(i \neq j = 1, 2,…n\) and \((e_1, u_{1}), (e_2, u_{2}),…\) , \((e_n, u_{n}) \}\).
Consider Incident Vertex Pi coloring for vertices of the Middle graph of the star graph as follows:
\[\{ u\rightarrow{}1, e_{1}\rightarrow{}2, e_{2}\rightarrow{}3,… e_{n}\rightarrow{}n+1 ; u_{1}\rightarrow{} n+2, u_{2}\rightarrow{}n+2,… u_{n}\rightarrow{}n+2 \}.\]
Thus we have a function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and a color set \(C=\{1,2,…n+2\}\) with its power set \(P(C)\). We notice that this coloring assigns distinct colors to every edge that is incident at its two end vertices, as below.
\[f(X_p)=\{(i, j),\text{ for } i = 1,2, …n \text{ and } j =i+1, i+2, … n+1 ; (i, n+2) \text{ for } i = 2, 3 …n+1\}.\]
Thus, we observe that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\). Therefore, \(IVPI(M(S_{1,n}))=n+2\). Hence the proof.
The incident vertex pi coloring of the middle graph \(M(S_{1,4})\) is shown in Figure 1. ◻
Theorem 3.2. If \(M(S_{1,n,n})\) is the middle graph of Double Star graph \(S_{1,n,n}\), then \[IVPI(M(S_{1,n,n})) = 2n+2.\]
Proof. Consider \(S_{1,n,n}\) be a Double Star graph with the vertex set \(V=\{u, u_{1}, u_{2},\) \(… u_{n}, v_{1}, v_{2}, v_{3},… v_{n}\}\) and an edge set is \(E=\{a_1=(u, u_{1}), a_2=(u, u_{2}), a_3=(u, u_{3}),… a_n=(u, u_{n}), b_1=(u_1, v_{1}), b_2=(u_2, v_{2}), b_3= (u_3, v_{3}), … b_n=(u_n, v_{n}) \}\). By definition of the Middle graph, we have a graph \(M(S_{1,n,n})\) with its vertex set is \(V(M(S_{1,n,n}))=\{u, u_{1}, u_{2}, … u_{n}, v_{1}, v_{2}, … v_{n}, a_{1}, a_{2}, … a_{n}, b_{1}, b_{2}, … b_{n} \}\). We observe that in this graph, there is a clique on the vertices \(\{u, a_{1}, a_{2}, a_{3}… a_{n}\}\). Therefore, its edge set \(E(M(S_{1,n,n}))\) consists of the edges of a complete subgraph on \(n+1\) vertices, namely \(\{u, a_{1}, a_{2}, a_{3}… a_{n}\}\). Also, there are \(3n\) edges with \(n\) triangles \(a_i-u_i-b_i-a_i\) for \(i=1,2,…n\). and \(n\) pendant edges \(\{ b_1 v_1, b_2 v_2, … b_n v_n \}\).
Thus, \(E(M(S_{1,n,n}))=\{(u, a_1), (u, a_2), …(u, a_n); (a_i, a_j),\) for \(i\neq j =1,2 …n\); \((b_1, v_{1})\), \((b_2, v_{2}), … (b_n, v_{n})\) and (\(a_i u_i, u_i b_i, b_i a_i\)), for \(i=1,2,…n \}\).
Consider Incident Vertex Pi coloring for vertices of the Middle graph of the double star graph \(M(S_{1,n,n})\) as follows:
\(\{ u \rightarrow{} 1, a_1 \rightarrow{} 2, a_2 \rightarrow{} 3,… a_n \rightarrow{} n+1; u_1 \rightarrow{} n+2, u_2 \rightarrow{} n+2,… u_n \rightarrow{} n+2;\) \(b_1 \rightarrow{} n+3, b_2 \rightarrow{} n+4,… b_n \rightarrow{} 2n+2; v_1 \rightarrow{} 1, v_2 \rightarrow{} 1,… v_n \rightarrow{} 1 \}\).
Thus, there is a function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and a color set \(C=\{1,2,…2n+2\}\) with its power set \(P(C)\). This coloring assigns distinct colors to every edge that is incident at its two end vertices, as below.
\(f(X_p)=\{(i, j),\) for \(i = 1,2 …n\) and \(j = i+1, i+2, … n+1; (i, n+2), (n+2, n+2+j), (n+2+j, i),\) for \(i = 2, 3 …n+1, j=1, 2 …n; (1, n+2+j),\) for \(j=1, 2 … n\}\). Thus, we observe that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\). Therefore, \(IVPI(M(S_{1,n,n}))=2n+2\). Hence the proof.
The Incident Vertex Pi coloring of the middle graph \(M(S_{1,4,4})\) is shown in Figure 2. ◻
Theorem 3.3. If \(T(S_{1,n})\) is Total graph of Star graph \(S_{1,n}\), then \[IVPI(T(S_{1,n}))=2n+1=\Delta +1.\]
Proof. Consider \(S_{1,n}\) be a Star graph with the vertex set \(V=\{u, u_{1}, u_{2}, u_{3},… u_{n}\}\) and edge set is \(E=\{e_1=(u, u_{1}), e_2=(u, u_{2}), e_3=(u, u_{3}),… e_n=(u, u_{n})\}\). Then, by definition of the Total graph, we have a graph \(T(S_{1,n})\) with its vertex set is \(V(T(S_{1,n}))=\{u, u_{1}, u_{2}, u_{3}… u_{n}, e_{1}, e_{2}, e_{3}… e_{n} \}\). We observe that in this graph, there is a clique on the vertices \(\{u, e_{1}, e_{2}, e_{3}… e_{n}\}\). Therefore, its edge set consists of edges of a complete subgraph on \(n+1\) vertices, namely \(\{u, e_{1}, e_{2}, e_{3}… e_{n}\}\). Also, we observe that the vertex \(u\) is the central vertex of a Star graph. Hence, in the Total graph of a Star graph, there are edges between a vertex \(u\) and \(\{u_{1}, u_{2}, u_{3}… u_{n}\}\) and each \(e_i\) is incident at \(u_i\), so there are edges \(\{(e_1, u_{1}), (e_2, u_{2}), … (e_n, u_{n})\}\).
Hence, \(E(T(S_{1,n}))=\{(u, e_1), (u, e_2), …(u, e_n); (e_i, e_j),\) for \(i =1, 2,…n-1, j = i+1, 2,…n; (u, u_1)\), \((u, u_2), …(u, u_n);\) and \((e_1, u_{1}), (e_2, u_{2}),… (e_n, u_{n}) \}\). The maximum degree of a vertex \(u\) is \(\Delta =2n\).
As a vertex \(u\) adjacent to all \(2n\) vertices of \(T(S_{1,n})\), hence by definition of Incident Vertex PI coloring, we needed \(2n+1\) colors for Incident Vertex Pi coloring [17]. So, Incident Vertex Pi coloring for vertices of the Total graph of the Star graph is as follows:
\[\{ u\rightarrow{}1, e_{1}\rightarrow{}2, e_{2}\rightarrow{}3,… e_{n}\rightarrow{}n+1 ; u_{1}\rightarrow{} n+2, u_{2}\rightarrow{}n+3,… u_{n}\rightarrow{}2n+1 \}.\]
So, we have a function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and a color set \(C=\{1,2,…2n+1\}\) with its power set \(P(C)\). This coloring assigns distinct colors to every edge that is incident at its two end vertices, as below.
\(f(X_p)=\{(i, j),\) for \(i = 1, 2, …n\) and \(j =i+1, i+2, … n+1; (1, j),\) for \(j = n+2, n+3, … 2n+1;\) \((i+1, n+i+1),\) for \(i = 1, 2, …n \}\).
Thus, we observe that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\). Therefore, \(IVPI(T(S_{1,n}))=2n+1=\Delta +1\). Hence the proof.
The incident vertex pi coloring of the total graph \(T(S_{1,4})\) is shown in Figure 3. ◻
Theorem 3.4. If \(T(S_{1,n,n})\) is Total graph of Double Star graph \(S_{1,n,n}\), then \[IVPI(T(S_{1,n,n}))=3n+1=(3/2)\Delta +1.\]
Proof. Consider \(S_{1,n,n}\) be a Double Star graph with the vertex set \(V=\{u, u_{1}, u_{2},\) \(… u_{n}, v_{1}, v_{2}, v_{3},… v_{n}\}\) and edge set is \(E=\{a_1=(u, u_{1}), a_2=(u, u_{2}), a_3=(u, u_{3}),… a_n=(u, u_{n}), b_1=(u_1, v_{1}), b_2=(u_2, v_{2}), b_3= (u_3, v_{3}), … b_n=(u_n, v_{n}) \}\). By definition of Total graph, we have a graph \(T(S_{1,n,n})\) with its vertex set is \(V(T(S_{1,n,n}))=\{u, u_{1}, u_{2}, u_{3}… u_{n}, v_{1}, v_{2}, v_{3}… v_{n}, a_{1}, a_{2}, a_{3}… a_{n}, b_{1}, b_{2}, b_{3}… b_{n} \}\). We observe that in this graph, there is a clique on the vertices \(\{u, a_{1}, a_{2}, a_{3}… a_{n}\}\). Therefore, its edge set \(E(T(S_{1,n,n}))\) consists of the edges of a complete subgraph on \(n+1\) vertices, namely \(\{u, a_{1}, a_{2}, a_{3}… a_{n}\}\). We notice that the vertex \(u\) is adjacent to vertices \(\{u_{1}, u_{2},… u_{n} \}\). Hence, in the total graph of the double star graph, there are edges between vertex \(u\) with vertices \(\{u_{1}, u_{2},… u_{n} \}\), and there are also edges of two types of triangular subgraphs \(a_i – u_i – b_i – a_i\), and \(u_i – b_i – v_i – u_i\), for \(i=1,2,… n\). Hence we have \(5n\) edges \((u_i, b_i)\) that are common edges between these two triangles for these \(2n\) triangular subgraphs. The maximum degree of vertex \(u\) is \(\Delta = 2n\).
The edge set is, \(E(T(S_{1,n,n}))=\{(u, a_1), (u, a_2), …(u, a_n); (a_i, a_j),\) for \(i=1,2 …n-1, j =i+1, …n\); \((u, u_1), (u, u_2), …(u, u_n)\); and \((a_i, u_i), (u_i, b_i), (b_i, a_i), (b_i, v_i), (v_i, u_i)\), for \(i=1,2,…n \}\).
Consider Incident Vertex Pi coloring for vertices of the Total graph of the double star graph \(T(S_{1,n,n})\) as follows:
\(\{ u \rightarrow{} 1, a_1 \rightarrow{} 2, a_2 \rightarrow{} 3,… a_n \rightarrow{} n+1; u_1 \rightarrow{} n+2, u_2 \rightarrow{} n+3,… u_n \rightarrow{} 2n+1;\)\( b_1 \rightarrow{} n+3, b_2 \rightarrow{} n+4, … b_{n-1} \rightarrow{} 2n+1, b_n \rightarrow{} n+2; v_1 \rightarrow{} 2n+2, v_2 \rightarrow{} 2n+3,… v_n \rightarrow{} 3n+1 \}\).
Thus, there is a function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and a color set \(C=\{1,2,…3n+1\}\) with its power set \(P(C)\). This coloring assigns distinct colors to every edge that is incident at its two end vertices, as below.
\(f(X_p)=\{(i, j),\) for \(i = 1,2 …n\) and \(j = i+1, i+2, … n+1\); \((1, n+1+j),\) for \(j=1, 2 … n\); \((i+1, n+1+i), (n+1+i, n+2+i), (n+2+i, i+1), (n+2+i, 2n+1+i), (2n+1+i, n+1+i),\) for \(i = 1, 2, 3 …n-1\); and \((n+1, 2n+1), (2n+1, n+2), (n+2, n+1), (n+2, 3n+1), (2n+1, 3n+1)\}\). As a result, we observe that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\). Therefore, \(IVPI(T(S_{1,n,n}))=3n+1=(3/2)\Delta +1\). Hence the proof.
The incident vertex pi coloring of middle graph \(T(S_{1,4,4})\) is shown in Figure 4. ◻
Theorem 3.5. If \(L(S_{1,n})\) is a Line graph of Star graph \(S_{1,n}\), then \[IVPI(L(S_{1,n}))=n=\Delta +1.\]
Proof. Consider \(S_{1,n}\) be a Star graph with the vertex set \(V=\{u, u_{1}, u_{2}, u_{3},… u_{n}\}\) and edge set is \(E=\{e_1=(u, u_{1}), e_2=(u, u_{2}), e_3=(u, u_{3}),… e_n=(u, u_{n})\}\). Its Line graph is a graph \(L(S_{1,n})\) with a vertex set is \(V(T(S_{1,n}))=\{e_{1}, e_{2}, e_{3}… e_{n} \}\). As all the edges of the Star graph are adjacent to each other, so \(L(S_{1,n})\) is a complete graph on these \(n\) vertices. Thus, \[E(L(S_{1,n}))=\{(e_i, e_j), \text{ for } i =1, 2,…n-1, j = i+1, i+2,…n \}.\]
The maximum degree of each vertex is \(\Delta =n-1\). Hence, by definition of Incident Vertex Pi coloring of a complete graph [17], we required \(n\) distinct colors as follows:
\[\{ e_{1}\rightarrow{}1, e_{2}\rightarrow{}2, e_{3}\rightarrow{}3,… e_{n}\rightarrow{}n \}.\]
Therefore, we have an Incident Vertex Pi coloring function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and color set \(C=\{1,2,…n\}\) with its power set \(P(C)\) such that
\[f(X_p)=\{(i, j), \text{ for } i = 1, 2, …n-1 \text{ and } j =i+1, i+2, … n \}.\]
As a result, \(f(X_p) \neq f(X_q)\), for all \(p \neq q\). Therefore, \(IVPI(L(S_{1,n}))=n=\Delta +1\). Hence the proof.
The incident vertex pi coloring of the total graph \(L(S_{1,6})\) is shown in Figure 5. ◻
Theorem 3.6. If \(L(S_{1,n,n})\) is a Line graph of Double Star graph \(S_{1,n,n}\), then \[IVPI(L(S_{1,n,n}))=n+1=\Delta +1.\]
Proof. Consider \(S_{1,n,n}\) be a Double Star graph with the vertex set \(V=\{ v, v_{1}, v_{2},\) \(… v_{n},\) \(u_{1}, u_{2},… u_{n} \}\) and edge set is \(E=\{a_1=(v, v_{1}), a_2=(v, v_{2}), … a_n=(v, v_{n}), b_1=(u_1, v_{1}), b_2=(u_2, v_{2}), …\) \(b_n=(u_n, v_{n}) \}\). Its Line graph is a graph \(L(S_{1,n,n})\) with a vertex set is \(V(T(S_{1,n,n}))=\{a_{1}, a_{2}, a_{3}… a_{n}, b_{1}, b_{2},\) \(b_{3}… b_{n} \}\). The edges \(\{a_{1}, a_{2}, a_{3}… a_{n}\}\) of the Double Star graph are adjacent to each other, so in \(L(S_{1,n,n})\) it forms a complete subgraph on these \(n\) vertices. Also, an edge \(a_i\) is adjacent to \(b_i\) for each \(i=1,2,…n\), hence there are \(n\) pendant edges \(\{(a_1, b_1), (a_2, b_2),…(a_n, b_n)\}\) in \(S_{1,n,n}\).
So, \[E(L(S_{1,n,n}))=\{(a_i, a_j), \text{ for } i = 1, 2, …n-1 \text{ and } j =i+1, i+2, … n;\] \((a_1, b_1),\) \((a_2, b_2),\) \(…(a_n, b_n) \}\). The maximum degree of this graph is \(\Delta=n\).
We required \(n\) distinct colors for Incident Vertex Pi coloring of complete subgraph [17] and we needed one more color, \(n+1\) for all pendant vertices. Hence, its Incident Vertex Pi colors are as follows:
\[\{ a_1 \rightarrow{} 1, a_2 \rightarrow{} 2,… a_n \rightarrow{} n; b_1 \rightarrow{} n+1, b_2 \rightarrow{} n+1, … b_n \rightarrow{} n+1 \}.\]
Thus, there is Incident Vertex Pi coloring function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and color set \(C=\{1,2,…n+1\}\) with its power set \(P(C)\) such that
\[f(X_p)=\{(i, j), \text{ for } i = 1,2 …n-1 \text{ and } j = i+1, i+2, … n; (i, n+1), \text{ for } i=1, 2 … n\}.\]
As a result, we observe that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\).
Therefore, \(IVPI(L(S_{1,n,n}))=n+1=\Delta +1\). Hence the proof.
The incident vertex pi coloring of middle graph \(L(S_{1,6,6})\) is shown in Figure 6. ◻
Theorem 3.7. If \(S(S_{1,n})\) is Splitting graph of Star graph \(S_{1,n}\), then \[IVPI(S(S_{1,n}))=2n+2=\Delta + 2.\]
Proof. Consider \(S_{1,n}\) be a Star graph with the vertex set \(V=\{u, u_{1}, u_{2}, u_{3},… u_{n}\}\) and edge set is \(E=\{a_1=(u, u_{1}), a_2=(u, u_{2}), a_3=(u, u_{3}),… a_n=(u, u_{n})\}\). Its Splitting graph is a graph \(S(S_{1,n})\) with its vertex set is \(V(S(S_{1,n}))=\{u, u_{1}, u_{2},\) \(… u_{n}\), \(v, v_{1}, v_{2}, … v_{n} \}\) such that \(N(u)=N(v)\) and \(N(u_i)=N(v_i)\) for \(i = 1, 2,…n\). The edge set of this graph is, \[E(S(S_{1,n}))=\{a_i=(u, u_i), b_i=(v, u_i),c_i=(u, v_i),d_i=(v, v_i),\text{ for } i = 1, 2,…n \}.\]
We observe that vertex \(u\) is adjacent to all vertices except \(v\); vertex \(v\) is adjacent to all vertices except \(u\) and \(d(u)=d(v)=2n\), which is the maximum degree \((\Delta)\) of this graph. By the definition of Incident Vertex Pi coloring, if we color every vertex with a distinct color, then every edge with its incident vertex pair will get distinct colors. Thus, for Incident Vertex Pi coloring, we are required \(2n+2\) distinct colors. The Incident Vertex Pi coloring is given below:
\[\{ u\rightarrow{}1, v\rightarrow{}2, u_{1}\rightarrow{}3, u_{2}\rightarrow{}4,… u_{n}\rightarrow{}n+2; v_{1}\rightarrow{} n+3, v_{2}\rightarrow{}n+4,… v_{n}\rightarrow{}2n+2 \}.\]
Define the Incident Vertex Pi coloring function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and a color set \(C=\{1,2,…2n+2\}\) with its power set \(P(C)\) such that every single edge of this graph is colored as follows:
\[f(X_p)=\{(1, i), (2, i)\text{ for }i = 3,4, …2n+2\}.\]
Thus, we observe that \(f(X_p) \neq f(X_q)\), for all \(p \neq q\). Therefore, \(IVPI(S(S_{1,n}))=2n+2=\Delta +2\). Hence the proof.
The incident vertex pi coloring of the splitting graph \(S(S_{1,4})\) is shown in Figure 7. ◻
Theorem 3.8. If \(S(S_{1,n,n})\) is a Splitting graph of Double Star graph \(S_{1,n,n}\), then \[IVPI(S(S_{1,n,n}))=2n+2=\Delta +2.\]
Proof. Consider \(S_{1,n,n}\) be a Double Star graph with the vertex set \(V=\{u, u_{1}, u_{2},\) \(… u_{n}, v_{1}, v_{2}, v_{3},… v_{n}\}\) and edge set is \(E=\{(u, u_{1}), (u, u_{2}), (u, u_{3}),… (u, u_{n})\), \((u_1, v_{1})\), \((u_2, v_{2}), (u_3, v_{3}), … (u_n, v_{n}) \}\). Its Splitting graph is a graph \(S(S_{1,n,n})\) with vertex set is \(V(S(S_{1,n,n}))=\{u, u_{1}, u_{2}, … u_{n}, v_{1}, v_{2}, … v_{n}\), \(p, p_{1}\), \(p_{2}, … p_{n}\), \(q_{1}, q_{2}, … q_{n} \}\), such that \(N(u)=N(p)\), \(N(u_i)=N(p_i)\) and \(N(v_i)=N(q_i)\) for \(i = 1, 2,…n\).
The edge set of this graph is, \(E(S(S_{1,n,n}))=\{(u, u_i), (u, p_i), (p, u_i); (p, p_i),\) for \(i=1,2 …n\); and edges of cycle \(u_i – q_i – p_i – v_i – u_i\): \((u_i, q_i), (q_i, p_i), (p_i, v_i), (v_i, u_i),\) for \(i=1,2 …n \}\).
We observe that, \(N(u)=N(p)= \{ u_1,u_2,…u_n,p,p_1,p_2,…p_n \}\). So \(d(u)=d(p)=2n\), this is the maximum degree (\(\Delta\)) of \(S(S_{1,n,n})\). Hence, by definition of Incident Vertex Pi coloring, we are required to have \(2n+2\) distinct colors as follows:
\(\{ u \rightarrow{} 1, p \rightarrow{} 2, u_1 \rightarrow{} 3, p_1 \rightarrow{} 4, u_2 \rightarrow{} 5; p_2 \rightarrow{} 6, … u_n \rightarrow{} 2n+1; p_n \rightarrow{} 2n+2; v_1 \rightarrow{} 5, q_1 \rightarrow{} 6, v_2 \rightarrow{} 7, q_2 \rightarrow{} 8,… v_{n-1} \rightarrow{} 2n+1, q_{n-1} \rightarrow{} 2n+2,\) and \(v_n \rightarrow{} 3, q_n \rightarrow{} 4 \}\).
Define the Incident Vertex Pi coloring function \(f:X \longrightarrow{} P(C)\), where \(X\) is a set of elements as edges of a graph with incident vertices of an edge as an ordered pair and a color set \(C=\{1,2,…2n+2\}\) with its power set \(P(C)\) such that every single edge of this graph is colored as follows:
\(f(X_p)=\{(1, i),(2, i),\) for \(i = 3,4, …2n+2\); \((i, i+3), (i+3, i+1), (i+1, i+2), (i+2, i)\) for \(i = 3, 5 …2n-1;\) and \((2n+1, 3), (3, 2n+2), (2n+2, 4), (4, 2n+1) \}\).
As a result, we observe that, \(f(X_p) \neq f(X_q)\), for all \(p \neq q\).
Therefore, \(IVPI(S(S_{1,n,n}))=2n+2=\Delta + 2\). Hence the proof. ◻
We investigated the Incident Vertex Pi coloring of the Middle graph, Total graph, Line graph, and Splitting graph for the family of Star and Double Star graphs in this research. We determined the precise optimum Incident Vertex Pi coloring numbers for these graph families based on the results. When compared to the chromatic number of a graph, we observed that the Incident Vertex Pi coloring number is distinct from the chromatic number.
| Graph | Chromatic Number | IVPI Coloring Number |
|---|---|---|
| \(S_{1,n}\) | 2 | \(n+1\) |
| \(S_{1,n,n}\) | 2 | \(n+1\) |
| \(M(S_{1,n})\) | \(n+1\) | \(n+2\) |
| \(M(S_{1,n,n})\) | \(n+1\) | \(2n+2\) |
| \(T(S_{1,n})\) | \(n+1\) | \(2n+1\) |
| \(T(S_{1,n,n})\) | \(n+1\) | \(3n+1\) |
| \(L(S_{1,n})\) | \(n\) | \(n\) |
| \(L(S_{1,n,n})\) | \(n\) | \(n+1\) |
| \(S(S_{1,n})\) | \(n\) | \(2n+2\) |
| \(S(S_{1,n,n})\) | \(n\) | \(2n+2\) |
The author expresses gratitude to the referees for their significant contributions, insightful remarks, and recommendations.
The authors declare no conflicts of interest.