The eternal vertex cover (EVC) problem is to compute the minimum number of guards to be placed on the vertices of a graph so that any sequence of attacks on its edges can be defended by dynamically recon guring the guards. The problem is NP hard in general and polynomial time algorithms are unknown even for simple graph classes like cactus graphs and bipartite graphs. A major di culty is that only few lower bounds, other than the trivial lower bound of vertex cover, is known in general and the known bounds are too weak to yield useful results even for the graph classes mentioned above. We introduce the notion of substructure property in the context of the EVC problem and derive a new lower bounding technique for the problem based on the property. We apply the technique to cactus graphs and chordal graphs and obtain new algorithms for solving the eternal vertex cover problem in linear time for cactus graphs and quadratic time for a family of graphs that includes all chordal graphs and cactus graphs.
Eternal vertex cover (EVC) problem is described by a two player attack-defense
game played on a graph G [
Commons License Attribution 4.0 International (CC BY 4.0). 1 Another version of the problem places an additional constraint that at most one guard can be on any vertex in a con guration. The results of this paper and those cited hold true in both versions. to eternally defend any arbitrary sequence of attacks. Clearly, evc(G) mvc(G), the vertex cover number of G. An evc class of G whose con gurations have evc(G) guards is called a minimum evc class of G.
Fomin et al. [
E cient algorithms for computing evc(G) were known for elementary classes
like trees, cycles, grids [
A cactus is a connected graph in which any two simple cycles have at most one vertex in common. The class of cactus graphs includes trees and cycles, but also contains graphs for which evc(G) 2= fmvcX (G); mvcX (G) + 1g. In Section 6, we show an in nite family of cactus graphs for which evc(G) > 32 mvcX (G). This shows that known lower bound techniques fails even on simple graph classes like cactus graphs.
We formulate a new lower bounding technique based on the substructure
property (De nition 4) using which e cient algorithms are obtained for the EVC
problem in some graph classes violating the condition evc(G) 2 fmvcX (G); mvcX (G)+
1g. This is achieved by generalizing a recursive procedure for trees by
Klostermeyer and Mynhardt [
De nition 1. Let G be a graph and S V (G). The minimum cardinality of a vertex cover of G that contains all vertices of S is denoted by mvcS (G). The minimum integer k such that there is a defense strategy on G using k guards with all vertices of S being occupied in each con guration is denoted by evcS (G). When S = fvg, we use mvcv(G) and evcv(G) respectively instead of mvcS (G) and evcS (G). From the above de nition, it is clear that evc(G) evcS (G). De nition 2. If G is a graph and x 2 V (G), we use Gx+ to denote the graph obtained by adding an additional vertex which is made adjacent only to x. Observation 1 evc(Gx+)
evc(G) + 1.
For proofs of some observations that are omitted from the main text, the reader
may refer to the draft version [
De nition 3 (x-components and x-extensions). Let x be a cut vertex in a connected graph G and H be a component of G n x. Let G0 be the induced subgraph of G on the vertex set V (H) [ fxg. Then, G0 is called an x-component of G and G is called an x-extension of G0.
De nition 4 (Substructure property). Let x be an arbitrary non-cut vertex of a graph G. If the following is true for any arbitrary x-extension G0 of G, then G satis es substructure property:
if evc(Gx+) evcx(G), then in every eternal vertex cover C0 of G0, the number of guards on V (G) is at least evcx(G) 1 and
if evc(Gx+) > evcx(G), then in every eternal vertex cover C0 of G0, the number of guards on V (G) is at least evcx(G).
Observation 2 If a graph G satis es substructure property and x is a non-cut vertex of G, then evcx(G) evc(Gx+) evcx(G) + 1.
De nition 5. Let G be a graph and x be a vertex of G. Then, G is Type 1 with respect to x if evc(Gx+) = evcx(G) and G is Type 2 with respect to x if evc(Gx+) > evcx(G).
Remark 1. A tree is Type 1 with respect to all its vertices. An even (respectively,
odd) cycle is Type 1 (respectively, Type 2) with respect to all its vertices. A
complete graph Kn, with n 3 is Type 2 with respect to all its vertices.
Remark 2. By Observation 2, if G satis es substructure property and x is a
non-cut vertex of G, then G is either Type 1 or Type 2 with respect to x.
De nition 6 ([
X Gi2T1(G;x) (evcx(Gi) 2) + (evcx(Gi)
1)
X Gi2T2(G;x) Lemma 1. Let G be a connected graph and x be a cut-vertex of G such that each x-component of G satis es the substructure property. If all x-components of G are Type 2, then evc(G) = evcx(G) = (G; x). Otherwise, evc(G) = evcx(G) = 1 + (G; x).
Lemma 1 indicates the possibility of a recursive method to compute eternal vertex cover number of graphs whose x-components satisfy the substructure property. However, this makes it necessary to also compute evcx(G) and the type of each x-component of G, with respect to x. Since a cut vertex of G is not a cut-vertex in its x-components, a general method to nd the type of a graph with respect to any arbitrary vertex of the graph (including non-cut vertices) is necessary. This section addresses this issue systematically.
Observation 3 (Type with respect to a cut vertex) Let G be a connected graph and x be a cut-vertex of G such that each x-component of G satis es the substructure property. Then, G is Type 1 with respect to x if at least one of the x-components of G is Type 1 with respect to x. Otherwise, G is Type 2 with respect to x.
Proof. Note that when a pendent edge xv is added to x, that edge is a Type 1 component with respect to x. Further, evcx of this x-component is 2. Using these facts in the expressions given in Lemma 1 immediately yields the observation. tu Observation 4 Let G be a graph that satis es substructure property and x be any vertex of G. If evc(G) < evcx(G), then G is Type 1 with respect to x. Proof. If evc(G) < evcx(G), then by Observation 1, we have evc(Gx+) evc(G) + 1 evcx(G). By Remark 2 and Observation 3, evc(Gx+) evcx(G). Therefore, evcx(G) = evc(Gx+). From this, the observation follows. tu The following observation is useful for deciding the type of a graph with respect to a pendent vertex.
Lemma 2 (Type with respect to a pendent vertex). Let G be a graph and x 2 V (G). Let H = Gx+ with v being the vertex in V (H) n V (G). Suppose each x-component of H satis es substructure property. Then, H is Type 1 with respect to v if and only if G is Type 1 with respect to x.
Proof. In any eternal vertex cover class of H with evcv(H) guards in which v is occupied in every con guration2, x must also be occupied in every con guration (otherwise, an attack on the edge vx cannot be defended maintaining a guard on v). Hence, the induced con gurations on G de ne an eternal vertex cover class of G in which x is occupied in every con guration. It follows that evcv(H) evcx(G) + 1. Moreover, from an eternal vertex cover class of G with x always occupied, we can get an eternal vertex cover class of H with v always occupied by placing an additional guard at v. Hence, evcv(H) evcx(G) + 1. Thus, evcv(H) = evcx(G) + 1. Note that, by Observation 1, evc(Hv+) evc(H) + 1. 2 If more than one guard is allowed on a vertex, we still can assume without loss of generality that v has only one guard in any con guration. Instead of placing more than one guard on v, it is possible to place all but one of those guards on x.
First, suppose G is Type 1 with respect to x. Then, evc(H) = evcx(G) and we get evcv(H) = evcx(G) + 1 = evc(H) + 1 = evc(Hv+), which means that H is Type 1 with respect to v.
Now, suppose G is Type 2 with respect to x. Then, evc(H) = evcx(G) + 1. Further, by Observation 3, if x is a cut vertex in G, then all the x-components of G are Type 2 with respect to x. Irrespective of whether x is a cut-vertex of G or not, by Lemma 1, evc(Hv+) = 2 + evcx(G). Hence, evc(Hv+) = evcv(H) + 1. Thus, if G is Type 2 with respect to x, then H is Type 2 with respect to v. tu Now, we give some observations that are useful for deciding the type of a graph with respect to a degree-2 vertex.
Lemma 3. Let G be any graph and suppose v is a degree-2 vertex in G such that its neighbors v1, v2 are not adjacent. Let G0 be the graph obtained by deleting v and adding an edge between v1 and v2. Then, evcv(G) = evc(G0) + 1. De nition 8. Let X be the set of cut vertices of a graph G. If B is a block of G, the set of B-components of G is de ned as CB(G) = fGi : Gi 2 Cx(G) for some x 2 X \ V (B), Gi edge disjoint with Bg. If P is a path in G, then the set of P -components of G is de ned as CP (G) = fGi : Gi 2 Cx(G) for some x 2 X \ V (P ), Gi edge disjoint with P g. De nition 9. For a block B (respectively, a path P ) of connected graph G, the type of a B-component (respectively, P -component) is its type with respect to the common vertex it has with B (respectively, P ). For i 2 f1; 2g, we de ne Ti(G; B) (respectively, Ti(G; P )) to be the set of all B-components (respectively, P -components) of G that are Type i.
If B is a block (respectively, P is a path) of a connected graph G, such that all B-components (respectively, P -components) of G satisfy substructure property, then we can easily obtain a lower bound on the total number of guards on SGi2CB(G) V (Gi) (respectively, on SGi2CP (G) V (Gi)) in any eternal vertex cover of G or its extensions. The notation introduced below is to abstract this lower bound.
De nition 10. For a block B of connected graph G, we de ne (G; B) to be (evcxi (Gi) 2) + (evcxi (Gi) 1): jV (B) \ Xj + jV (P ) \ Xj +
X
Gi2T1(G;B) xi2V (Gi)\V (B)
X
Gi2T1(G;P ) xi2V (Gi)\V (B) Similarly, for a path P of connected graph G, we de ne (G; P ) to be Remark 3. If B is a block (respectively, P is a path) of a connected graph G, such that all B-components (respectively, P -components) of G satisfy substructure Gi2T2(G;B) xi2V (Gi)\V (B)
X
X
Gi2T2(G;P ) xi2V (Gi)\V (B) (evcxi (Gi) 2) + (evcxi (Gi) 1): property, then the total number of guards on SGi2CB(G) V (Gi) (respectively, on SGi2CP (G) V (Gi)) in any eternal vertex cover of G or its extensions is at least (G; B) (respectively, (G; P )). De nition 11 (Vertex bunch of a path). Let P be a path in a connected graph G. The vertex set V (P ) [ SGi2CP (G) V (Gi) is the vertex bunch of P in G, denoted by VBG(P ).
De nition 12 (Eventful path). Let G be a connected graph and X be the set of cut vertices of G. A path P in a graph G is an eventful path if (i) P is either an induced path in G or a path obtained by removing an edge from an induced cycle in G (ii) the endpoints of P are in X and (iii) any subpath P 0 of P with both endpoints in X has jV (P 0) n Xj even.
Lemma 4. Let G be a connected graph and let P be an eventful path in G. Let X be the set of cut vertices of G. If each P -component in CP (G) satis es the substructure property, then in any eternal vertex cover con guration of G, the total number of guards on VBG(P ) is at least jV (P2)nXj + (G; P ). Moreover, if VBG(P ) 6= V (G) and the number of guards on VBG(P ) is exactly equal to the above expression, then at least one of the neighbors of the endpoints of P outside VBG(P ) has a guard on it.
Proof. Consider any subpath P 0 of P such that both endpoints of P 0 are in X and none of its intermediate vertices are from X. Let C be an eternal vertex cover con guration of G. Since P is eventful, jV (P 0) n Xj is even and in any vertex cover of G, at least jV (P 0)nXj internal vertices of P 0 must be present. Using this 2 along with the substructure property of P -components proves the rst part of the lemma.
Now, suppose VBG(P ) 6= V (G) and the number of guards in the con guration C on VBG(P ) is exactly equal to the expression given in the lemma. Now, for contradiction, let us assume that none of the neighbors of the endpoints of P outside VBG(P ) has a guard in C. Consider an attack on an edge xv, where x is an endpoint of P and v is a neighbor of x outside VBG(P ). To defend this attack, a guard must move from x to v. Note that, no guards can move to VBG(P ) from outside VBG(P ). Hence, while defending the attack, the number of guards on VBG(P ) decreases at least by one. But, then the new con guration will violate the rst part of the lemma. Hence, it must be the case that at least one of the neighbors of the endpoints of P outside VBG(P ) has a guard in C. tu De nition 13 (Maximal uneventful path). Let G be a connected graph and let X be the set of cut vertices of G. A path P in G is a maximal uneventful path in G if (i) V (P ) \ X = ; (ii) jV (P )j is odd and (iii) P is a maximal induced path in G satisfying the above two conditions.
The next lemma is applicable to any connected graph G that contains a block B which is a cycle such that all B-components satisfy the substructure property. Since each block of a cactus is either a cycle or an edge, this lemma will be useful for computing the eternal vertex cover number of cactus graphs. The proof of the lemma makes use of the fact that B can be partitioned into a collection of edge disjoint paths which are either eventful paths or maximal uneventful paths. Lemma 5. Let B be a cycle forming a block of a connected graph G and let X be the set of cut vertices of G. Suppose each B-component Gi of G that belongs to CB(G) satis es the substructure property. If T1(G; B) = ;, then evc(G) = l jV (B2)nXj m + (G; B). Otherwise, evc(G) = l jV (B)2nXj+1 m + (G; B). Proof. Let jV (B)j = n and jX \ V (B)j = k. For each B-component Gi of G that belongs to CB(G), let xi be the vertex that Gi has in common with B. Let C be a minimum eternal vertex cover of G. Note that the condition stated in Lemma 4 has to simultaneously hold for all subpaths of the cycle that are eventful in G.
Let l 0 be the number of maximal uneventful paths in B and let P1, P2, : : :, Pl be these listed in the cyclic order along B. To protect the edges within each Pi, V (Pi) should contain at least mvc(Pi) = b jV (Pi)j c guards. If there are 2 exactly b jV (2Pi)j c guards on V (Pi), the end vertices of Pi are not occupied and alternate vertices in Pi are occupied by guards. We divide the proof into four cases, based on the parity of n k and whether T1(G; B) is empty or not. We prove one of the cases here.
Let us consider the case when T1(G; B) = ; and n k is odd. In this case, from De nition 12, it follows that l is odd. First, suppose l = 1. Let P be the subpath obtained from B by deleting the edges of P1. It is easy to see that P is an eventful path. If V (P1) contains only b jV (2P1)j c guards, then the end vertices of P1 are not occupied by guards and the condition stated in Lemma 4 cannot hold for P . Therefore, the lemma holds when l = 1. Now, suppose l > 1. Then, if V (Pi) and V (Pi+1) (+ is mod l) respectively contains only b jV (2Pi)j c and b jV (P2i+1)j c guards and the vertex bunch of the path P between the last vertex of Pi and the rst vertex of Pi+1 contains exactly as many guards as mentioned in the rst part of Lemma 4, the condition stated in the second part of Lemma 4 cannot hold for P . Since this is true for all 1 i l, and the condition stated in Lemma 4 has to simultaneously hold for all subpaths of the cycle that are eventful in G, a simple counting argument shows that number of guards in C should be at least n2 k + (G; B).
Thus, we know that evc(G) is at least the expression given above. If T1(G; B) = ;, it is easy to show that these many guards are also su cient. The guards on V (B) can defend any attack on edges of B while keeping X \ V (B) always occupied. Attacks on edges of B-components can be handled, maintaining xi always occupied and having exactly evcxi (Gi) guards on each B-component Gi.
The proof of the other cases are similar and is omitted. tu
The following lemma gives a method to compute the type of a graph with respect to degree-two vertices in blocks which are cycles.
Lemma 6. Let B be a cycle of n vertices, forming a block of a connected graph G. Let X be the set of cut vertices of G and let k = jX \ V (B)j. Suppose each B-component in CB(G) satis es the substructure property. Let v 2 V (B) n X. The type of G with respect to v can be computed as follows.
{ If T1(G; B) 6= ; and n k is even, then evcv(G) = evc(G) = evc(Gv+). If T1(G; B) 6= ; and n k is odd, then evcv(G) = evc(G) + 1 = evc(Gv+). In both cases, G is Type 1 with respect to v. { If T1(G; B) = ; and n k is even, then evcv(G) = evc(G) + 1 = evc(Gv+) and G is Type 1 with respect to v. If T1(G; B) = ; and n k is odd, then evcv(G) = evc(G), evc(Gv+) = evcv(G) + 1 and G is Type 2 with respect to v. 4
Theorem 1. Every cactus graph satis es substructure property. Proof. Let G be a cactus graph. The proof is using an induction on the number of cut-vertices in G.
In the base case, G is a cactus without a cut vertex. Then, G is either a single vertex, a single edge or a simple cycle. In all these cases, the lower bound for the number of guards on V (G), speci ed by substructure property is equal to the vertex cover number of the respective graphs. Hence, the theorem holds in the base case.
Now, let us assume that the theorem holds for any cactus with at most k cut-vertices. Let G be a cactus with k + 1 cut vertices, for k 0 and let X be the set of cut vertices of G. Let v be a non-cut vertex of G and G0 be an arbitrary v-extension of G. We need to show that in any eternal vertex cover con guration of G0, the number of guards on V (G) is as speci ed by the substructure property. Since v is a non-cut vertex of the cactus G, either it is a degree-one vertex of G or it is a degree-2 vertex of G that is in some block B of G, where B is a cycle. We want to compute a lower bound on the number of guards on V (G) in an arbitrary eternal vertex cover con guration C0 of G0.
First, consider the case where v is a degree-one vertex of G. Let w be the neighbor of v in G and let H = G n v. Since G has at least one cut-vertex, w must be a cut vertex in G. There are two possibilities depending on whether w is a cut-vertex of H or not.
When w is a cut-vertex of H, consider any w-component Hi of H. Hi is a cactus and the number of its cut vertices is less than that of G. Hence, Hi satis es the substructure property. Further, G0 is a w-extension of Hi. In C0, the number of guards on V (Hi) is at least evcw(Hi) 1 if Hi 2 T1(H; w) and it is evcw(Hi) if Hi 2 T2(H; w). The total number of guards on V (H) is at least 1+PHi2T1(H;w) (evcw(Hi) 2)+PHi2T2(H;w) (evcw(Hi) 1). If v is occupied in C0, then the total number of guards on V (G) is at least the same as that of evc(G) as given by Lemma 1. If v is not occupied in C0, then to defend an attack on the edge wv, a guard from V (H) must move to v. Hence, in C0, the number of guards in V (H) should have been one more than the minimum mentioned earlier. Hence, in this case also, the number of guards on V (G) in C0 would have been at least evc(G). By Lemma 1, evc(Gv+) = evc(G) + 1. By Lemma 2, the type of G with respect to v is the same as the type of H with respect to w. Hence, if H is Type 1 with respect to w, we have evc(Gv+) = evcv(G) = evc(G) + 1. We have seen that the number of guards on V (G) is at least evc(G) = evcv(G) 1. If H is Type 2 with respect to w, then we have evc(Gv+) > evcv(G). Since evc(Gv+) = evc(G) + 1, in this case we must have evcv(G) = evc(G). We have seen that the number of guards on V (G) is at least evc(G) = evcv(G). Hence, the substructure property holds in both cases.
When w is not a cut vertex of H, G0 is a w-extension of H. By substructure property of H, it follows that in con guration C0, the number of guards on V (G) must be at least evcw(H) if H is Type 1 with respect to w and at least evcw(H) + 1 if H is Type 2 with respect to w. By Lemma 1, when H is Type 1 with respect to w, evc(G) = evcw(H) and when H is Type 2 with respect to w, evc(G) = evcw(H) + 1. By Lemma 2, the type of G with respect to v is the same as the type of H with respect to w. Hence, if H is Type 1 with respect to w, we have evc(Gv+) = evcv(G) = evc(G) + 1. The number of guards on V (G) is at least evcw(H) = evcv(G) 1. If H is Type 2 with respect to w, we have evc(Gv+) > evcv(G). Since evc(Gv+) = evc(G) + 1, in this case we must have evcv(G) = evc(G). The number of guards on V (G) is at least evcw(H) + 1 = evcv(G). Hence, the substructure property holds in both cases.
Now, consider the case when v is a degree-two vertex of G that is in some block B of G, where B is a cycle. Suppose jV (B)j = nb. Let X be the set of cut vertices of G and kb = jX \ V (B)j. As noted earlier, we have to compute a lower bound on the number of guards on V (G) in an arbitrary eternal vertex cover con guration C0 of G0. Let p and q respectively be the clockwise and anticlockwise nearest vertices to v in X \ V (B). Let P be the path in B between p and q that does not contain v. Note that, every B-component of G satis es substructure property by our induction hypothesis and G0 is an extension for each of them. Hence, we have a lower bound on the number of guards on V (Gi), for each Gi 2 CB(G). Similarly, the condition stated in Lemma 4 needs to be satis ed for each eventful subpath P 0 of P .
We have three possibilities to consider. When T1(G; B) = ;, by similar arguments as in the proof of Lemma 5, we can see that the number of guards on V (G) in C0 must be at least evc(G). By Lemma 6, when nb kb is even, G is Type 1 with respect to v and evcv(G) = evc(G) + 1. Since the number of guards on V (G) is at least evc(G) = evcv(G) 1, we are done. Similarly, when nb kb is odd, G is Type 2 with respect to v and evcv(G) = evc(G) and we are done. When T1(G; B) 6= ; and nb kb is even, by similar arguments we can see that the number of guards on V (G) in C0 must be at least evc(G) 1. By Lemma 6, G is Type 1 with respect to v and evc(G) = evcv(G). Since the number of guards on V (G) is at least evc(G) 1 = evcv(G) 1, we are done. When T1(G; B) 6= ; and nb kb is odd, by similar arguments we can see that the number of guards on V (G) in C0 must be at least evc(G). By Lemma 6, G is Type 1 with respect to v and evcv(G) = evc(G) + 1. Since the number of guards on V (G) is at least evc(G) = evcv(G) 1, we are done. Thus, in all cases, the lower bound on the number of guards on V (G) in an arbitrary eternal vertex cover con guration C0 of G0 satis es the condition stated in substructure property. Hence, G satis es substructure property.
Thus, by induction, it follows that every cactus satis es substructure property. tu Now, we have all ingredients for designing a recursive algorithm for the computation of eternal vertex cover number of a cactus, using Lemma 1. Our algorithm will take a cactus G and a vertex v of G and output evc(G), evcv(G) and the type of G with respect to v. If G is a cycle or an edge or a vertex, the answer is trivial and can be computed in linear time.
In other cases, G has at least one cut vertex. If v is a cut vertex, then we call the algorithm recursively on each v-component of G along with vertex v. Then, we can use Lemma 1 to compute evc(G) and evcv(G) in constant time from the result of the recursive call. Using the same information from recursive calls, the type of G with respect to v can also be computed using Observation 3. If v is a pendent vertex and w is its neighbor in G, then we recursively call the algorithm on (G n v; w). By Lemma 2, the type of G with respect to v is the same as the type of G n v with respect to w. Moreover, from the proof of Lemma 2, we have evcv(G) = evcw(G n v) + 1. Further, evc(G) = evcw(G n v), when G is Type 1 with respect to v and evc(G) = evcw(G n v) + 1, when G is Type 2 with respect to v. Thus, from the results of the recursive call on (G n v; w), the output can be computed in constant time. In the remaining case, v is a vertex that belongs to a cycle B in G. In this case, we recursively call the algorithm for each B-component of G, along with the respective cut vertices it shares with B. Using this information, we can compute evc(G) using Lemma 5 in time proportional to the number of B-components. We can also compute evcv(G) and the type of G with respect to v, using Lemma 6 in time proportional to the number of B-components.
Thus, the algorithm works in all cases and runs in time linear in the size of G. Hence, we have the following result.
Theorem 2. Eternal vertex cover number of a cactus G can be computed in time linear in the size of G.
From the upper bound arguments in the proofs discussed in Section 2 and Section 3, we can see that with evc(G) guards determining con gurations of guards to keep defending attacks on G is straightforward. 5
It may be noticed that most of the intermediate results stated in this paper are generic, though we have stated Lemma 5 and Lemma 6 in a way suitable for handling cactus graphs. In this section, we show how to extend the method used for cactus graphs to a graph class consisting of connected graphs in which each block is a cycle, an edge or a biconnected chordal graph. It may be noted that this class contains all chordal graphs and cactus graphs. To generalize the proof of Theorem 1 for this class, the base case of the proof needs to be modi ed to handle biconnected chordal graphs as well. The following observation addresses this requirement.
Observation 5 Every biconnected chordal graph satis es substructure property. Proof. Let G be a biconnected chordal graph and v 2 V (G). Let G0 be a vextension of G and C be an eternal vertex cover con guration of G0. If the number of guards on V (G) in C is less than mvcv(G), then v is not occupied in C. In this con guration, an attack on an edge of G adjacent to v cannot be defended, because when a guard on a vertex of G moves to v, some edge of G will be without guards. Therefore, in any arbitrary eternal vertex cover con guration C of G0, the number of guards on V (G) must be at least mvcv(G).
By a result in [
Proof. Since B is a biconnected chordal graph, if for every v 2 V (B) n X,
mvc(X\V (B))[fvg(B) = mvcX\V (B)(B), then evcX\V (B)(B) = mvcX\V (B)(B)
and evcX\V (B)(B) = mvcX\V (B)(B) + 1 otherwise [
When T1(G; B) = ;, it is easy to show that evc(G) evcX\V (B)(B) + (G; B) jX \ V (B)j. When T1(G; B) 6= ;, by repeated attacks on edges of V (Gi) for some Gi 2 T1(G; B), eventually a con guration which requires (G; B) + 1 guards on SGi2CB V (Gi) can be forced. Hence, evc(G) mvcX\V (B)(B) + 1 + (G; B) jX \V (B)j. Since evcX\V (B)(B) mvcX\V (B)(B)+1, it is not di cult to also show that evc(G) mvcX\V (B)(B) + 1 + (G; B) jX \ V (B)j. In both cases, the value of evc(G) is as stated in the lemma.
For deciding the type of G with respect to a vertex v 2 V (B), we need to compare evcv(G) and evc(Gv+). For computing evc(Gv+), we can use the formula given by the rst part of the lemma for the graph evc(Gv+). Using similar arguments as in the proof of the rst part of the lemma, we get the following: if T1(G; B) = ;, then evcv(G) = evc(X\V (B))[fvg(B) + (G; B) jX \ V (B)j and evcv(G) = mvc(X\V (B))[fvg(B) + 1 + (G; B) jX \ V (B)j otherwise. By computing mvc(X\V (B))(B) and mvc(X\V (B))[fvg(B) for each v 2 V (B), evcv(G) and evc(Gv+) can be computed. Since minimum vertex cover of a chordal graph can be computed in linear time, the total time required for computing evcv(G) and evc(Gv+) this way is possible in time quadratic in the size of B. From the values of evcv(G) and evc(Gv+), the type of G with respect to v can be inferred. Now, similar arguments as in the proof of Theorem 1 and Theorem 2 yields: Theorem 3. Suppose G is a connected graph in which each block is a cycle, an edge or a biconnected chordal graph. Then, G satis es substructure property and the eternal vertex cover number of G can be computed in quadratic time. tu 6
A cactus family with evc(G) > 1:5 mvcX (G) v2k v2k 1 v1 v2 v3 v5 v4
Until now, all graph classes with known polynomial time algorithms for eternal vertex cover had evc(G) 2 fmvcX (G); mvcX (G) + 1g, where X is the set of all cut vertices of G. It is interesting to note that mvcX (G) could be much smaller than evc(G) for some cactus graphs. An example of this is shown in Fig. 1. Using the formula given by Lemma 5, we can show that the eternal vertex cover number of this graph G is k + d k +21 e. However, for this graph, mvcX (G) is only k making evc(G) > 1:5 mvcX (G). 7
Though the substructure property has been shown here for a family of graphs that include cactus and chordal graphs, we believe that this property or a generalization of it holds for fairly large classes of graphs. It is interesting to characterize graphs that satisfy this property. Deriving a generalization of the substructure property to outerplanar graphs and bounded treewidth graphs is also an interesting direction.