# Induced Graphoidal Decompositions in Product Graphs

Authors: Mayamma Joseph; I. Sahul Hamid
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

LetG be a nontrivial, simple, finite, connected, and undirected graph. A graphoidal decomposition (GD) of G is a collection ψ of nontrivial paths and cycles in G that are internally disjoint such that every edge of G lies in exactly one member of ψ. By restricting the members of a GD ψ to be induced, the concept of induced graphoidal decomposition (IGD) of a graph has been defined. The minimum cardinality of an IGD of a graph G is called the induced graphoidal decomposition number and is denoted by ηi(G). An IGD of G without any cycles is called an induced acyclic graphoidal decomposition (IAGD) of G, and the minimum cardinality of an
IAGD of G is called the induced acyclic graphoidal decomposition number of G, denoted by ηia(G). In this paper we determine the value of ηi(G)
and ηia(G) when G is a product graph, the factors being paths/cycles.


---

## Body

## 1. Introduction

By a graphG=(V,E) we mean a nontrivial, finite, connected, and undirected graph having no loops and multiple edges. The order and size of graph G are denoted by n and m respectively. For terms not defined here we refer the reader to [1].Adecomposition of G is a collection ψ=(H1,H2,H3,…,Hk) of edge-disjoint subgraphs of G such that every edge of G belongs to exactly one Hi. Graph decomposition problems constitute a major area of research because of their theoretical and practical implications. Designing interconnection networks and drug designing are examples for the application of graph decomposition problems. Among the variants of decompositions of graphs that abound in the literature, path decomposition problems assume a prominent position. Harary [2] introduced the concept of path decomposition of graphs in 1970 which was further studied by Harary and Schwenk [3], Péroche [4], and Stanton et al. [5]. As a special case of path decomposition, Acharya and Sampathkumar [6] introduced the notion of graphoidal decomposition which is a decomposition of a graph into internally disjoint paths/cycles. By imposing the condition that the members of a graphoidal decomposition are induced paths/cycles, Arumugam [7] introduced the concept of induced graphoidal decomposition as well as that of induced acyclic graphoidal decomposition. Studies on these decompositions were initiated by Ratan Singh and Das [8, 9] and were further extended by Sahul Hamid and Joseph [10, 11] by obtaining certain bounds of the related parameters ηi and ηia and solving some characterization problems. In this paper we determine the value of ηi and ηia for a class of product graphs, namely, products of paths and cycles.


## 2. Induced Graphoidal Decomposition

