Application of Decomposition of Cartesian Product and Corona Product of Sunlet and Path in Pharmacy

All graphs considered here are finite and undirected unless otherwise stated. Let P_r be the path on r vertices. For a graph G, if E(G) can be partitioned into E_1,E_2,….,E_m such that the subgraph of G induced by E_i is H_i for all 1 ≤i ≤m, then H_1,H_2,….,H_m decompose G and is written as E(G)=E(H_1 )∪E(H_2 )∪….∪E(H_m ). If for 1 ≤i ≤m, H_i≅ H, we say that G has a H-decomposition.  In [6], Tay-Woei Shyu studied the decomposition of graphs into paths and stars. In [4], S. Arumugam, I. Sahul Hamid and V. M. Abraham gave the decomposition of a graph G on n vertices (not necessarily connected) into ⌊n/2⌋ paths and cycles.  For any two graphs G and H, their cartesian product, denoted by G □ H has vertex set V(G □(□)  H)=V(G)×V(H) and edge set E(G □ H)={(g,h)(gˈ,hˈ):g=gˈ,hhˈ∈E(H),or ggˈ∈E(G),h=hˈ}. It is well known that the cartesian product is commutative and associative. R. Frucht and F. Harary in their paper [3], introduced a new and simple operation on two graphs G_1 and G_2 called their corona product. For any two graphs G_1 and G_2 of orders m and n respectively, their corona product G_1◉ G_2 is the graph obtained by taking one copy of G_1 and m copies of G_2 such that the i^th vertex of G_1 is connected to every vertex in the i^th copy of G_2. K. Sowndhariya and A. Muthusamy [1], studied the cartesian product of complete graphs into sunlet graphs of order eight. In [5], S. Vimala Roshni and P. Chithra Devi gave the P_4- decomposability of cartesian product of paths and cycles. Here in this paper, we focus on the decomposition of cartesian product and corona product of sunlet and path.

 

Consider a graph H_1 with V(H_1 )={x_(i,j):1≤i≤6; 1≤j≤3} and E(H_1 )={x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(3,q),x_(r,s) x_(r+3,s):1≤i≤6;1≤j≤2; 1≤k≤5;  1≤l,q,r,s≤3}. H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2 as follows: {x_1,2 x_1,1,x_1,2 x_2,2,x_1,2 x_3,2 },{x_1,3 x_1,2,x_1,3 x_2,3,x_1,3 x_3,3 },{x_2,2 x_2,1,x_2,2 x_3,2,x_2,2 x_5,2 }, 

{x_2,3 x_2,2,x_2,3 x_3,3,x_2,3 x_5,3 }, {x_3,2 x_3,1,x_3,2 x_6,2 }, {x_3,3 x_3,2,x_3,3 x_6,3 },{x_4,2 x_4,1,x_4,2 x_1,2 },

{x_4,3 x_4,2,x_4,3 x_1,3 },{x_5,2 x_5,1,x_5,2 x_5,3 } and {x_6,2 x_6,1,x_6,2 x_6,3 }.

Theorem 1.2. For any two positive integers m,n with m=3, n≥2 and n is even, 

L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2 if and only if

 p+2/3 q=5/3 mn-(n+2).

 

Let G=L_2m□ P_n where V(G)={x_(i,j):1≤i≤2m,1≤j≤n} and 

E(G)={x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(m,q),x_(r,s) x_(r+m,s):1≤i≤2m,1≤j≤n-1,

1≤k≤m-1,1≤l,q,s≤n,1≤r≤m}. Suppose that L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

Since |E(G)|=3p+2q, we have

3p+2q=3[n(m-1)]+2(mn-3).

⇒3p+2q=5mn-3n-6.

Therefore, p+2/3 q=5/3 mn-(n+2).

Conversely, suppose that p+2/3 q=5/3 mn-(n+2).

For n=2, the set of edges {x_1,1 x_1,2,x_1,1 x_2,1,x_1,1 x_3,1 },{x_1,2 x_2,2,x_1,2 x_3,2,x_1,2 x_4,2 },

{x_2,1 x_3,1,x_2,1 x_5,1,x_2,1 x_2,2 }, {x_3,2 x_2,2,x_3,2 x_3,1,x_3,2 x_6,2 }, {x_4,1 x_1,1,x_4,1 x_4,2 },{x_5,2 x_5,1,x_5,2 x_2,2 } and {x_6,1 x_3,1,x_6,1 x_6,2 } forms 4 copies of  K_1,3 and 3 copies of  K_1,2. Therefore L_6□ P_2 is decomposed into 4 copies of K_1,3 and 3 copies of K_1,2. For n≥4, we prove this theorem by induction on n. For n=4, the induced subgraph <{x_(i,3),x_(i,4)}> together with the edge x_(i,2) x_(i,3)  forms H_1  ∀ 1≤i≤2m. Thus E(L_2m □(□(□)) P_4 )=E(L_2m □(□(□)) P_2)∪E(H_1). Assume that the theorem is true for n-2. The induced subgraph <{x_(i,j),x_(i,j+1)}> together with the edge x_(i,j-1) x_(i,j) where j=5,7,…,n-1 forms H_1  ∀ 1≤i≤2m. 

 

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□)) P_(n-2))∪E(H_1). Therefore by induction hypothesis, L_2m□ P_(n-2) is decomposed into 2(n-2) copies of K_1,3 and 3(n-3) copies of K_1,2.  Also by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2. Hence L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

 

