IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 52 (2014), 1194
ISSN 2232-2094
THE k-PATH VERTEX COVER OF ROOTED PRODUCT GRAPHS
Marko Jakovac
Ljubljana, February 18, 2014
The k-path vertex cover of rooted product graphs
Marko Jakovaca'b
a University of Maribor, Faculty of Natural Sciences and Mathematics, Koroska cesta
160, SI-2000 Maribor, Slovenia bInstitute of Mathematics, Physics and Mechanics, Jadranska 19, SI-1000 Ljubljana,
Slovenia,
fc _
Abstract
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by —k(G) the minimum cardinality of a k-path vertex cover in G. In this article a lower and an upper bound for —k of the rooted product graphs are presented. Two characterizations are given when those bounds are attained. Moreover —2 and —3 are exactly determined. As a consequence the independence and the dissociation number of the rooted product are given.
Keywords: k-path vertex cover, vertex cover, independence number, dissociation number, rooted product 2010 MSC: 05C15, 05C38, 05C69
00 -
CM
1. Introduction and preliminaries
Let G be a simple, undirected graph. For a positive integer k > 2 the
CO
subset S Ç V(G) is a k-path vertex cover of G, if every path of order k in graph G contains a vertex from S. The set S is also called the set of covered vertices in a k-path vertex cover of G and we call T = V (G) — S the set of uncovered vertices. The cardinality of a minimum k-path vertex cover is denoted by — k (G).
The motivation for this invariant was introduced in [4] and arises from communications in wireless sensor networks, where the data integrity is ensured by using the Novotny's k-generalized Canvas scheme [15]. There are many other motivations, for instance in traffic control as presented in [20].
Gï
CO
CO CD
$H
CD CO
u
a
CD U
Email address: marko.jakovac@uni-mb.si (Marko Jakovac) Preprint submitted, to Elsevier	February 17, 2014
CM	, ,
The problem of computing (G) is in general NP-hard for each k > 2, but it was also shown that it is polynomial for trees. In [19, 20, 21] some approximation algorithms for 03(G) were derived and in [13] an exact algorithm for computing 03(G) in running time 0(1.5171"") for a graph of order n was presented.
The k-path vertex cover is a generalization of the vertex cover. It is easy to see that 02(G) equals the size of a minimum vertex cover. Moreover
&
"02(G) = | V(G)| — a(G),
where a(G) denotes the maximum stable set and is called the independence number of G. This gives an interesting connection to the well studied independence number [10, 11, 22, 18].
The value of ^(G) is in close relation to the concept of the dissociation number of a graph [23]. A subset of vertices in a graph G is called a dissociation set if it induces a subgraph with maximum degree at most 1. The number of vertices in a maximum cardinality dissociation set in G is called the dissociation number of G and is denoted by diss(G). The relation between ^(G) and diss(G) is
Gï
fi
03(G) = |V(G)| — diss(G).
i
CM	Determining the dissociation number of a graph is NP-hard in the class of
bipartite graphs [23]. The dissociation number problem was also studied in several other articles [1, 2, 5, 9]. This results were also united in a survey, see [16].
Recently, in [3] some results on d-regular graphs were presented. For instance for an arbitrary integer k > 2 and a d-regular graph G, d > k — 1, it follows that
d — k + 2 0k <G) > ¿-r+2 iv <g".
The concept of the k-path vertex cover was also studied in different graph products. In [3] the exact value for 03 was determined for the Cartesian product of paths. Also, some bounds for the same products were determined for . These bounds were later improved in [12] and extended to the strong product of paths. In the same article [12] some results for the lexicographic product were presented, which were the first results in graph products for arbitrary graphs. A good lower and upper bound for the lexicographic product
CO
00 CM CM
CO CO
CO CD
■ i-H
u
u
a
CD U
00 1—1
b
u
CD
0 o
CM
1
CM CO CM CM
£ CO CO
of arbitrary graphs was given and the exact value for and was determined. As a consequence, the independence and the dissociation number of the lexicographic product were derived. Those results imply a well-known result of Geller and Stahl [7] who determined the independence number of the lexicographic product.
We continue our research in the rooted product which is closely related to the Cartesian product. The rooted product of graphs was studied in many occasions, see for instance [6, 8, 14, 17, 24]. Since no results for the k-path vertex cover in the Cartesian product of arbitrary graphs were presented it would be interesting to see if some general results can be derived in the rooted product of graphs.
Figure 1: The rooted product C3 o P4
Let V (G) = (gi, g2,... gm} and V (H) = (hi ,h2,...hn}. We chose a vertex from V(H) to be the root vertex of H, say h1. The rooted product G o H of graphs G = (V(G), E(G)) and H = (V(H), E(H)) has the vertex set
V (G o H ) = ((gi, hj) | i e(1,...,m},j e(1,...,n}} ,
and the edge set
m
CD
$H
CD
m
E(GoH) = ((gi, hi)(gfc, hi) | g,gk e E(G)} U U((gi, hj)(gi, hk) | hjhk e E(H)} .
i=1
If G is also rooted at g1, one can view the product itself as rooted at (g1, h1). The rooted product is a subgraph of the Cartesian product of the same two graphs.
Let G and H be arbitrary graphs and H rooted at h. We refer to the set V(G) x {h} as the G-layer of graph G o H. Similarly, for any vertex u e V(G), the set (u} x V(H) is an H-layer. Note that there is only one
U
a
CD U
m
G-layer, but there might be many H-layers. Layers can also be regarded as the graphs induced on the sets that define them. Obviously, in the rooted product the G-layer and an H-layer are isomorphic to G and H, respectively. An example of the rooted product C3 o P4, where P4 is rooted at an inner vertex, can be seen in Figure 1.
Since the main motivation for the k-path vertex cover is securing networks with as few sensors as possible one can view the rooted product as a combination of many local networks (copies of graph H) having a server (the root vertex of graph H). These servers are connected between each other through a global network (the graph G). Hence, we get another motivation why it is interesting to study the k-path vertex cover of rooted product graphs.
2. Main results
We start this section with the following results of a lower and upper bound of (GoH). Note that in the figures the vertices which belong to the k-path vertex cover S are colored black.
CD
o
CM CM
Proposition 2.1. Let G and H be arbitrary connected graphs and H rooted at any vertex h G V(H). Then
|V(G)|^(H) < ^(G o H) < |V(G)|^(H)+ ^(G).
CM
Proof. We need at least (H) covered vertices in every H-layer of graph G o H. The number of such layers is |V(G)| therefore the lower bound of ik(G o H) is |V(G)|1fc(H).
For the upper bound we construct a k-path vertex cover of graph G o H. Let Si be a minimum k-path vertex cover of graph H and S2 a minimum 2-path vertex cover (i.e. vertex cover) of graph G. If every H-layer is covered in the same way that S1 covers graph H and the G-layer in covered the same way that S2 covers graph G then the size of the minimum k-path vertex cover of graph G o H is at most
|V (G)|
L |Si| I + |S2| \ i=1
CD
Suppose this is not true. Then we have a path of order k in G o H which is not covered. If such a path lies in more than one H-layer then there exist two
U
a
CD U
adjacent vertices on this path that lie in the G-layer of graph G o H. Hence, we have two adjacent vertices in the G-layer that are not covered. This is a contradiction since S2 is a vertex cover of graph G. Therefore, this path lies completely in one of the H-layers which is also a contradiction since Si is a k-path vertex cover of graph H. Hence
/ |V (G)| \
A (G o H) < £ |Si| + IS2I \ i=i /