The concept of graphoidal cover (we say graphoidal decomposition) introduced by Acharya and Sampathkumar [6] is defined as follows.Definition 1 (see [6]).
Agraphoidal decomposition (GD) of a graph G is a collection ψ of non-trivial paths and cycles of G such that(i)
every vertex ofG is an internal vertex of at most one member of ψ,(ii)
every edge ofG is in exactly one member of ψ.The minimum cardinality of a GD of a graphG is called the graphoidal decomposition number of G and is denoted by η(G).Note that ifP=(v0,v1,…,vk) is a path, not necessarily open, in a graph G, then v0 and vk are called terminal vertices and v1,v2,…,vk-1 are called internal vertices of P. For cycles (considered as closed paths), there is an inherent “ordering” of vertices as in paths. So, when we say that a cycle C of a graph G is a member of a GD ψ of G, we should mention the vertex at which the cycle C begins, and this particular vertex is considered as the terminal vertex of C and all other vertices on C are called internal vertices of C. Given a GD ψ of G, a vertex v is said to be interior to ψ if v is an internal vertex of an element of ψ and is called exterior to ψ otherwise.As a variation of GD, Arumugam [7] formulated the concept of induced graphoidal decomposition by restricting the members of a GD to be induced paths/cycles.Definition 2 (see [7]).
Aninduced graphoidal decomposition (IGD) of a graph G is a GD ψ of G in which every member of ψ is an induced path/cycle. The minimum cardinality of an IGD of G is called the induced graphoidal decomposition number of G and is denoted by ηi(G) or ηi.Arumugam [7] further defined an induced acyclic graphoidal decomposition (IAGD) of a graph G as a GD of G in which every member is an induced path. The minimum cardinality of an IAGD of G is called the induced acyclic graphoidal decomposition number of G and is denoted by ηia(G) or ηia.The study of the parametersηi and ηia was initiated by Ratan Singh and Das [8, 9] by determining the values of these path-decomposition parameters for families of graphs such as complete graphs, complete bipartite graphs, unicyclic graphs, and bicyclic graphs. Sahul Hamid and Joseph [10, 11] extended this study further and obtained bounds for ηi(G) as well as ηia(G) in terms of the diameter, girth, and maximum degree of a vertex of G and also characterized graphs obtaining these bounds.The following theorem which gives the value ofηi in terms of the size m of a graph G and the maximum number of interior vertices of an IGD of G is useful in determining the value of ηi for a given graph.Theorem 3 (see [10]).
For every IGDψ of a graph G, let tψ denote the number of vertices interior to ψ and let ti(G)=maxtψ, where the maximum is taken over all the IGD ψ of G. Then ηi(G)=m-ti(G).Remark 4.
If there exists an edge-disjoint collection𝒮 of internally disjoint induced paths/cycles of G such that each vertex of G is an internal vertex of some element of 𝒮, then ηi(G)=m-n and vice versa. This is because 𝒮 together with the edges of G not belonging to members of 𝒮 yields an IGD ψ of G with ti(G)=n.We require the following theorem giving the value ofηi for complete graphs.Theorem 5 (see [8]).
For the complete graphKn one has
(1)ηi(Kn)={1,ifn=3,4,ifn=4,m-n,ifn≥6,nis even,m-n+1,ifn≥5,nis odd.The following result is analogous to Theorem3 and is useful in determining ηia(G) for a given graph G.Theorem 6 (see [11]).
For any graphG, ηia(G)=m-tia(G), where tia(G) denotes the maximum number of vertices of G that can be made interior to an IAGD of G.Remark 7.
η
i
a
(
G
)
=
m
-
n if and only if there exists an edge-disjoint collection 𝒮 of internally disjoint induced paths of G such that each vertex of G is an internal vertex of some path in 𝒮.


## 3. Induced Graphoidal Decomposition Number of Products of Paths and Cycles

Given two graphsG and H, their product is a graph whose vertex set is V(G)×V(H)={(g,h):g∈V(G)andh∈V(H)} while the edge set varies according to the nature of the product. Various kinds of graph products are defined in [12]. We consider only the Cartesian product, strong product, and lexicographic product of two paths/cycles. The Cartesian product of graphs G and H denoted by G□H has the edge set E(G□H)={((g,h),(g′,h′)):g=g′,(h,h′)∈E(H)or(g,g′)∈E(G),h=h′}, and the strong product of graphs G and H is denoted by G⊠H with edge set E(G⊠H)={((g,h),(g′,h′)):g=g′,(h,h′)∈E(H);(g,g′)∈E(G),h=h′or(g,g′)∈E(G)and(h,h′)∈E(H)}. The lexicographic product or the composition of graphs G and H is denoted by G∘H where E(G∘H)={((g,h),(g′,h′)):(g,g′)∈E(G)org=g′,(h,h′)∈E(H)}.All through this section and the next, we use the following notations. For positive integersn1 and n2,
(2)Pn1=(u1,u2,u3,…,un1),Pn2=(v1,v2,v3,…,vn2),Cn1=(u1,u2,u3,…,un1,u1),Cn2=(v1,v2,v3,…,vn2,v1).For all the product graphsG we have considered, the vertex set V(G)={wij:1≤i≤n1;1≤j≤n2}, where wij=(ui,vj).First we determine the value ofηi for the Cartesian products of two paths/cycles.Theorem 8.
For the graphG=Pn1□Pn2, where n1,n2≥2, one has
(3)ηi(G)={1,ifn1=n2=2,m-n+2,ifn1=2,n2≥3,m-n,otherwise.Proof.
We haveE(G)={wijwi(j+1):1≤i≤n1;1≤j≤(n2-1)}∪{wijw(i+1)j:1≤i≤(n1-1); 1≤j≤n2}.
Ifn1=n2=2, then G=C4 and obviously ηi(G)=1. When n1=2 and n2≥3, let Q1=(w21,w11,w12,w13,…,w1n2,w2n2), Q2=(w21,w22,w23,…,w2n2) and S′={w1jw2j:2≤j≤(n2-1)}. Then Q1 and Q2 along with the set S′ form an IGD ψ of G with cardinality n2 so that ηi(G)≤|ψ|=n2=m-n+2. Also for any IGD ψ of G, at least one vertex of each of the cycles (w11,w21,w22,w12,w11) and (w1n2,w1(n2-1),w2(n2-1),w2n2,w1n2) will be exterior and therefore ti(G)≤n-2. Hence by Theorem 3 we get ηi(G)≥m-n+2 proving that ηi(G)=m-n+2.
Now, supposen1,n2≥3. Then consider the following paths and cycles:
(4)Q′=(w22,w21,w11,w12,w22),Q1=(w12,w13,…,w1n2,w2n2,…,wn1n2,wn1(n2-1),…,wn11,w(n1-1)1…,w21),Q2=(wn12,w(n1-1)2,…,w32,w22,w23,…,w2n2),Qi=(wi2,wi3,…,win2)foreachi=3,4,5,…,(n1-1).
Then 𝒮={Q′,Q1,Q2,…,Q(n1-1)} is an edge-disjoint collection of internally disjoint induced paths and cycles of G having all the vertices of G as internal vertices of members of 𝒮. Therefore by Remark 4, we have ηi(G)=m-n, thus proving the theorem.Theorem 9.
IfG=Cn1□Cn2, where n1,n2≥3, then ηi(G)=m-n.Proof.
The edge setE(G)={wijwi(j+1):1≤i≤n1;1≤j≤(n2-1)}∪{win2wi1:1≤i≤n1}∪{wijw(i+1)j:1≤i≤(n1-1);1≤j≤n2}∪{wn1jw1j:1≤j≤n2}. Now, let
(5)Q1=(w11,w12,w13,…,w1n2,w11),Q2=(w1n2,w2n2,w3n2,…,wn1n2,w1n2),Q3=(wn1n2,wn1(n2-1),wn1(n2-2),…,wn11,wn1n2),Q4=(wn11,w(n1-1)1,w(n1-2)1,…,w11,wn11),Q5=(wn12,w(n1-1)2,…,w32,w22,w23,…,w2n2),Q(i-2)′=(wi2,wi3,…,win2)foreachi=3,4,…,(n1-1).
Then𝒮={Q1,Q2,…,Q5,Q1′,Q2′,…,Q(n1-3)′} is a collection of induced paths and cycles that are edge-disjoint as well as internally disjoint where each vertex of G is internal to a path/cycle of 𝒮. Hence it follows from Remark 4 that ηi(G)=m-n.Theorem 10.
For the graphG=Pn1□Cn2, where n1≥2,n2≥3, ηi(G)=m-n.Proof.
We haveE(G)={wijwi(j+1):1≤i≤n1;1≤j≤(n2-1)}∪{win2wi1:1≤i≤n1}∪{wijw(i+1)j:1≤i≤(n1-1);1≤j≤n2}. Let
(6)Q1=(w12,w11,w21,w2n2),Q2=(w21,w22,w12,w13,…,w1n2),Q3=(w22,w23,w24,…,w2n2,w1n2,w11),Q′=(w2n2,w3n2,…,wn1n2,wn11),Qj′′=(w2j,w3j,w4j,…,wn1j,wn1(j+1)),j=1,2,…(n2-1).
Then by taking𝒮={Q1,Q2,Q3} when n1=2 and 𝒮={Q1,Q2,Q3,Q′,Q1′′,Q2′′,…,Q(n2-1)′′} for n1≥3 we get the collection of internally disjoint induced paths satisfying the property mentioned in Remark 4 and therefore ηi(G)=m-n.Next we proceed to obtain the value ofηi for the strong product of two paths/cycles.Theorem 11.
LetG=Pn1⊠Pn2 where n1,n2≥2. Then one has
(7)ηi(G)={4,ifn1=n2=2,m-n+1,ifn1=2,n2=3,m-n,otherwise.Proof.
LetE(G)={wijwi(j+1):1≤i≤n1;1≤j≤n2-1}∪{wijw(i+1)j:1≤i≤n1-1;1≤j≤n2}∪{wijw(i+1)(j+1):1≤i≤(n1-1);1≤j≤(n2-1)}∪{wijw(i+1)(j-1):1≤i≤(n1-1);2≤j≤n2}.
The cases whenn1=n2=2, n1=2, and n2=3 can easily be verified.
Supposen1=2 and n2≥4. To prove that ηi(G)=m-n, by Remark 4, it is sufficient to obtain an edge-disjoint and internally-disjoint collection 𝒮 of induced paths and cycles such that every vertex of G is an internal vertex of an element of 𝒮. Let us consider the following cycles and paths of G:
(8)Q1=(w22,w21,w11,w22),Q2=(w2(n2-1),w2n2,w1n2,w2(n2-1)),Q3=(w12,w22,w23,w12),Q4=(w23,w24,w14,w23),Q5=(w1(n2-1),w2(n2-1),w2(n2-2),w1(n2-1)),Q6=(w11,w12,w13,…,w1(n2-1),w1n2),Q7=(w11,w12,w13,w14),Q8=(w23,w24,w25,…,w2(n2-2)).
Ifn2=4, let 𝒮={Q1,Q2,Q3,Q6}; if n2=5, let 𝒮={Q1,Q2,Q3,Q4,Q7}, and when n2≥6, let 𝒮={Q1,Q2,Q3,Q5,Q6,Q8} thus obtaining the required collection 𝒮, proving that ηi(G)=m-n.
Whenn1=n2=3, we consider the collection 𝒮={Q1,Q2,Q3,Q4,Q5} where
(9)Q1=(w22,w21,w11,w22),Q2=(w22,w23,w13,w22),Q3=(w21,w31,w32,w21),Q4=(w32,w33,w22,w32),Q5=(w11,w12,w13).
And for n1≥3 and n2≥4, we consider the following paths and cycles
(10)Q1=(w22,w11,w12,w22),Q2=(w2(n2-1),w1n2,w1(n2-1),w2(n2-1)),Q3=(w(n1-1)2,wn11,wn12,w(n1-1)2),Q4=(w(n1-1)(n2-1),wn1n2,wn1(n2-1),w(n1-1)(n2-1)),Q5=(w11,w21,w31,…,wn11),Q6=(w1n2,w2n2,w3n2,…,wn1n2),Q7=(w12,w13,w14,…,w1(n2-1)),Q8=(wn12,wn13,wn14,…,wn1(n2-1)),Qi-1′=(wi1,wi2,wi3,…,win2)foreachi=2,3,4,…,(n1-1)
to obtain the collection𝒮={Q1,Q2,…,Q8,Q1′,Q2′,…,Q(n1-2)′} mentioned in Remark 4 so that ηi(G)=m-n thus completing the proof of the theorem.Theorem 12.
For the graphG=Cn1⊠Cn2 where n1,n2≥3(11)ηi(G)={m-n+1,ifn1=n2=3,m-n,otherwise.Proof.
We haveE(G)={wijwi(j+1):1≤i≤n1;1≤j≤n2-1}∪{win2wi1:1≤i≤n1}∪{win2w(i+1)1:1≤i≤(n1-1)}∪{wi1w(i+1)n2:1≤i≤(n1-1)}∪{wijw(i+1)j:1≤i≤n1-1;1≤j≤n2}∪{wn1jw1j:1≤j≤n2}∪{w1jwn1(j+1):1≤i≤(n2-1)}∪{wn1jw1(j+1):1≤i≤(n2-1)}∪{wijw(i+1)(j+1):1≤i≤(n1-1);1≤j≤(n2-1)}∪{wijw(i+1)(j-1):1≤i≤(n1-1);2≤j≤n2}∪{w11wn1n2,w1n2wn11}.
Whenn1=n2=3 clearly G=K9, and therefore by Theorem 5, ηi(G)=m-n+1. If n1≥3 and n2≥4, consider
(12)Q1=(w11,w12,w13,…,w1n2,w11),Q2=(w1n2,w2n2,w3n2,…,wn1n2,w1n2),Q3=(wn1n2,wn1(n2-1),wn1(n2-2),…,wn11,wn1n2),Q4=(wn11,w(n1-1)1,w(n1-2)1,…,w11,wn11),Q5=(w11,w22,w23,w11),Q6=(w22,w32,w42,…,wn12),Q7=(w23,w33,w43,…,wn13),Qi-1′=(wi3,wi4,wi5,…,wi(n2-1),win2);2≤i≤(n1-1).
Then𝒮={Q1,Q2,…,Q7,Q1′,Q2′,…,Q(n1-2)′} forms an internally-disjoint and edge-disjoint collection of induced paths and cycles having all the vertices of G as internal vertices. Hence by Remark 4 we have the desired result.Theorem 13.
IfG=Pn1⊠Cn2, where n1≥2 and n2≥3, then ηi(G)=m-n.Proof.
The edge set ofG is given by E(G)={wijwi(j+1):1≤i≤n1;1≤j≤n2-1}∪{win2wi1:1≤i≤n1}∪{win2w(i+1)1:1≤i≤(n1-1)}∪{wi1w(i+1)n2:1≤i≤(n1-1)}∪{wijw(i+1)j:1≤i≤n1-1;1≤j≤n2}∪{wijw(i+1)(j+1):1≤i≤(n1-1);1≤j≤(n2-1)}∪{wijw(i+1)(j-1):1≤i≤(n1-1);2≤j≤n2}.
In this case also, we will show the existence of a collection𝒮 of internally-disjoint and edge-disjoint induced paths and cycles in G such that each vertex of G is an internal vertex of an element of 𝒮 so that by Remark 4, we get ηi(G)=m-n.
Whenn1=2, consider
(13)Q′=(w1n2,w2n2,w11,w1n2),Qj=(w1j,w2j,w1(j+1),w1j)foreachj=1,2,…,(n2-1)
to obtain the desired collection 𝒮={Q′,Q1,Q2,…,Q(n2-1)} of induced cycles. Next we consider
(14)Q1=(w21,w11,w1n2,w21),Q2=(w21,w31,w3n2,w21),Q3=(w12,w21,w32),Q4=(w11,w12,w22,w11),Q5=(w22,w23,w32,w22),Q1′=(w12,w13,…,w1n2),Q2′=(w32,w33,…,w3n2),Q(j-1)′=(w1j,w2j,w3j),foreachj=4,5,…,n2
so that whenn1=n2=3,  𝒮={Q1,Q2,Q3,Q4,Q5} and when n1=3, n2≥4, 𝒮={Q1,Q2,…,Q5,Q1′,Q2′,…,Q(n2-1)′} form the required collection of edge-disjoint and internally-disjoint induced paths/cycles.
Ifn1≥4, we consider
(15)Q1=(w21,w11,w1n2,w21),Q2=(w(n1-1)1,wn11,wn1n2,w(n1-1)1),Q3=(w12,w21,w31,…,w(n1-1)1,wn12),Q4=(w11,w12,w22,w11),Q5=(wn11,wn12,w(n1-1)2,wn11),Q1′=(w12,w13,…,w1n2),Q2′=(wn12,wn13,…,wn1n2),Qj′=(w1j,w2j,…,wn1j),foreachj=3,4,…n2
to obtain the collection 𝒮={Q1,Q2,…,Q5,Q1′,Q2′,…,Qn2′} so that by Remark 4   ηi(G)=m-n, thus completing the proof.Theorem 14.
LetG=Pn1∘Pn2, where n1,n2≥2 such that n2≥n1. Then
(16)ηi(G)={4,ifn1=n2=2,m-n,otherwise.Proof.
We know thatE(G)={wijw(i+1)k:1≤i≤n1-1;1≤j≤n2;1≤k≤n2}∪{wijwi(j+1):1≤i≤n1;1≤j≤(n2-1)}.
Whenn1=n2=2, G=K4, and therefore by Theorem 5, ηi(G)=4. If n1=2 and n2≥3, consider
(17)Qj=(w1j,w2j,w1(j+1),w1j)where1≤j≤(n2-1),Q′=(w2(n2-1),w2n2,w11,w2(n2-1)).
Then the collection𝒮={Q1,Q2,…,Q(n2-1),Q′} of internally-disjoint induced paths and cycles satisfies the property mentioned in Remark 4 and therefore ηi(G)=m-n.
Whenn1,n2≥3, we observe that all the edges of the strong product Pn1⊠Pn2 are included in E(Pn1∘Pn2). Therefore using the same argument as that of Theorem 11 we get ηi(G)=m-n thus completing the proof of the theorem.Theorem 15.
For the graphG=Cn1∘Cn2, where n1,n2≥3 with n2≥n1 one has
(18)ηi(G)={m-n+1,ifn1=n2=3,m-n,otherwise.Proof.
For the given graphG the edge set E(G)={wijw(i+1)k:1≤i≤(n1-1);1≤j≤n2;1≤k≤n2}∪{wijwi(j+1):1≤i≤n1;1≤j≤(n2-1)}∪{wi1win2:1≤i≤n1}∪{w1jwn1k:1≤j≤n2;1≤k≤n2}.
Whenn1=n2=3, G=K9, and therefore by Theorem 5, ηi(G)=m-n+1. If n1≥3 and n2≥4, then the same set 𝒮={Q1,Q2,…,Q7,Q1′,Q2′,…,Q(n1-2)′} we have considered in Theorem 12 is sufficient to prove that ηi(G)=m-n.Remark 16.
The lexicographic product of two graphs is not commutative. Therefore the case whenn1>n2 is to be considered separately. However, using the same argument followed in the previous theorems, it is not difficult to show that ηi(Pn1∘Pn2)=m-n+1 when n1=3 and n2=2 whereas in all other cases ηi(G)=m-n, whether G=Pn1∘Pn2 or G=Cn1∘Cn2.Theorem 17.
LetG=Pn1∘Cn2, where n1≥2 and n2≥3. Then ηi(G)=m-n.Proof.
The edge set ofG is given by E(G)={wijw(i+1)k:1≤i≤(n1-1);1≤j≤n2;1≤k≤n2}∪{wijwi(j+1):1≤i≤n1;1≤j≤(n2-1)}∪{wi1win2:1≤i≤n1}.
This result follows immediately from Theorem13 as the collection of induced paths and cycles considered in the set 𝒮 in various cases there is applicable to the graph G=Pn1∘Cn2 as well.Remark 18.
It can also be proved thatηi(Cn2∘Pn1)=m-n by showing the existence of a collection 𝒮 mentioned in Remark 4.


## 4. Induced Acyclic Graphoidal Decomposition Number of Products of Paths and Cycles

Many of the path decomposition problems in the literature deal with splitting of a graph into paths (and not cycles) with a specified property. Therefore in this section we consider the concept of induced acyclic graphoidal decomposition for product graphs. As seen before, aninduced acyclic graphoidal decomposition (IAGD) of a graph G is an induced graphoidal decomposition ψ where each member of ψ is an induced path. The minimum cardinality of an IAGD of G is called the induced acyclic graphoidal decomposition number of G, and it is denoted by ηia(G).As in the previous section, we determine the value ofηia for nine types of product graphs. We begin with the Cartesian product of two paths.Theorem 19.
For the graphG=Pn1□Pn2 where n1,n2≥2,
(19)ηia(G)={m-n+2,ifn1=2,n2≥2orn1=n2=3m-n+1,ifn1=3or4,n2=4m-n,otherwise.Proof.
Ifn1=n2=2, G=C4, and so, ηia(G)=2=m-n+2. For n1=2 and n2≥3, let Q1=(w11,w21,w22,w23,…,w2n2,w1n2), let Q2=(w11,w12,w13,…,w1n2), and let S′={w1jw2j:2≤j≤(n2-1)}. Then Q1 and Q2 along with the set S′ form an IAGD ψ of G with cardinality n2=m-n+2 so that ηia(G)≤|ψ|=m-n+2. Also for any IAGD ψ of G, one of the vertices w11 and w21 will be exterior and the same is in the case with the vertices w1n2 and w2n2. Therefore, tia(G)—the maximum number of vertices interior to any IAGD of G—is ≤(n-2), and hence by Theorem 6  ηia(G)≥m-n+2 proving the desired result.
The case whenn1=n2=3 also is similar to the previous case where at least two vertices of G will be exterior to any IAGD of G, and, therefore, ηia(G)≥m-n+2 by Theorem 6. Further, the paths
(20)Q1=(w11,w21,w31,w32,w33,w23,w13),Q2=(w11,w12,w13),Q3=(w21,w22,w23)
along with the edges w12w22 and w22w32 form an IAGD of cardinality 5=m-n+2, and hence it follows that ηia(G)=m-n+2.
Next assume thatn1=3 and n2=4. Consider the induced paths Q1, Q2, and Q3, where
(21)Q1=(w11,w21,w31,w32,w33,w34,w24,w14,w13),Q2=(w11,w12,w13,w23),Q3=(w21,w22,w23,w24).
Then the collectionψ1={Q1,Q2,Q3} together with the edges e1=w12w22, e2=w22w32, and e3=w23w33 forms an IAGD ψ of G such that |ψ|=6=m-n+1 proving that ηia≤m-n+1. Also it can be verified that at least one vertex of G is exterior to any IAGD of G, and therefore ηia≥m-n+1 by Theorem 6 thus proving the required result.
Ifn1=4=n2, then as in the previous case any IAGD of G will have at least one vertex exterior to it so that ηia(G)≥m-n+1. Also there exists an IAGD ψ of cardinality 9=m-n+1 consisting of the induced paths Q1,Q2,Q3, and Q4 where
(22)Q1=(w11,w21,w31,w41,w42,w43,w44,w34,w24,w14,w13),Q2=(w11,w12,w13,w23),Q3=(w21,w22,w23,w24),Q4=(w31,w32,w33,w34)
and the edges e1=w12w22, e2=w22w32, e3=w32w42, e4=w23w33, and e5=w33w43 so that ηia≤m-n+1 and hence the result.
Finally, assume thatn1≥3 and n2≥5. Consider the paths
(23)Q1=(w12,w11,w21,…,wn11,wn12,…,wn1n2,w(n1-1)n2,w1n2,w1(n2-1)),Q′=(w22,w12,w13,…,w1(n2-1),w2(n2-1)),Qi=(wi1,wi2,…,win2)foreachi=2,3,…(n1-1).
Then𝒮={Q1,Q2,…,Q(n1-1),Q′} is an edge-disjoint collection of internally-disjoint induced paths of G such that every vertex of G is an internal vertex of some path in 𝒮. Therefore by Remark 7, ηia(G)=m-n.Theorem 20.
IfG=Cn1□Cn2, where n1,n2≥3, then ηia(G)=m-n.Proof.
For the given graph we will show that there exists a collection𝒮 of internally-disjoint and edge-disjoint induced paths such that each vertex of G is internal to a member of 𝒮. If n1=3, let 𝒮={Q1,Q2,Q3,Q4} where
(24)Q1=(w21,w11,w1n2,w3n2,w3(n2-1),…,w32),Q2=(w11,w12,…,w1(n2-1),w2(n2-1),w2n2,w3n2),Q3=(w2(n2-1),w2(n2-2),…,w21,w31,w3n2),Q4=(w31,w32,w23).
Ifn1≥4, let
(25)Q1=(w21,w11,w1n2,wn1n2,wn1(n2-1),…,wn12),Q2=(w11,w12,…,w1(n2-1),w2(n2-1),w2n2,w3n2,…,wn1n2),Q3=(w2(n2-1),w2(n2-2),…,w21,w31,…,wn11,wn1n2),Q4=(wn11,wn12,w(n1-1)2,w(n1-1)3,…,w(n1-1)n2),Qi-1′=(w2j,w3j,…,w(n1-1)j)foreachj=2,3,…,(n2-1).
Then𝒮={Q1,Q2,Q3,Q4,Q1′,Q2′,…,Q(n2-2)′} forms the desired collection of internally-disjoint and edge-disjoint induced paths such that all the vertices of G are internal to some path in 𝒮, and by Remark 7, ηia(G)=m-n.Theorem 21.
IfG=Pn1□Cn2, then ηia(G)=m-n.Proof.
The result follows from Theorem10 and Remark 7 as the collection 𝒮 considered there does not contain any cycle.Theorem 22.
LetG=Pn1⊠Pn2 where n1,n2≥2. Then one has
(26)ηia(G)={6,ifn1=n2=2,m-n+4,otherwise.Proof.
Whenn1=n2=2, the result is immediate as G=K4 which has its edge set as a minimum IAGD as G does not contain any induced paths of length greater than one.
In all other cases it can easily be observed that the verticesw11, w1n1, wn11, and wn1n2 cannot be made interior to any IAGD of G. Therefore tia(G)≤n-4, and hence by Theorem 6, ηia≥m-n+4. Now, let
(27)Qi=(wi1,wi2,…,win2)foreachi=1,2,…,n1,Q′=(w11,w21,…,wn11),Q′′=(w1n2,w2n2,…,wn1n2).
Then the collection of induced paths S1={Q1,Q2,…,Qn1,Q′,Q′′} together with the edges of G not covered by the paths in S1 forms an IAGD ψ such that |ψ|=n1+2(n2-2)(n1-1)+2(n1-1)(n2-1)=m-n+4, proving that ηia(G)≤m-n+4, and this completes the proof of the theorem.Theorem 23.
IfG is the graph Cn1⊠Cn2wheren1,n2≥3, then
(28)ηia(G)={m,ifn1=n2=3,m-n,otherwise.Proof.
Whenn1=n2=3, we have G=K9, and therefore ηi(G)=m as the edge set of G is a minimum IAGD of G.
Ifn1=3 and n2=4, we consider the collection of induced paths 𝒮={(w12,w11,w14), (w22,w21,w24), (w32,w31,w34), (w21,w12,w23), (w31,w22,w33), (w21,w32,w23), (w12,w13,w24), (w22,w23,w34), (w32,w33,w24), (w13,w14,w31), (w23,w24,w31), (w33,w34,w11)} which satisfy the property mentioned in Remark 7, and therefore ηia(G)=m-n in this case.
Ifn1≥3 and n2≥5, we consider the following induced paths:
(29)Qi=(wi2,wi1,win2,wi(n2-1))foreachi=1,2,…,n1,Qi′=(w(i+1)1,wi2,w(i+1)3)foreachi=1,2,…,(n1-1),Q*=(w(n1-1)1,wn12,w(n1-1)3),Qi′′=(w(i+1)(n2-2),wi(n2-1),w(i+1)n2)foreachi=1,2,…,(n1-1),Q**=(w(n1-1)(n2-2),wn1(n2-1),w(n1-1)n2),Qi′′′=(wi2,wi3,…,wi(n2-1))foreachi=1,2,…,n1.
Then the collection 𝒮 of all the paths given previous constitutes an edge-disjoint collection of internally-disjoint induced paths in G such that each vertex of G is internal to some path in 𝒮. Therefore it follows from Remark 7 that ηia=m-n, thus completing the proof.Theorem 24.
LetG=Pn1⊠Cn2 where n1≥2;n2≥3. Then
(30)ηia(G)={m-n+6,ifn2=3,m-n,otherwise.Proof.
Supposen2=3. Then it can be observed that the vertices w11,w12,w13,wn11,wn12 and wn13 cannot be made internal to any induced path of G. Therefore, tia(G)≤(n-6). Further, the three paths Q1={w11,w21,…,wn11}; Q2={w12,w22,…,wn12}, and Q3={w13,w23,…,wn13} together with the edges of G not belonging to the induced paths Q1, Q2, and Q3 form an IAGD of cardinality m-3(n1-1)+3=m-n+6 so that ηia(G)≤m-n+6 thus proving that ηia(G)=m-n+6.
Next assume thatn2≥4. If n1=2, consider the induced paths
(31)Q1=(w12,w11,w1n2),Q2=(w21,w12,w23),Q3=(w22,w21,w2n2),Q4=(w11,w22,w13),Q5=(w21,w1n2,w2(n2-1)),Q6=(w11,w2n2,w1(n2-1)),Q7=(w12,w13,…,w1n2),Q8=(w22,w23,…,w2n2)
so that𝒮={Q1,Q2,…,Q8} is a collection of edge-disjoint and internally-disjoint induced paths such that each vertex of G is an internal vertex of a path in 𝒮. Therefore by Remark 7, ηia(G)=m-n.
Ifn1≥3 and n2≥4, let
(32)Q1=(w12,w11,w1n2),Q2=(w21,w12,w23),Q3=(w21,w1n2,w2(n2-1)),Q4=(wn12,wn11,wn1n2),Q5=(w(n1-1)1,wn12,w(n1-1)3),Q6=(w(n1-1)1,wn1n2,w(n1-1)(n2-1)),Q7=(w12,w13,…,w1n2),Q8=(wn12,wn13,…,wn1n2),Q(j-1)′=(w1j,w2j,…,wn1j)foreachj=2,3,…,n2.
Then𝒮={Q1,Q2,…,Q8,Q1′,Q2′,…,Q(n2-1)′} is a collection of internally-disjoint and edge-disjoint induced paths mentioned in Remark 7 so that ηia(G)=m-n.Theorem 25.
For the graphG=Pn1∘Pn2 where n1,n2≥2 and n2≥n1 one has
(33)ηia(G)={m,ifn1=n2=2,m-n+2,ifn1=2,n2=3,m-n,otherwise.Proof.
Whenn1=n2=2, G=K4, and therefore ηia(G)=m.
Next assume thatn1=2 and n2=3. Then at least two of the vertices w11, w1n2, w21, w2n2 will be exterior to any IAGD of G, and hence ηia≥m-n+2 by Theorem 6. Now, let
(34)Q1=(w11,w21,w13),Q2=(w11,w22,w13),Q3=(w11,w23,w13),Q4=(w21,w12,w23).
Then the collectionψ′={Q1,Q2,Q3,Q4} along with the edges of G not covered by the paths in ψ′ forms an IAGD of cardinality m-n+2, and hence it follows that ηia=m-n+2.
Ifn1=2 and n2≥4, then we get a collection 𝒮 of induced paths given by 𝒮={Q1,Q2,…,Q6} which satisfies the condition mentioned in Remark 7 by considering the following paths:
(35)Q1=(w21,w11,w23),Q2=(w22,w1n2,w2n2),Q3=(w12,w21,w14),Q4=(w11,w2n2,w13),Q5=(w11,w12,…,w1n2),Q6=(w21,w22,…,w2n2).
Thus we have ηia(G)=m-n. Next assume that n1=3 and n2≥3. In this case let us consider the paths
(36)Q1=(w21,w11,w2n2),Q2=(w21,w1n2,w2n2),Q3=(w21,w31,w2n2),Q4=(w21,w3n2,w2n2),Q5=(w12,w21,w32),Q6=(w12,w2n2,w32),Qi′=(wi1,wi2,…,win2)foreachi=1,2,3.
Then 𝒮={Q1,Q2,…,Q6,Q1′,Q2′,Q3′} is an internally-disjoint and edge-disjoint collection of induced paths in G such that each vertex of G is internal to some path in 𝒮 and so by Remark 7, ηia=m-n. Finally, when n1,n2≥4, consider the induced paths following:
(37)Q1=(w21,w11,w2n2),Q2=(w21,w1n2,w2n2),Q3=(w(n1-1)1,wn11,w(n1-1)n2),Q4=(w(n1-1)1,wn1n2,w(n1-1)n2),Q5=(w12,w21,w31,…,w(n1-1)1,wn12),Q6=(w1(n2-1),w2n2,w3n2…,w(n1-1)n2,wn1(n2-1)),Qi′=(wi1,wi2,…,win2)foreachi=1,2…,n1.
Then 𝒮={Q1,Q2,…,Q6,Q1′,Q2′…,Qn1′} is the collection satisfying the condition mentioned in Remark 7 so that ηia(G)=m-n, and this completes the proof of the theorem.Theorem 26.
For the graphG=Cn1∘Cn2 where n1,n2≥3 and n2≥n1(38)ηia(G)={m,ifn1=n2=3,m-n,otherwise.Proof.
Whenn1=n2=3, G is a complete graph on nine vertices, and therefore ηia(G)=m. Suppose n1≥3 and n2≥4. Consider the induced paths
(39)Qi=(wi2,wi1,win2)foreachi=1,2,…,n1,Qi′=(wi2,wi3,win2)foreachi=1,2,…,n1,Qi′′=(w(i+1)1,wi2,w(i+1)3)foreachi=1,2,…,(n1-1),Qi′′′=(w(i+1)(n2-2),win2,w(i+1)n2)foreachi=1,2,…,(n1-1),Q*=(w(n1-1)1,wn12,w(n1-1)3),Q**=(w(n1-1)1,wn1n2,w(n1-1)3).
Then𝒮={Q1,Q2,…,Qn1,Q1′,Q2′,…,Qn1′,Q1′′,Q2′′,…,Q(n1-1)′′,Q1′′′,Q2′′′,…,Q(n1-1)′′′,Q*,Q**} is a collection of induced paths that are edge-disjoint and internally-disjoint such that each vertex of G is an internal vertex of some path in 𝒮. Therefore by Remark 7, ηia(G)=m-n.Remark 27.
Since the lexicographic product of two graphs is not commutative, the case whenn1>n2 is to be considered separately. However, in this case using the same argument followed in Theorems 25 and 26 we get ηia(Pn1∘Pn2)=m-n+4 when n1=2 and ηia(Pn1∘Pn2)=m-n otherwise. Also, ηia(Cn1∘Cn2)=m-n when n1>n2.Theorem 28.
LetG=Pn1∘Cn2 where n1≥2 and n2≥3. Then
(40)ηia(G)={m-n+6,ifn2=3,m-n,otherwise.Proof.
The result follows from Theorem24 as Pn1∘C3=Pn1⊠C3, and all the induced paths considered in Theorem 24 to obtain the collection 𝒮 mentioned in Remark 7 are induced paths in Pn1∘Cn2 as well.Remark 29.
For the graphG=Cn1∘Pn2, it can easily be shown that ηia(G)=m if n1=3 and n2=2 and ηia(G)=m-n in all other cases.


## 5. Scope for Further Research

Given any graphG, the lower bound for ηi as well as ηia is m-n. This is because the maximum value that ti(G) and tia(G) can take is n. It has been found in [10, 11] that the families of graphs for which this lower bound is attained are very large. In this study on product graphs, we observe that ηi and ηia attain the bound m-n for several product graphs. Therefore, the present study leads us to problems like the following that need further investigation.(i)
Characterize the product graphs for whichηi=m-n.(ii)
Characterize the product graphs for whichηia=m-n.(iii)
Characterize the product graphs for whichηi=ηia=m-n.



---

*Source: 892839-2013-02-20.xml*