Remark 1.3. 

Consider a graph H_2 with V(H_2 )={x_i,y_j:1≤i≤4; 1≤j≤2} and 

E(H_2 )={x_i x_(i+1),x_4 x_1,x_j y_j:1≤i≤4;1≤j≤2}. H_2 is decomposed into 3 copies of K_1,2 as follows: {x_1 y_1,x_1 x_4 }, {x_3 x_2,x_3 x_4 } and {x_2 x_1,x_2 y_2 }.

 

Remark 1.4. 

Consider a graph H_3 with V(H_3 )={x_(i,j):1≤i≤3; 1≤j≤3} and

E(H_3 )={x_(i,j) x_(i,j+1),x_(1,l) x_(2,l),x_(1,q) x_(3,q):i=1,3; 1≤j≤2;  2≤l≤3; 2≤q≤3}.

H_3 is decomposed into 2 copies of K_1,3 and 1 copy of K_1,2 as follows: {x_1,2 x_1,1,x_1,2 x_2,2,x_1,2 x_3,2 }, {x_1,3 x_1,2,x_1,3 x_2,3,x_1,3 x_3,3 } and {x_3,2 x_3,1,x_3,2 x_3,3 }.

 

Theorem 1.5. For any two positive integers m,n with m=4, n≥2 and n is even, 

L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2 if and only if

 p+2/3 q=4/3(mn-2).

 

Proof:

Let G=L_2m□ P_n where V(G)={x_(i,j):1≤i≤2m,1≤j≤n} and 

E(G)={x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(m,q),x_(r,s) x_(r+m,s):1≤i≤2m,1≤j≤n-1,

1≤k≤m-1,1≤l,q,s≤n,1≤r≤m}. Suppose that L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

Since |E(G)|=3p+2q,

we have 3p+2q=3[n(m-1)-2]+2[(m+3)  n/2-1].

⇒3p+2q=4mn-8.

⇒3p+2q=4(mn-2).

Therefore, p+2/3 q=4/3(mn-2).

 

Conversely, suppose that p+2/3 q=4/3(mn-2).

For n=2, the induced subgraph <{x_3,1,x_3,2,x_7,1,x_7,2}> together with the edges {x_3,1 x_4,1,

x_2,2,x_3,2} forms H_2. Thus E(L_8 □(□(□)) P_2 )=E(L_6 □(□(□)) P_2)∪E(H_2). Therefore, by Theorem 1.2., L_6 □(□(□)) P_2 is decomposed into 4 copies of K_1,3 and 3 copies of K_1,2. Also, by Remark 1.3., H_2 is decomposed 3 copies of K_1,2. For n≥4, we prove this theorem by induction on n.

 

For n=4, the induced subgraph <{x_(i,3),x_(i,4),x_(m-1,3),x_(m-1,4),x_(m,3),x_(m,4),x_(m+1,3),x_(m+1,4),

x_(2m-1,3),x_(2m-1,4),x_(2m,3),x_(2m,4)}> together with the edges {x_(i,2) x_(i,3),x_(i+1,3) x_(i,3),x_(i,4) x_(i+1,4),

x_(m-1,2) x_(m-1,3),x_(m,2) x_(m,3),x_(m+1,2) x_(m+1,3),x_(2m-1,2) x_(2m-1,3),x_(2m,2) x_(2m,3)} forms H_1

 ∀ 1≤i≤2m. Also, the induced subgraph <{x_(i,3),x_(i,4),x_(i+m,3),x_(i+m,4) }> together with the edges 〖{x〗_(i,2) x_(i,3),x_(i,3) x_(i+1,3),x_(i,4) x_(i+1,4),x_(i+m,2) x_(i+m,3)} forms H_3 ∀ i=2.

Thus E(L_2m □(□(□)) P_4 )=E(L_2m □(□(□)) P_2)∪E(H_1)∪E(H_3). Assume that the theorem is true for 

n-2. The induced subgraph <{x_(i,j),x_(i,j+1),x_(m-1,j),x_(m-1,j+1),x_(m,j),x_(m,j+1),x_(m+1,j),x_(m+1,j+1),

x_(2m-1,j),x_(2m-1,j+1),x_(2m,j),x_(2m,j+1)}> together with the edges {x_(i,j-1) x_(i,j),x_(i+1,j) x_(i,j),

x_(i,j+1) x_(i+1,j+1),x_(m-1,j-1) x_(m-1,j),x_(m,j-1) x_(m,j),x_(m+1,j-1) x_(m+1,j),x_(2m-1,j-1) x_(2m-1,j),x_(2m,j-1) x_(2m,j)} 

where j=5,7,…,n-1 forms H_1 ∀ 1≤i≤2m. Also, the induced subgraph <{x_(i,j),x_(i,j+1),

x_(i+m,j),x_(i+m,j+1)}> together with the edges 〖{x〗_(i,j-1) x_(i,j),x_(i,j) x_(i+1,j),x_(i,j+1) x_(i+1,j+1),

x_(i+m,j-1) x_(i+m,j)} where j=5,7,…,n-1 forms H_3 ∀ i=2.

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□)) P_(n-2))∪E(H_1)∪E(H_3). Therefore, by induction hypothesis, L_2m□ P_(n-2) is decomposed into 3n-8 copies of K_1,3 and 7n/2 copies of K_1,2.  Also, by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2. And also, by Remark 1.3., H_3 is decomposed into 2 copies of K_1,3 and 1 copy of K_1,2. Hence L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

 