o
o
CM
u
a
CD U
= \ V(G)||Si| + |S2| = \ V(G) \A(H) + A2(G).
Having proved Proposition 2.1 it would be interesting to know when both bounds are achieved. For the sake of this we introduce the following definition.
Definition 2.1. Let h E V(H). If there exists a minimum k-path vertex cover S of graph H, i.e. |S| = (H), such that h E S, then we call vertex h a kPVC-perfect vertex.
As an example (Figure 2), we take the path Pk+1 = v^2v3 ... vkvk+1 for which (Pk+1) = 1. It is easy to see that all vertices except v1 and vk+1 are kPVC-perfect vertices.
CO
o-•-o-----o-o
o-o-•-----o-o
-o
V1 V2 V3	Vk Vk+1
Figure 2: The path Pk+1 with all possibilities for the kPVC-perfect vertex
With the help of Definition 2.1 we can give a sufficient condition when the lower bound in Proposition 2.1 is achieved.
Theorem 2.1. Let G and H be arbitrary connected graphs , graph H rooted at h e V(H), and A(G) = 0. Then
Ak(G O H) = \ V(G)\Ak(H)
CD
if and only if h is a kPVC-perfect vertex.
CD
CM	/ ^
Proof. Suppose that h G V(H) is a kPVC-perfect vertex. Then there exists a minimum k-path vertex cover S of graph H such that h G S. We construct a k-path vertex cover of graph G o H in such way that we cover every H-layer in the same way that S covers graph H. In this sense, vertices (gi5 h), i G {1,..., |V(G) |}, are covered since the vertex h is a kPVC-perfect vertex. Hence, the G-layer is completely covered and there is no uncovered path of order k in the G o H having some of its vertices in the G-layer. Also, since S is a k-path vertex cover of H there is not path of order k in any H-layer. Hence.
tk(G o H) < |V(G)||S| = |V(G)|tk(G).
According to Proposition 2.1 this upper bound is also the lower bound of tk(G o H) and therefore
i-H	tk(G o H) = |V(G)|tk(H).
For the converse, suppose that tk(G o H) = |V(G)|tk(H). Let S be a minimum k-path vertex cover of graph G o H and Sj, i G {1,..., |V(G) |}, the set of vertices of S that lie in Hj-layer. Hence,
lV (G)l |S| = £ |Sj| • CM	j=i
If |Sj| >tk(H), i G {1,..., |V(G)|}, then
|V(G)|	|V(G)|
|S| = J] |Sj| >Y, tk(H) = |V(G)|tk(H) i=1 i=1
CM CM
S CO CO
CO CD
■ i-H
u
CD
which is a contradiction. Therefore, S = tfc(H), for any i G {1,... , | V(G)|}. Suppose that h is not a kPVC-perfect vertex. Then h does not lie in any minimum k-path vertex cover of graph H. Set Sj, i G {1,..., |V(G)|}, is a minimum k-path vertex cover of the H-layer, i G {1,..., |V(G)|}. Since h is not a kPVC-perfect vertex, (g, h) / Sj, for all i G {1,... , | V(G)|}. Moreover, (g, h) / S, for all i G {1,..., |V(G)|}. This means that the G-layer of graph G o H, which is isomorphic to graph G, is completely uncovered. This is a contradiction since one of the assumptions states that tfc (G) = 0. Hence, h is a kPVC-perfect vertex.	□
Remark 2.1. The assumption tfc(G) = 0 in Theorem 2.1 is only needed to prove one implication. Hence, when h is a kPVC-perfect vertex it always
holds that tfc(G o H) = |V(G)|tfc(H), even if tfc(G) = 0.
a
CD
With the help of Theorem 2.1 and Remark 2.1 we can prove the following nice results.
Proposition 2.2. Let G and H be arbitrary connected graphs and H rooted at h £ V(H). If h is not a kPVC-perfect vertex then
that (G) = 0. By Theorem 2.1 we know that ^k(GoH) > |V(G)|^k(H) + 1. We can show more, namely that (G o H) > |V(G)|^k(H) + (G). If H is the vertex graph this bound is trivial, since (G o H) = (G) and ^k(H) = 0. Let H be different then the vertex graph, the root vertex h = hi, S a minimum k-path vertex cover of graph G o H, Si = {(gi,hj) £ S | j £ {2,..., | V (H )|}, i £ {1,..., |V (G) |}, and S' = {(gi,hi) £ S | i £ {1,..., |V(G)|}. It is obvious that
Qï
u
a
CD U
^(G O H) > |V(G)|^(H)+ ^(G). Proof. If (G) = 0, the result is the same as in the Proposition 2.1. Suppose
|V (G)|
IS I = ISiM + IS'!
i=1
Since h = hi is not a kPVC-perfect vertex, every minimum k-path vertex cover of H does not contain vertex h. If IS| = (H) — 1, for some i, then SiU {(gij hi)} is a minimum k-path vertex cover of graph induced by the Hi-layer,
CM
and hence h = hi is a kPVC-perfect vertex, which is not possible. Hence, |Si| > ^k(H), for all i £ {1,..., |V(G)|}. Also, |S'| > ^k(G). Therefore,
/|V (G)| \
IS I = E N + |S'|
Vi=i /
/|V (G)|
>
Ik(HH + Ik(G)

i=1
= |V(G)||(H)+ |(G),
and the proof is complete.	□
Corollary 2.1. Let G and H be arbitrary connected graphs and H rooted at h £ V(H). Then
CD
I (G H) = / IV(G)||2(H)	; h is a kPVC-perfect vertex
^2(G O h ) = j |v(g)||2(h) + 12(G) ; h is not a kPVC-perfect vertex '
o
CM 00

m
CD
■ l-H
u
CD
Proof. If G is the vertex graph then (G) = 0. It follows that
^(G O H) = ^(H) = |V(G)|^(H) = |V(G)|^(H) + ^(G)
and both results coincide no matter weather h is kPVC-perfect or not.
Suppose now that G is different from the vertex graph. Since G is connected, "2(G) = 0. By Theorem 2.1 ^(G o H) = |V(G)|^(H) if and only if h is a kPVC-perfect vertex. If h is not a kPVC-perfect vertex then by Proposition 2.2 it follows that
|V(G)|^(H)+ "2(G) < "02(G O H) < |V(G)|^(H)+ "2(G),
and hence, 02(G o H) = |V(G)|02(H) + "2(G).	□
Corollary 2.2. Let G and H be arbitrary connected graphs and H rooted at h G V(H). Then
(G h) = / |V(G)|a(H)	; h is a kPVC-perfect vertex
a(GoH) = \ |V(G)|(a(H) - 1) + a(G) ; h is not a kPVC-perfect vertex
Proof. By Corollary 2.1 the result follows immediately. First, suppose that h is a kPVC-perfect vertex. Then
a(G o H) = |V(G o H)| — ^(G o H)
CN	= |V (G)||V (H)| —|V (G)|^(H)
= |V (G)|(|V (H )|— ^(H )) = |V(G)|a(H).
If h is not a kPVC-perfect vertex, then
CO
a(G o H) = |V(G o H)| — ^(G o H)
= |V (G)||V (H )| —|V (G)|^(H ) — "02 (G) = |V (G)||V (H)| — |V (G)|"2(H ) — |V (G)| + |V (G)| — "2(G) = |V (G)|(|V (H)| — "2(H) — 1) + |V (G)| — "2(G) = |V(G)|(a(H) — 1) + a(G).
□
The assumption (G) = 0 which is used in Theorem 2.1 and later in the proof of Proposition 2.2 is connected to the fact weather the root vertex is a
kPVC-perfect vertex or not. We can derive the following corollary.
8
• 1
00 1—1
b
u
CD
0 o
CM
1
CM CO CM CM
£ CO CO
Corollary 2.3. Let G and H be arbitrary connected graphs and H rooted at vertex h e V(H). If (G o H) = |V(G)|^fc(H) then h is a kPVC-perfect vertex or (G) = 0.
Proof. Suppose (G o H) = |V(G)|^k(H). If (G) = 0, we are done. We may therefore assume that (G) = 0. By Theorem 2.1 vertex h is a kPVC-perfect vertex.	□
Even though Corollary 2.3 is almost the same then Theorem 2.1, it is important to know that the converse in Corollary 2.3 is not true. If h is not a kPVC-perfect vertex and (G) = 0, then the equality (G o H) = |V(G)|^fc(H) does not necessary hold. Take for example k > 3, G = Pk-1 = U\U2 ... uk-1 and H = P2k-1 = v1v2 ... v2k-1 rooted at v1. It is clear that (G) = 0. Also, it is easy to see that (H) = 1 and v1 is not a kPVC-perfect vertex. There is a unique way how to cover each H-layer with the k-path vertex cover of the size (H) = 1. However, such a cover is not a k-path vertex cover for the whole graph G o H since it is easy to find a path on k vertices which is not covered (see Figure 3). Hence, (G o H) > | V (G)|^ (H ) = | V (G)|.
(m,,V,) (M2,V,) («3,V,)
9-9-
("i-lVl)
(M1,V2) (M2,V2) (1<3,V2)	(Mt-I,v2)
Î f Î t
|("1>vt) ^«2,Vt) ^(«3>Vt> ^(«t-lV)
Figure 3: The graph Pk-1 o P2fc-i rooted at (wj, vi), « G {1,..., k — 1}
CO CD
Jh
CD CO
We continue our observation by finding some conditions for which the value (G o H) would equal the lower bound in Proposition 2.2 and the upper bound in Proposition 2.1. For both cases we introduce some new definitions.
Let h G V(H) be a vertex that is not a kPVC-perfect vertex. We may refer to such a vertex as the kPVC-imperfect vertex. Then we know that h / S, for any minimum k-path vertex cover S. Therefore, h G T = V(H) — S,
U
a
CD U
where T is the set of uncovered vertices. Then vertex h lies in some paths Pi, for some i £ {1,...,k — 1}, having h as one of its end-vertices, and consisting only of the vertices of the set T. There always exists at least one such path, namely the path Pi on vertex h. Let P(H : S : h) be the set of all such paths. It is clear that the set depends on graph H, a minimum k-path vertex cover S, and kPVC-imperfect vertex h. To be consistent, we define P(H : S : h) = 0 if h is a kPVC-perfect vertex. Also note, that P(H : S : h) is not a multiset, which means that we do not repeat the elements in the set,
e.g. {P3, P3} = {P3}.

GÏ O CM
CM
£ CO CO
CD
u
CD
Proposition 2.3. Let H be a graph, S a minimum k-path vertex cover of H, and h £ V(H). Then
0 < |P (H : S : h)| = max{i | P £ P (H : S : h)} < k - 1.
Proof. Let H be a graph and S a minimum k-path vertex cover of H. If h is a kPVC-perfect vertex, then |P(H : S : h)| = |0| =0. Let h be a kPVC-imperfect vertex and Pi = vi(= h)v2... vl be the path with the maximum order in the set P (H : S : h). Then also the paths Pl-1 = v1(= h)v2 ... vl-1, Pi-2 = Vi(= h)v2 ... vi-2, ..., P2 = Vi(= h)v2, Pi = vi(= h) are all in P(H : S : h). Since we do not repeat the elements in the set, |P(H : S : h)| = l. Also, all paths are of order strictly less than k, therefore l < k — 1.	□
CM
With the help of Proposition 2.3 we can define for any graph H the following concept.
Definition 2.2. Let H be a graph and h £ V(H). If
q = min{|P(H : S : h)| | S is a minimum k-path vertex cover of H} then we refer to the vertex h as the q-kPVC-imperfect vertex.
For the kPVC-perfect vertex the Definition 2.2 implies that such a vertex is a 0-kPVC-imperfect vertex. To understand the Definition 2.2 we give an example presented in Figure 4. Take again the graph P2k-1. There is a unique way how to cover graph P2k-1 with a k-path vertex cover S of size (P2k-1) = 1. Namely, vertex vk must be covered. All other vertices are kPVC-imperfect vertices. Hence, P(H : S : v1) = {P1; P2,..., Pk-1}, and since S is a unique minimum k-path vertex cover, it follows that q = |P(H :
S : vi)| = k — 1. Therefore, vi is a (k — 1)-kPVC-imperfect vertex. In
00 1—1
CD
CM
i
CD
U
CD
Vl V2	Vk-1 Vk Vk+1 V2k-2 V2k-1
Figure 4: The path P2fc-i with vk as the only kPVC-perfect vertex
general, for every Vj, i = k, we find the longest uncovered path for which v is its end-vertex. The size of this path equals q and v is a q-kPVC-imperfect vertex.
The definition of an q-kPVC-imperfect vertex gives the desired theorems
similar to Theorem 2.1.
Theorem 2.2. Let G and H be connected graphs, where G is different from the vertex graph, and graph H rooted at h G V(H). If h is an q-kPVC-imperfect vertex for some q > , then
i—l
—(G o H) = | V(G) —(H)+ -02(G).
O
Proof. Suppose that h is an q-kPVC-imperfect vertex for some q > . Let S be a minimum k-path vertex cover of graph G o H, S» = {(gi? hj) G S | j G {2,..., | V (H )|}, i G {1,..., |V (G) |}, and S' = {(gi,hi) G S | i G {1,..., |V(G)|}. It is obvious that
|V (G)|
|S| = |Sj| I + |S'I.
j=i
CM
By the definition of the kPVC-imperfect vertex h always lies in an uncovered path of order at least Pq for every k-path vertex cover of graph H in such a away that h is the end-vertex of this path. Since h = h1 is a kPVC-imperfect vertex, every minimum k-path vertex cover of H does not contain vertex h. If |Sj| = —k(H) — 1, for some i, then S» U {(gi,h1)} is a minimum k-path vertex cover of graph induced by the H»-layer, and hence h = h1 is a kPVC-perfect vertex, which is not possible. Therefore, |S»| > —k(H), for all i G {1,..., | V(G)|}.
The main idea of the proof is to show that any two adjacent H-layers contribute at least 2—k(H) + 1 vertices in S. Let (g», h1), (gj, h1) G V(G o H), i = j, be any two adjacent vertices. We analyze two cases.
Case 1: Let |S»| = —k(H) and |Sj | = —k(H). Suppose that both vertices (gj, h1) and (gj, h1) do not belong to S. Then S» and Sj are minimum k-path
vertex covers of the H»-layer and the Hj-layer, respectively. If h = h1 is a
s
CO CO
r + s > 2 ■ q > 2
> k
q-kPVC-imperfect vertex of graph H, then (gi, h1) and (gj, h1) are q-kPVC-imperfect vertices of the Hi-layer and the Hj-layer, respectively. Hence, (gi,h1) lies in an uncovered path Pr, r > q, and is the end-vertex of this path. Also, (gj, h1) lies in an uncovered path Ps, s > q, and is the end-vertex of this path. Since vertices (gi, h1) and (gj, h1) are adjacent in graph G o H, paths Pr and Ps together form another uncovered path of order
Hence, S is not a k-path vertex cover, which is a contradiction. Therefore, at least one of the vertices (gi, h1) and (gj, h1) must belong to S. Moreover, layers Hi and Hj contribute at least 2^k(H) + 1 vertices to S.
Case 2: At least one of |Si| and |Sj| does not equal (H). Without loss of generality, let this be |Si |. According to the observation above |Si| > (H) + 1 and |Sj | > (H). Obviously, layers Hi and Hj contribute at least 2^k(H) + 1 vertices to S. Considering both cases,
CM
^(G o H) = |V(H(H)+ ^(G).
CM
|S| > |V(H(H)+ ^2(G). By Proposition 2.1, this is also the upper bound. Hence,
Theorem 2.3. Let G and H be connected graphs, where G is different from the vertex graph, and graph H rooted at h e V(H). If
^(G o H) = |V(G)|^k(H)+ ^(G),
then h is an q-kPVC-imperfect vertex for some q > |_|J.
Proof. First note that ^2(G) = 0 since G is connected and different from the "vertex graph. Suppose that h is an q-kPVC-imperfect vertex for some q < |_|J — 1. If q = 0, then h is a kPVC-perfect vertex and by Remark 2.1 it follows that
^(G o H) = | V(G)|^k(H) < | V(G)|^k(H)+ ^(G).
Let q = 0. If k = 2 or k = 3, then q = 0, and the rest of the proof is not necessary. Therefore, we may assume that k > 4. First, we construct a k-path vertex cover S of graph G o H such that |S| = |V(G)|A (H) + A(G). Let S1 be a minimum k-path vertex cover of graph H, such that h is the endvertex of an uncovered path of order Pq, and S2 a minimum 2-path vertex cover (i.e. vertex cover) of graph G. We cover every H-layer in the same way that S1 covers graph H. Also, we cover the G-layer in the same way that S2 covers graph G. We take both mentioned covers for the set S. Note that S2 = 0 since G is connected and different from the vertex graph. Take a vertex (g, h) E V(G o H) such that g E S2. Let T2 be the set of vertices in graph G which are adjacent to g and are not covered. Since S2 is a minimum vertex cover T2 = 0. The graph induced on the set of vertices T2 U {g} is a star graph with the central vertex g. Vertices in V(G) — (T2 U {g}) (if there are any) that are adjacent to vertices in T2 must all belong to S2. Otherwise, S2 would not be a vertex cover. Therefore, by uncovering vertex g, we get an uncovered path of order at most 3 in graph G. For |T2| = 1 and ui E T2, this path is of order 2, namely P2 = uig. The worst case is if |T2| > 2. For
CD
O
vertices ui,uj- E T2, i = j, this path is of order 3, namely P3 = uiguj-. It is obvious that if we eliminate paths of order k in the case of |T2| > 2, we also eliminate them in the case of |T2| = 1. Hence, we consider two vertices ui,u E T2, i = j.
If h is a q-kPVC-imperfect vertex of graph H, then (gi;h) and (gj, h) are q-kPVC-imperfect vertices of the Hi-layer and the Hj-layer, respectively.
CM	Hence, (gi;h) lies in an uncovered path Pq and is the end-vertex of this
path. Also, (gj, h) lies in an uncovered path Pq and is the end-vertex of this path. Since vertices (gi;h), (g, h) and (gj, h) form the path P3, both paths Pq together with the path P3 form another uncovered path of order at most
CO
2 ■ q + 1 < 2
— 1+1 < k— 1
We have proved that S — {(g, h)} is also a k-path vertex cover of graph G o H. Therefore
A(G o H) < |V(G)|A(H) + A(G) — 1 < |V(G)|A(H) + A(G). For even k we can combine Theorem 2.2 and Theorem 2.3 into the fol-
m
CD
1
$H
CD
lowing nice corollary.
U
a
CD U
00 CM CM
u
a
CD U
Corollary 2.4. Let G and H be connected graphs, where G is different from the vertex graph, and graph H rooted at h G V(H). If k is even, then
tk(G o H) = | V(G)|tk(H)+ t2(G)
if and only if h is an q-kPVC-imperfect vertex for some q > |.
Proof. For k is even the equality |"|] = |_|J holds. Hence, Theorem 2.3 is the converse of Theorem 2.2 and vise versa.	□
To see the behavior of tk (G o H) for smaller values of q for a q-kPVC-imperfect vertex we give the following result.
Proposition 2.4. Let G and H be connected graphs, where G is different from the vertex graph, and graph H rooted at h G V(H). If h is a 1-kPVC-imperfect vertex, then
o
tk(G o H) = |V(G)|tk(H)+ tk(G). Proof. Let h G V(H) be a 1-kPVC-imperfect vertex. Then there exists a
minimum k-path vertex cover S of graph H such that h is uncovered and isolated from the other uncovered vertices in H. We construct a k-path vertex cover of graph G o H in such way that we cover every H-layer in the same CM	way that S covers graph H. In this sense vertices (gj, h), i G {1,..., |V(G)|},
are all uncovered and isolated from the uncovered vertices in all H-layers. To complete the proof we cover the vertices of the G-layer with a k-path vertex cover of the size tk(G). Altogether we have covered |V(H)|tk(H) + tk(G) vertices and since, according to Proposition 2.2, this is also the lower bound of tk(G o H) it follows that
tk (G o H) = |V (G)|tk (H)+ tk (G).
The converse of Proposition 2.4 does not hold. Take for example k > 5, G = Pk-3 = MiM2 . ..uk_3, and H = Pk+2 = viv2 ...vk+2 rooted at v^ It is clear that tk (H) = 1 and that v1 is a 2-kPVC-imperfect vertex since the closest vertex to v1 which can be covered in a minimum k-path vertex cover of H = Pk+2 is vertex v3. It is easy to see that tk(GoH) = |V(H)|tk(H)+tk(G) (see Figure 5).
00 1—1
b
u
CD
("l>vl) ("2>vl) («3>vl)	("i-3>vl)
O-Q-
("l>v2)
(«2>v2)
Q Q 0
(«3>v2)
(«1,V3)

(u3,v3)
(uk-3,v2)
(uk-3 ,v3)
t t t t
j("l>Vt+2)	J(«3>vi« ) JC"i-3>vi+2)
Figure 5: The graph Pk-3 o Pk+2 rooted at (wj, vi), i G {1,..., k — 1}
0 o
CM
1
CM CO CM CM
£ CO CO
C0 CD
$H
CD C0
Corollary 2.5. Let G and H be arbitrary connected graphs and H rooted at h G V(H). Then
{|V(G)|"3(H)	; h is a kPVC-perfect vertex
|V(g)|^s(h)+ "3(G) ; h is a 1-kPVC-imperfect vertex . |V(g)|"2(h) + "2(g) ; h is a 2-kPVC-imperfect vertex
Proof. If G is the vertex graph, then "2(G) = "3 (G) = 0. It follows that
"03(G O H) = ^(H) = |V(G)|^(H)
= | V (G)|"3(H)+ "3(G) = | V (G)|"3(H)+ "2(G)
and all three results coincide.
Now suppose that G is not the vertex graph. If h is a kPVC perfect vertex, then by Remark 2.1 it follows that
"(G O H) = | V(G)|"(H).
Let q > |"|] = |"|] =2. If h is a q-kPVC-imperfect vertex, and hence also a 2-kPVC-imperfect vertex, then by Theorem 2.2 it follows that
"3(G O H) = |V(G)|"3(H)+ "2(G).
To end the proof, by Theorem 2.3, if h is a 1-kPVC-imperfect vertex, then
"3(G O H) = |V(G)|"3(H)+ "3(G).
U
a
CD U
Corollary 2.6. Let G and H be arbitrary connected graphs and H rooted at h G V(H). Then

|V(G)|diss(H)	; h is a kPVC-perfect vertex
diss(GoH) = ^ |V(G)|(diss(H) — 1) + diss(G) ; h is a 1-kPVC-imperfect vertex |V(G)|(diss(H) — 1) + a(G) ; h is a 2-kPVC-imperfect vertex
Proof. By Corollary 2.5 the result follows immediately. First, suppose that h is a kPVC-perfect vertex. Then

CO CD
■ i-H
u
CD
diss(G o H) = |V(G o H)| - ^(G o H)
= | V (G)||V (H )| — |V (G)|03(H) = | V (G)|(|V (H )|— 0a(H)) = |V(G)|diss(H).
If h is a 1-PVC-imperfect vertex, then
fi
diss(G o H) = |V(G o H)| — ^(G o H)
= | V (G)||V (H )| — |V (G)|^s(H) — 0a(G) = | V (G)||V (H)| — |V (G)|0a(H) — |V (G)| + |V (G)| — 03(G) = | V (G)|(|V (H)| — 03(H) — 1) + | V (G)| — 0a(G) = |V(G)|(diss(H) — 1) + diss(G).
CO
If h is a 2-PVC-imperfect vertex, then
CM
diss(G o H) = |V(G o H)| — 03(G o H)
= | V (G)||V (H )| —|V (G)|03(H) — 02(G) = | V (G)||V (H)| — |V (G)|03(H) — | V (G)| + | V (G)| — 02(G) = | V (G)|(|V (H)| — 03(H) — 1) + | V (G)| — 02(G) = |V(G)|(diss(H) — 1) + a(G).
□
3. Concluding remarks
We have seen that securing local networks which are communicating with each other through servers that are connected in a global network can be
done in such a way that we place a server in a kPVC-perfect vertex of a local
network. In this sense we get a secured network with the smallest possible number of sensors. If this is not possible, then the server must be placed as close as possible to a kPVC-perfect vertex in the local networks.
This study was made in the case where all local networks are the same. In general, local networks are different. Hence, the study of generalized rooted product of graphs is needed. This product was introduced in [8]. Let G be a labeled graph on m vertices and let H be a sequence of m rooted graphs Hi; H2,..., Hm. The rooted product graph G (H) is the graph obtained by identifying the root of graph Hi with the i-th vertex of graph G.
We end this short section with an open question of how to properly secure a generalized rooted product.
Acknowledgment
This work has been financed by ARRS Slovenia under the grant P1-0297 and within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation.
CD
O
References
o
[1] V.E. Alekseev, R. Boliac, D.V. Korobitsyn, V.V. Lozin, NP-hard graph problems and boundary classes of graphs, Theor. Comp. Science 389 (1-2) (2007) 219-236.
i
CM 00 CM CM
[2]	R. Boliac, K. Cameron, V.V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241-253.
CO
[3]	B. Bresar, M. Jakovac, J. Katrenic, G. Semanisin, A. Taranenko, On the vertex k-path cover, Discrete Appl. Math. 161 (13-14) (2013) 1943-1949.
[4]	B. Bresar, F. Kardos, J. Katrenic, G. Semanisin, Minimum k-path vertex cover, Discrete Appl. Math. 159 (12) (2011) 1189-1195.
m
CD
i
u
CD
[5]	K. Cameron, P. Hell, Independent packings in structured graphs, Math. Program. 105 (2-3) (2006) 201-213.
[6]	J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (4) (1985)
287-293.
17
• i $H
a
CD
$H
cu
[7]	D. Geller, S. Stahl, The chromatic number and other functions of the lexicographic product, Journal of Combinatorial Theory, Series B 19 (1975) 87-95.
[8]	C. D. Godsil, B. D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1) (1978) 21-28.
2 U
CD
Ö
GÏ O CM
I
S CO CO
CO CD
CD CO
u
a
CD U
[9] F. Göring, J. Harant, D. Rautenbach, I. Schiermeyer, On F-independence in graphs, Discuss. Math. Graph Theory 29 (2) (2009)
377-383.
[10]	J. Harant, M.A. Henning, D. Rautenbach, I. Schiermeyer, Independence Number in Graphs of Maximum Degree Three, Discrete Math. 308 (2008) 5829-5833.
[11]	J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math. 232 (2001) 131-138.
[12] M. Jakovac, A. Taranenko, On the k-path vertex cover of some graph products, Discrete Math. 313 (1) (2013) 94-100.
[13]	F. Kardos, J. Katrenic, I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theor. Comp. Science. 412 (50) (2011) 7009-7017.
CO
[14]	K. M. Koh, D. G. Rogers, T. Tan, Products of graceful trees, Discrete Math. 31 (3) (1980) 279-292.
[15]	M. Novotny, Design and Analysis of a Generalized Canvas Protocol, in: P. Samarati, M. Tunstall, J. Posegga, K. Markantonakis, D.Sauveron (Eds.), Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices, Springer, Berlin / Heidelberg, 2010, 106-121.
[16]	Y. Orlovich, A. Dolguib, G. Finkec, V. Gordond, F. Wernere, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (13) (2011) 1352-1366.
[17]	V. R. Rosenfeld, The independence polynomial of rooted products of graphs, Discrete Appl. Math. 158 (5) (2010) 551-558.
00 1—1
b
u
CD
0 o
CM
1
CM CO CM CM
£ CO CO
[18]	S. M. Selkow, The independence number of graphs in terms of degrees, Discrete Math. 122 (1-3) (1993) 343-348.
[19]	J. Tu, F. Yang, The vertex cover P3 problem in cubic graphs, Inform. Process. Lett. 113 (13) (2013) 481-485.
[20]	J. Tu, W. Zhou, A factor 2 approximation algorithm for the vertex cover P3 problem, Inform. Process. Lett. 111 (14) (2011) 683-686.
[21]	J. Tu, W. Zhou, A primal-dual approximation algorithm for the vertex cover P3 problem, Theoret. Comput. Sci. 412 (50) (2011) 7044-7048.
[22]	A. Vesel, J. Zerovnik, The independence number of the strong product of odd cycles, Discrete Math. 182 (1-3) (1998) 333-336.
[23]	M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Computing 10 (1981) 310-327.
[24]	I. G. Yero, J. A. Rodriguez-Velazquez, and D. Kuziak, Closed formulae for the metric dimension of rooted product graphs, manuscript 2013.
m
CD
$H
CD
m
u
a
CD U