Theorem 1.6. For any two positive integers m,n with m=5, n≥2 and n is even, 

L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2 if and only if

 p+2/3 q=5/3[n(m-1)-2].

 

Let G=L_2m□ P_n where V(G)={x_(i,j):1≤i≤2m,1≤j≤n} and 

E(G)={x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(m,q),x_(r,s) x_(r+m,s):1≤i≤2m,1≤j≤n-1,

1≤k≤m-1,1≤l,q,s≤n,1≤r≤m}. Suppose that L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

Since |E(G)|=3p+2q,

we have 3p+2q=3[n(m-1)-4]+2[n(m-1)+1].

⇒3p+2q=5mn-5n-10.

Therefore,  p+2/3 q=5/3[n(m-1)-2]

Conversely, suppose that  p+2/3 q=5/3 [n(m-1)-2].

For n=2, the induced subgraph <{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1)}> together with the edges {x_(i-1,j+1) x_(i,j+1),x_(i,j),x_(i+1,j)} where j=1 forms 2 copies of H_(2 )∀ i=3,4.

 

Thus E(L_10 □(□(□)) P_2 )=E(L_6 □(□(□)) P_2)∪E(H_2)∪E(H_2). Therefore, by Theorem 1.2., L_6 □(□(□)) P_2 is decomposed into 4 copies of K_1,3 and 3 copies of K_1,2. Also, by Remark 1.3., H_2 is decomposed 6 copies of K_1,2. For n≥4, we prove this theorem by induction on n. 

For n=4, the induced subgraph <{x_(i,3),x_(i,4),x_(m-1,3),x_(m-1,4),x_(m,3),x_(m,4),x_(m+1,3),x_(m+1,4),

x_(2m-1,3),x_(2m-1,4),x_(2m,3),x_(2m,4)}> together with the edges {x_(i,2) x_(i,3),x_(i+1,3) x_(i,3),x_(i,4) x_(i+1,4),

x_(m-1,2) x_(m,3),x_(m+1,2) x_(m+1,3),x_(2m-1,2) x_(2m-1,3),x_(2m,2) x_(2m,3)} forms H_1

 ∀ 1≤i≤2m. Also, the induced subgraph <{x_(i,3),x_(i,4),x_(i+m,3),x_(i+m,4) }> together with the edges 〖{x〗_(i,2) x_(i,3),x_(i,3) x_(i+1,3),x_(i,4) x_(i+1,4),x_(i+m,2) x_(i+m,3)} forms 2 copies of H_3 ∀ i=2,3.

Thus E(L_2m □(□(□)) P_4 )=E(L_2m □(□(□)) P_2)∪E(H_1)∪E(H_3)∪E(H_3). Assume that the theorem is true for n-2. The induced subgraph <{x_(i,j),x_(i,j+1),x_(m-1,j),x_(m-1,j+1),x_(m,j),x_(m,j+1),x_(m+1,j),

x_(m+1,j+1),x_(2m-1,j),x_(2m-1,j+1),x_(2m,j),x_(2m,j+1)}> together with the edges {x_(i,j-1) x_(i,j),x_(i+1,j) x_(i,j),

 

where j=5,7,…,n-1 forms H_1 ∀ 1≤i≤2m. Also, the induced subgraph 

<{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1) }> together with the edges 〖{x〗_(i,j-1) x_(i,j),x_(i,j) x_(i+1,j),x_(i,j+1) x_(i+1,j+1),

x_(i+m,j-1) x_(i+m,j)} where j=5,7,…,n-1 forms 2 copies of H_3 ∀ i=2,3.

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□)) P_(n-2))∪E(H_1)∪E(H_3)∪E(H_3). Therefore, by induction hypothesis, L_2m□ P_(n-2) is decomposed into 4(n-3) copies of K_1,3 and 4n-7 copies of K_1,2. Also, by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2. And also, by Remark 1.4., H_3 is decomposed into 4 copies of K_1,3 and 2 copies of K_1,2. Hence L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

 

Theorem 1.7. For any two positive integers m,n with m≥3, n≥2 and n is even, 

L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2 if and only if

 p+2q/3={█((n(5m-3)-6(m+2))/3,if m=3@(2[m(2n-3)+8])/3,if m≥4 and m is even@(5n(m-1)-2(3m-10))/3,if m≥5 and m is odd)┤

 

Let G=L_2m□ P_n where V(G)={x_(i,j):1≤i≤2m,1≤j≤n} and 

E(G)={x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(m,q),x_(r,s) x_(r+m,s):1≤i≤2m,1≤j≤n-1,

1≤k≤m-1; 1≤l≤n; 1≤q≤n; 1≤r≤m; 1≤s≤n}. Suppose that L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

 

Case (i): m=3

Since |E(G)|=3p+2q, 

we have 3p+2q=3[n(m-1)-2(m-3)]+2[mn-3].

⇒3p+2q=5mn-3n-6m+12.

Therefore, p+2q/3=(n(5m-3)-6(m+2))/3.

 

Case (ii): m≥4 and m is even

Since |E(G)|=3p+2q, 

we have 3p+2q=3[n(m-1)-2(m-3)]+2[(m+3)n/2-1].

⇒3p+2q=4mn-6m+16.

Therefore, p+2q/3=(2[m(2n-3)+8])/3.

Case (iii): m≥5 and m is odd

Since |E(G)|=3p+2q, 

we have 3p+2q=3[n(m-1)-2(m-3)]+2[n(m-1)+1].

⇒3p+2q=5mn-5n-6m+20.

Therefore, p+2q/3=(5n(m-1)-2(3m-10))/3.

Conversely,

Case (i): Suppose that p+2q/3=(n(5m-3)-6(m+2))/3, if m=3 

The proof of this case follows precisely from Theorem 1.2.

Case (ii): Suppose that p+2q/3=(2[m(2n-3)+8])/3, if m≥4 and m is even

For m=4, The proof follows precisely from Theorem 1.5. For m≥6, we prove this case by double induction method.

Subcase (i): m=6

For n=2, the induced subgraph <{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1)}> together with the edges {x_(i-1,j+1) x_(i,j+1),x_(i,j),x_(i+1,j)} where j=1 forms 3 copies of H_(2 )∀ i=3,4,5.

Thus E(L_2m □(□(□)) P_2 )=E(L_6 □(□(□)) P_2) ∪E(H_2)∪E(H_2)∪E(H_2). Therefore, by Theorem 1.2., L_6 □(□(□)) P_2 is decomposed into 4 copies of K_1,3 and 3 copies of K_1,2. Also, by Remark 1.3., H_2 is decomposed 9 copies of K_1,2. For n≥4, we prove this theorem by induction on n. 

For n=4, the induced subgraph <{x_(i,3),x_(i,4),x_(m-1,3),x_(m-1,4),x_(m,3),x_(m,4),x_(m+1,3),x_(m+1,4),

x_(2m-1,3),x_(2m-1,4),x_(2m,3),x_(2m,4)}> together with the edges {x_(i,2) x_(i,3),x_(i+1,3) x_(i,3),x_(i,4) x_(i+1,4),

x_(m-1,2) x_(m-1,3),x_(m,2) x_(m,3),x_(m+1,2) x_(m+1,3),x_(2m-1,2) x_(2m-1,3),x_(2m,2) x_(2m,3)} forms H_1

 ∀ 1≤i≤2m. Also, the induced subgraph <{x_(i,3),x_(i,4),x_(i+m,3),x_(i+m,4) }> together with the edges 〖{x〗_(i,2) x_(i,3),x_(i,3) x_(i+1,3),x_(i,4) x_(i+1,4),x_(i+m,2) x_(i+m,3)} forms 3 copies of H_3 ∀ i=2,3,4.

Thus E(L_2m □(□(□)) P_4 )=E(L_2m □(□(□)) P_2)∪E(H_1)∪E(H_3)∪E(H_3)∪E(H_3). Therefore, by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2. Also, by Remark 1.4., H_3 is decomposed into 6 copies of K_1,3 and 3 copies of K_1,2. Assume that this subcase is true for n-2. The induced subgraph <{x_(i,j),x_(i,j+1),x_(m-1,j),x_(m-1,j+1),x_(m,j),x_(m,j+1),x_(m+1,j),x_(m+1,j+1),

x_(2m-1,j),x_(2m-1,j+1),x_(2m,j),x_(2m,j+1)}> together with the edges {x_(i,j-1) x_(i,j),x_(i+1,j) x_(i,j),

x_(i,j+1) x_(i+1,j+1),x_(m-1,j-1) x_(m-1,j),x_(m,j-1) x_(m,j),x_(m+1,j-1) x_(m+1,j),x_(2m-1,j-1) x_(2m-1,j),x_(2m,j-1) x_(2m,j)} 

where j=5,7,…,n-1 forms H_1 ∀ 1≤i≤2m. Also, the induced subgraph 

<{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1) }> together with the edges 〖{x〗_(i,j-1) x_(i,j),x_(i,j) x_(i+1,j),

x_(i,j+1) x_(i+1,j+1),x_(i+m,j-1) x_(i+m,j)} where j=5,7,…,n-1 forms 3 copies of H_3 ∀ i=2,3,4.

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□(□)) ) P_(n-2) )∪E(H_1 )∪E(H_3 )∪E(H_3 )∪E(H_3 ). Therefore, by induction hypothesis, L_2m□ P_(n-2) is decomposed into 5n-16 copies of K_1,3 and (9(n-2))/2-1 copies of K_1,2. Hence the Subcase (i) is decomposed into 5n-1 copies of K_1,3 and 9n/2-1 copies of K_1,2. Assume that this Case (ii) is true for m-2. The induced subgraph 

<{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1) }> together with the edges 〖{x〗_(i,j-1) x_(i,j),x_(i,j) x_(i+1,j),

x_(i,j+1) x_(i+1,j+1),x_(i+m,j-1) x_(i+m,j)} where j=n-3,n-1 forms 2 copies of H_3

for all i=m-3,m-2. Thus E(L_2m □(□(□)) P_n )=E(L_(2m-2) □(□(□(□)) ) P_n )∪E(H_3 )∪E(H_3 ).

Therefore, by induction hypothesis, L_(2m-2)□ P_n is decomposed into n(m-3)-2(m-5) copies of K_1,3 and (m+1)n/2-1 copies of K_1,2. Hence L_2m□ P_n is decomposed into

 n(m-1)-2(m-3) copies of K_1,3 and (m+3)n/2-1 copies of K_1,2 in this case.

Case (iii): Suppose that p+2q/3=(5n(m-1)-2(3m-10))/3, if m≥5 and m is odd

For m=5, The proof follows precisely from Theorem 1.6. For m≥7, we prove this case by double induction method.

Subcase (ii): m=7

For n=2, the induced subgraph <{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1)}> together with the edges {x_(i-1,j+1) x_(i,j+1),x_(i,j),x_(i+1,j)} where j=1 forms 4 copies of H_(2 )∀ i=3,4,5,6.

Thus E(L_2m □(□(□(□)) ) P_2 )=E(L_6 □(□(□(□)) ) P_2 )∪E(H_2 )∪E(H_2 )∪E(H_2 )∪E(H_2 ). Therefore, by Theorem 1.2., L_6 □(□(□(□)) ) P_2 is decomposed into 4 copies of K_1,3 and 3 copies of K_1,2. Also, by Remark 1.3., H_2 is decomposed 12 copies of K_1,2. For n≥4, we prove this theorem by induction on n. For n=4, the induced subgraph <{x_(i,3),x_(i,4),x_(m-1,3),x_(m-1,4),x_(m,3),x_(m,4),

x_(m+1,3),x_(m+1,4),x_(2m-1,3),x_(2m-1,4),x_(2m,3),x_(2m,4)}> together with the edges {x_(i,2) x_(i,3),

forms H_1 ∀ 1≤i≤2m. Also, the induced subgraph <{x_(i,3),x_(i,4),x_(i+m,3),x_(i+m,4) }> together with the edges 〖{x〗_(i,2) x_(i,3),x_(i,3) x_(i+1,3),x_(i,4) x_(i+1,4),x_(i+m,2) x_(i+m,3)} forms 4 copies of H_3 

for all i=2,3,4,5. 

Thus E(L_2m □(□(□)) P_4 )=E(L_2m □(□(□)) P_2)∪E(H_1)∪E(H_3)∪E(H_3)∪E(H_3)∪E(H_3).

Therefore, by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2. Also, by Remark 1.4., H_3 is decomposed into 8 copies of K_1,3 and 4 copies of K_1,2. Assume that this Subcase is true for n-2. The induced subgraph <{x_(i,j),x_(i,j+1),x_(m-1,j),x_(m-1,j+1),x_(m,j),x_(m,j+1),

x_(m+1,j),x_(m+1,j+1),x_(2m-1,j),x_(2m-1,j+1),x_(2m,j),x_(2m,j+1)}> together with the edges {x_(i,j-1) x_(i,j),

x_(i+1,j) x_(i,j),x_(i,j+1) x_(i+1,j+1),x_(m-1,j-1) x_(m-1,j),x_(m,j-1) x_(m,j),x_(m+1,j-1) x_(m+1,j),x_(2m-1,j-1) x_(2m-1,j),

x_(2m,j-1) x_(2m,j)} where j=5,7,…,n-1 forms H_1 ∀ 1≤i≤2m. Also, the induced subgraph <{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1) }> together with the edges 〖{x〗_(i,j-1) x_(i,j),x_(i,j) x_(i+1,j),x_(i,j+1) x_(i+1,j+1),

x_(i+m,j-1) x_(i+m,j)} where j=5,7,…,n-1 forms 4 copies of H_3 ∀ i=2,3,4,5.

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□(□)) ) P_(n-2) )∪E(H_1 )∪E(H_3 )∪E(H_3 )∪E(H_3 )∪E(H_3).

Therefore, by induction hypothesis, L_2m□ P_(n-2) is decomposed into 2(3n-10) copies of K_1,3 and 6n-11 copies of K_1,2. Hence the Subcase (ii) is decomposed into 2(3n-4) copies of K_1,3 and 6n+1 copies of K_1,2. Assume that this Case (iii) is true for m-2.

The induced subgraph <{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1) }> together with the edges 〖{x〗_(i,j-1) x_(i,j),

x_(i,j) x_(i+1,j),x_(i,j+1) x_(i+1,j+1),x_(i+m,j-1) x_(i+m,j)} where j=n-3,n-1 forms 2 copies of H_3 

for all i=m-3,m-2. Thus E(L_2m □(□(□)) P_n )=E(L_(2m-2) □(□(□(□)) ) P_n )∪E(H_3 )∪E(H_3 ).

Therefore, by induction hypothesis, L_(2m-2)□ P_n is decomposed into n(m-3)-2(m-5) copies of K_1,3 and n(m-3)+1 copies of K_1,2. Hence L_2m□ P_n is decomposed into n(m-1)-2(m-3) copies of K_1,3 and n(m-1)+1 copies of K_1,2 in this case.

Therefore, L_2m□ P_n is decomposed into p copies of K_1,3 and q copies of K_1,2.

Theorem 1.8. For any two positive integers m,n with m=3, n≥3 and n is odd, 

L_2m□ P_n is decomposed into p copies of K_1,3, q copies of K_1,2 and one copy of P_4 if 

and only if p+2/3 q=m/3 (5n-4)-(n-1).

 

Let G=L_2m□ P_n where V(G)={x_(i,j):1≤i≤2m;1≤j≤n} and 

E(G)={x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(m,q),x_(r,s) x_(r+m,s):1≤i≤2m;1≤j≤n-1;

1≤k≤m-1,1≤l≤n; 1≤q≤n,1≤r≤m,1≤s≤n}. Suppose that L_2m□ P_n is decomposed into p copies of K_1,3, q copies of K_1,2 and one copy of P_4.

Since |E(G)|=3p+2q+3, 

we have 3p+2q+3=3[n(m-1)+1]+2(mn-2m)+3.

⇒3p+2q+3=5mn-4m-3n+6.

⇒3(p+n-1)+2q=m(5n-4).

Therefore, p+2/3 q=m/3 (5n-4)-(n-1).

Conversely, suppose that p+2/3 q=m/3 (5n-4)-(n-1). We prove this theorem by induction on n. For n=3, the set of edges {x_1,1 x_1,2,x_1,1 x_2,1,x_1,1 x_4,1 },

 

{x_1,3 x_2,3,x_1,3 x_3,3,x_1,3 x_4,3 },{x_3,1 x_1,1,x_3,1 x_3,2,x_3,1 x_6,1 }, {x_3,2 x_1,2,x_3,2 x_3,3,x_3,2 x_6,2 }, {x_5,2 x_5,1,x_5,2 x_5,3 },{x_4,2 x_4,1,x_4,2 x_4,3 }, {x_2,3 x_3,3,x_2,3 x_5,3 } and {x_3,3 x_6,3,x_6,3 x_6,2,x_6,2 x_6,1}

forms 7 copies of  K_1,3, 3 copies of  K_1,2 and one copy of P_4. Therefore L_6□ P_3 is decomposed into 7 copies of K_1,3, 3 copies of K_1,2 and one copy of P_4. For n≥5, we prove this theorem by induction on n. For n=5, the induced subgraph <{x_(i,4),x_(i,5)}> together with the edge x_(i,3) x_(i,4) forms H_1  ∀ 1≤i≤2m. Thus E(L_2m □(□(□)) P_5 )=E(L_2m □(□(□)) P_3)∪E(H_1). Assume that the theorem is true for n-2. The induced subgraph <{x_(i,j),x_(i,j+1)}> together with the edge x_(i,j-1) x_(i,j) where j=4,6,…,n-1 forms H_1  ∀ 1≤i≤2m. 

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□)) P_(n-2))∪E(H_1). Therefore, by induction hypothesis, L_2m□ P_(n-2) is decomposed into 2n-3 copies of K_1,3, 3(n-4) copies of K_1,2 and one copy of P_4.  Also, by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2. Hence L_2m□ P_n is decomposed into p copies of K_1,3, q copies of K_1,2 and one copy of P_4.

Remark 1.9. 

Consider a graph H_4 with V(H_4 )={x_(i,j):1≤i≤3; 1≤j≤3} and

E(H_4 )={x_(i,j) x_(i,j+1),x_(1,l) x_(2,l),x_(1,q) x_(3,q):i=1,3;1≤j≤2;1≤l≤3; 1≤q≤3}.

H_4 is decomposed into 2 copies of K_1,3 and 2 copies of K_1,2 as follows:

{x_1,1 x_1,2,x_1,1 x_2,1,x_1,1 x_3,1 }, {x_1,2 x_2,2,x_1,2 x_1,3,x_1,2 x_3,2 }, {x_1,3 x_2,3,x_1,3 x_3,3 } and {x_3,2 x_3,1,x_3,2 x_3,3 }.

Theorem 1.10. For any two positive integers m,n with m≥3, n≥3 and n is odd, 

L_2m□ P_n is decomposed into p copies of K_1,3, q copies of K_1,2 and one copy of P_4 if 

and only if p+2/3 q=(2m(2n-1))/3-1.

Proof:

Let G=L_2m□ P_n where V(G)={x_(i,j):1≤i≤2m; 1≤j≤n} and 

E(G)={(x_(i,j) x_(i,j+1),x_(k,l) x_(k+1,l),x_(1,q) x_(m,q),x_(r,s) x_(r+m,s) ):1≤i≤2m;1≤j≤n-1;

1≤k≤m-1; 1≤l≤n; 1≤q≤n; 1≤r≤m; 1≤s≤n}. Suppose that L_2m□ P_n is decomposed into p copies of K_1,3, q copies of K_1,2 and one copy of P_4.

Since |E(G)|=3p+2q+3, 

we have 3p+2q+3=3[n(m-1)+(4-m)]+2[(m+3)(n-1)/2+(m-6)]+3.

⇒3p+2q+3=4mn-2m-3.

Therefore, p+2/3 q=(2m(2n-1))/3-1.

Conversely, suppose that p+2/3 q=(2m(2n-1))/3-1.

For n=3, the induced subgraph <{x_(i,j-1),x_(i,j),x_(i,j+1),x_(i+m-1,j-1),x_(i+m-1,j),x_(i+m-1,j+1)}> together with the edges {x_(i,j-1) x_(i+1,j-1),x_(i,j),x_(i+1,j),x_(i,j+1),x_(i+1,j+1)} where j=2 forms m-3 copies of H_(4 )∀ i=3,4,…,m-1.

Thus, E(L_2m □(□(□)) P_3 )=E(L_6 □(□(□)) P_3) ∪[E(H_4 )∪…∪E(H_4 )  (m-3)  ‐times]. Therefore, by Theorem 1.8., L_6 □(□(□)) P_3 is decomposed into 4 copies of K_1,3 and 3 copies of K_1,2. Also, by Remark 1.9., H_4 is decomposed 2(m-3) copies of K_1,2 and 2(m-3) copies of K_1,2.

For n≥5, we prove this theorem by induction on n. For n=5, the induced subgraph 

<{x_(i,4),x_(i,5),x_(m-1,4),x_(m-1,5),x_(m,4),x_(m,5),x_(m+1,4),x_(m+1,5),x_(2m-1,4),x_(2m-1,5),x_(2m,4),x_(2m,5)}> 

together with the edges {x_(i,3) x_(i,4),x_(i+1,4) x_(i,4),x_(i,5) x_(i+1,5),x_(m-1,3) x_(m-1,4),x_(m,3) x_(m,4),x_(m+1,3) x_(m+1,4),

x_(2m-1,3) x_(2m-1,4), x_(2m,3) x_(2m,4)} forms H_1 ∀ 1≤i≤2m. Also, the induced subgraph 

<{x_(i,4),x_(i,5),x_(i+m,4),x_(i+m,5) }> together with the edges 〖{x〗_(i,3) x_(i,4),x_(i,4) x_(i+1,4) x_(i,5) x_(i+1,5),

x_(i+m,3) x_(i+m,4)} forms (m-3) copies of  H_3 ∀ i=2,3,…,m-2.

Thus E(L_2m □(□(□)) P_5 )=E(L_2m □(□(□(□)) ) P_3 )∪E(H_1 )∪[E(H_3 )∪…∪E(H_3 )(m-3)  ‐times]

Assume that the theorem is true for n-2. The induced subgraph <{x_(i,j),x_(i,j+1),x_(m-1,j),

x_(m-1,j+1),x_(m,j),x_(m,j+1),x_(m+1,j),x_(m+1,j+1),x_(2m-1,j),x_(2m-1,j+1),x_(2m,j),x_(2m,j+1)}> together with the edges {x_(i,j-1) x_(i,j),x_(i+1,j) x_(i,j),x_(i,j+1) x_(i+1,j+1),x_(m-1,j-1) x_(m-1,j),x_(m,j-1) x_(m,j),x_(m+1,j-1) x_(m+1,j),

x_(2m-1,j-1) x_(2m-1,j),x_(2m,j-1) x_(2m,j)} where j=6,8,…,n-1 forms H_1 ∀ 1≤i≤2m.

Also, the induced subgraph <{x_(i,j),x_(i,j+1),x_(i+m,j),x_(i+m,j+1) }> together with the edges 

〖{x〗_(i,j-1) x_(i,j),x_(i,j) x_(i+1,j),x_(i,j+1) x_(i+1,j+1),x_(i+m,j-1) x_(i+m,j)} where j=6,8,…,n-1 forms m-3 copies of H_3 ∀ i=2,3,…,m-2.

Thus E(L_2m □(□(□)) P_n )=E(L_2m □(□(□(□)) ) P_(n-2) )∪E(H_1 )∪[E(H_3 )∪…∪E(H_3 )  (m-3)  ‐times].

Therefore, by induction hypothesis, L_2m□ P_(n-2) is decomposed into (n-2)(m-1)+(4-m) copies of K_1,3,  ((m+3)(n-3))/2+(m-6) copies of K_1,2  and one copy of P_4.

 

Also, by Remark 1.1., H_1 is decomposed into 4 copies of K_1,3 and 6 copies of K_1,2.

 And also, by Remark 1.4., H_3 is decomposed into 2(m-3) copies of K_1,3 and (m-3) copies of K_1,2. Hence L_2m□ P_n is decomposed into p copies of K_1,3, q copies of K_1,2 and one copy of P_4.

Theorem 1.11. For any two positive integers m,n with m≥3, n≥2 and n is even, L_2m◉ P_n is decomposed into p copies of K_1,3+e if and only if p=mn.

 

Let G=L_2m◉ P_n. Let V( L_2m )={u_i,v_i:1≤i≤m}, where u_i is the pendant vertex adjacent to v_i. Let V(G)={u_i,v_i,u_(ijˈ),v_(ijˈ):1≤i≤m; 1≤j≤n}, where u_(i1ˈ),u_(i2ˈ),…,u_(inˈ) are the vertices in the copy of the path corresponding to each u_i and v_(i1ˈ),v_(i2ˈ),…,v_(inˈ) are the vertices in the copy of the path corresponding to each v_i. Suppose that G is decomposed into p copies of K_1,3+e.

Since |E(G)|=4p, 

we have 4p=4mn.

Therefore, p=mn.

Conversely, suppose that p=mn.

Now, the induced subgraph <{u_(i1ˈ),u_(i2ˈ),u_i,v_i }> ≅ K_1,3+e ∀ 1≤i≤m. The induced subgraph <{u_(i(j-1)ˈ),u_(ijˈ),u_i }> together with the edge u_(i(j-2)ˈ) 〖 u〗_(i(j-1)ˈ), where j=4,6,…,n forms K_1,3+e ∀ 1≤i≤m. Also, the induced subgraph <{v_((i-1)1ˈ),v_((i-1)2ˈ),v_(i-1),v_i }> ≅ K_1,3+e ∀ 2≤i≤m. The induced subgraph <{v_(i(j-1)ˈ),v_(ijˈ),v_i }> together with the edge v_(i(j-2)ˈ) 〖 v〗_(i(j-1)ˈ), where j=4,6,…,n forms K_1,3+e ∀ 1≤i≤m. And also, the induced subgraph <{v_(m1ˈ),v_(m2ˈ),v_m,v_1 }> ≅ K_1,3+e. The induced subgraph 

<{v_(mjˈ),v_(m(j-1)ˈ),v_m }> together with the edge v_(m(j-2)ˈ) 〖 v〗_(m(j-1)ˈ), where j=4,6,…,n forms K_1,3+e. Thus E(G)=[E(K_1,3+e)∪E(K_1,3+e)∪…∪E(K_1,3+e)  mn ‐times]. Hence L_2m◉ P_n is decomposed into p copies of K_1,3+e.

Corollary 1.12. For any two positive integers m,n with m≥3, n≥2 and n is even, 

H_m◉ P_n is decomposed into p copies of K_1,3+e and one copy of S_m if and only if

 p=mn+n/2.

Theorem 1.13. For any two positive integers m,n with m≥3, n≥3 and n is odd,

 L_2m◉ P_n is decomposed into p copies of K_1,3+e and q copies of K_1,2 if and only if 

 2p+q=2m.

 

Let G=L_2m◉ P_n. Let V( L_2m )={u_i,v_i:1≤i≤m}, where u_i is the pendant vertex adjacent to v_i. Let V(G)={u_i,v_i,u_(ijˈ),v_(ijˈ):1≤i≤m,1≤j≤n}, where u_(i1ˈ),u_(i2ˈ),…,u_(inˈ) are the vertices in the copy of the path corresponding to each u_i and v_(i1ˈ),v_(i2ˈ),…,v_(inˈ) are the vertices in the copy of the path corresponding to each v_i. Suppose that G is decomposed into p copies of K_1,3+e and q copies of K_1,2.

Since |E(G)|=4p+2q, 

we have 4p+2q=4m(n-1)+2(2m).

⇒4p+2q=4mn.

Therefore, 2p+q=mn.

Conversely, suppose that 2p+q=mn.

Now, the induced subgraph <{u_(i1ˈ),u_(i2ˈ),u_i,v_i }> ≅ K_1,3+e ∀ 1≤i≤m. The induced subgraph <{u_(i(j-1)ˈ),u_(ijˈ),u_i }> together with the edge u_(i(j-2)ˈ) 〖 u〗_(i(j-1)ˈ), where j=4,6,…,

n-1 forms K_1,3+e ∀ 1≤i≤m. The induced subgraph <{u_(i(n-1)ˈ) u_(inˈ),〖〖 u〗_(inˈ) u〗_i }> ≅ K_1,2  ∀ 1≤i≤m. Also, the induced subgraph <{v_((i-1)1ˈ),v_((i-1)2ˈ),v_(i-1),v_i }> ≅ 

K_1,3+e ∀ 2≤i≤m. The induced subgraph <{v_(ijˈ),v_(i(j-1)ˈ),v_i }> together with the edge v_(i(j-2)ˈ) 〖 v〗_(i(j-1)ˈ), where j=4,6,…,n-1 forms K_1,3+e ∀ 1≤i≤m. The induced subgraph <{v_(i(n-1)ˈ) v_(inˈ),〖〖 v〗_(inˈ) v〗_i }> ≅ K_1,2  ∀ 1≤i≤m. And also, the induced subgraph 

<{v_(m1ˈ),v_(m2ˈ),v_m,v_1 }> ≅ K_1,3+e. The induced subgraph <{v_(mjˈ),v_(m(j-1)ˈ),v_m }> together with the edge v_(m(j-2)ˈ) 〖 v〗_(m(j-1)ˈ), where j=4,6,…,n-1 forms K_1,3+e. The induced subgraph <{v_(m(n-1)ˈ) v_(mnˈ),〖v_(mnˈ) v〗_m }> ≅ K_1,2. 

Thus E(G)=[E(K_1,3+e)∪E(K_1,3+e)∪…∪E(K_1,3+e)(mn-m)  ‐times]

   ∪[E(K_1,2 )∪E(K_1,2 )∪...∪E(K_1,2 )  2m ‐times].

Hence L_2m◉ P_n is decomposed into p copies of K_1,3+e and q copies of K_1,2.

Corollary 1.14. For any two positive integers m,n with m≥3, n≥3 and n is odd, 

H_m◉ P_n is decomposed into p copies of K_1,3+e, q copies of K_1,2 and one copy of S_m

 if and only if  p+q/2=(n(m+1))/2.

 

The Cartesian product of graphs provides mathematical framework for complex pharmaceutical systems. It helps in predictive modeling and simulation, supports clinical decision making and also it enhances drug safety and treatment efficiency. The corona product of graphs provides a mathematical support for complex therapeutic modeling. It represents hierarchical and modular pharmaceutical systems, supports advanced drug design and clinical research and also it helps in modeling drug targeting and interaction mechanisms.