Zbigniew Lonc

Paweł Naroski

A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph

Keywords: 3-uniform hypergraph, Euler walk, strongly connected hypergraph, linear time algorithm

By an Euler walk in a 3-uniform hypergraph H we mean an alternating sequence v0, e1, v1, e2, v2, . . . , vm-1, em, vm of vertices and edges in H such that each edge of H appears in this sequence exactly once and vi-1, vi ∈ ei, vi-1 = vi, for every i = 1, 2, . . . , m. This concept is a natural extension of the graph theoretic notion of an Euler walk to the case of 3-uniform hypergraphs. We say that a 3-uniform hypergraph H is strongly connected if it has no isolated vertices and for each two edges e and f in H there is a sequence of edges starting with e and ending with f such that each two consecutive edges in this sequence have two vertices in common. In this paper we give an algorithm that constructs an Euler walk in a strongly connected 3-uniform hypergraph (it is known that such a walk in such a hypergraph always exists). The algorithm runs in time O(m), where m is the number of edges in the input hypergraph.

Introduction

In this paper we consider a generalization of the graph-theoretic concept of an Euler walk to 3-uniform hypergraphs. This notion is well-understood from both theoretical and algorithmic point of view in the case of graphs. There are several possible ways to generalize this concept to the case of hypergraphs. The way we do it is motivated by some past research and potential applications.

By a hypergraph we mean a pair H = (V, E), where V is a finite set and E is a family of some subsets of V . The elements of the set V are called vertices of H and the elements of E its edges. In this paper we deal with k-uniform hypergraphs only, i.e. hypergraphs whose all edges have the same cardinality equal to k. Clearly, 2-uniform hypergraphs are graphs.

By a walk (or a v 0 v -walk) of length in a hypergraph H we mean an alternating sequence v 0 , e 1 , v 1 , e 2 , v 2 , ..., v -1 , e , v of vertices and edges of this hypergraph satisfying the following conditions: † zblonc@mini.pw.edu.pl ‡ p.naroski@mini.pw.edu.pl 1365-8050 c 2012 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France (i) the edges e 1 , e 2 , . . . , e are pairwise different, (ii) v i-1 , v i ∈ e i , for i = 1, ..., , and

(iii) v i-1 = v i , for i = 1, ..., .

A walk is called a tour if (iv) v 0 = v .

We observe that the conditions (iii) and (iv) in the definition of a tour imply that ≥ 2. If, for some walk (respectively tour), e 1 , e 2 , . . . , e are all the edges of a hypergraph H, then we call such a walk (resp. tour) an Euler walk (resp. tour) in H. Let us observe that if H is a 2-uniform hypergraph (i.e. a graph), then the notions of an Euler walk and tour coincide with their traditional meanings in graph theory.

As we have already mentioned, there are several possible ways to extend the graph-theoretic concept of a tour to the case of hypergraphs. The tours we have just defined are most closely related to so-called Berge-cycles (see Berge [START_REF] Berge | Hypergraphs, Combinatorics of Finite Sets[END_REF], p. 155). More precisely, a tour defined in this paper in which all vertices v 1 , v 2 , . . . , v are pairwise different is a Berge-cycle.

It is natural to ask questions how fast we can check if an Euler walk and an Euler tour in a k-uniform hypergraph exist and, if they exist, how fast we can construct them. It is not surprising (and quite simple to prove; see [START_REF] Lonc | On tours that contain all edges of a hypergraph[END_REF]) that unlike in the case of graphs, the problems of existence of an Euler walk and tour in a k-uniform hypergraph are NP-complete, when k > 2.

However, if we restrict our attention to some important smaller classes of hypergraphs, the problems become tractable. A good example of such a class is the class of so-called triangulated irregular networks. Following the terminology we use in this paper, a triangulated irregular network (or a TIN) is a 3-uniform hypergraph whose edges are the vertex sets of all the triangular faces of some planar 2-connected graph in which all faces, except possibly the outer face, are triangles. TINs are structures widely used in geographic information systems (GIS) and computer graphics to represent terrains and surfaces (see for example [START_REF] Laurini | Fundamentals of Spatial Information Systems[END_REF]). An important issue addressed in these areas is to order triangles of a TIN into a sequence such that the consecutive triangles in this sequence share 1 or 2 vertices. Such ordering enables to compress the data and speeds up transmission and processing of triangulations. Clearly, we obtain a more efficient compression if consecutive triangles in the ordering share 2 vertices. However, it is not difficult to show that the problem of existence of such ordering for a TIN is NP-complete. Therefore, we relax the restriction and require that consecutive triangles share at least 1 vertex. This relaxation leads naturally to the concept of an Euler walk in a TIN (see [START_REF] Arkin | Hamilton triangulations for fast rendering[END_REF] and [START_REF] Bartholdi | Multiresolution indexing of triangulated irregular networks[END_REF] for a more thorough discussion of these issues).

Euler walks and tours in TINs have been intensively studied, in the context described in the preceding paragraph, in a series of papers by Bartholdi and Goldsman [3,[START_REF] Bartholdi | Vertex-labeling algorithms for the hilbert spacefilling curve[END_REF][START_REF] Bartholdi | Multiresolution indexing of triangulated irregular networks[END_REF][START_REF] Bartholdi | The vertex-adjacency dual of a triangulated irregular network has a hamiltonian tour[END_REF] and Arkin et al. [START_REF] Arkin | Hamilton triangulations for fast rendering[END_REF]. Among others it was shown in [START_REF] Bartholdi | Multiresolution indexing of triangulated irregular networks[END_REF] that all TINs have Euler walks. Moreover a TIN has an Euler tour unless it belongs to some special family of exceptions (described in [START_REF] Bartholdi | Multiresolution indexing of triangulated irregular networks[END_REF]). For TINs in which every edge has 2-element intersections with at least 2 other edges, the authors gave an algorithm constructing Euler tours. The running time of this algorithm is O(m 2 ), where m is the number of edges in the TIN.

The problem of existence of an Euler walk in TINs has also been studied in mixed integer programming in connection with the problem of approximation of a two-variable function with a piecewise linear function (see Wilson [START_REF] Wilson | Polyhedral Methods for Piecewise-Linear Functions[END_REF] and Vielma et al. [START_REF] Vielma | Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions[END_REF]).

In [START_REF] Lonc | On tours that contain all edges of a hypergraph[END_REF] we studied the problems of existence of Euler walks and tours in strongly connected k-uniform hypergraphs. A k-uniform hypergraph H is strongly connected if it has no isolated vertices and for each two edges e and f in H there is a sequence of edges starting with e and ending with f such that each two consecutive edges in this sequence have k -1 vertices in common. One can easily observe that the class of strongly connected 3-uniform hypergraphs contains the class of TINs as a proper subclass. For this reason this case (of k = 3) seems to be more interesting that the case of k > 3. Another reason is that, as we demonstrated in [START_REF] Lonc | On tours that contain all edges of a hypergraph[END_REF], for k > 3 the problems of existence of an Euler walk or tour in a strongly connected hypergraph become trivial. Therefore in this paper we consider 3-uniform hypergraphs only.

In [START_REF] Lonc | On tours that contain all edges of a hypergraph[END_REF] we characterized all strongly connected 3-uniform hypergraphs that have an Euler tour and proved that all 3-uniform strongly connected hypergraphs have an Euler walk.

In the present paper we describe an algorithm that constructs an Euler walk in a strongly connected 3-uniform hypergraph that runs in time O(m), where m is the number of edges in the hypergraph. It improves over the already mentioned algorithm given in [START_REF] Bartholdi | Multiresolution indexing of triangulated irregular networks[END_REF], designed for some special strongly connected TINs only, that runs in time O(m 2 ).

Using similar ideas we can also design an algorithm constructing an Euler tour in a strongly connected 3-uniform hypergraph, whenever it exists (see Naroski [START_REF] Naroski | Long tours in hypergraphs[END_REF]), that runs in time O(m). The algorithm (which we do not discuss in this paper) is, however, much more technically complicated.

The paper is organized as follows. In Section 2 we present our algorithm and prove its correctness. All aspects regarding the data structures and the running time of our algorithm are discussed in Section 3. Finally in Section 4 we give some final remarks.

The algorithm and its correctness

Our algorithm (that we call EulerW alk) works in two main steps. First, we partition the edge set of the input strongly connected 3-uniform hypergraph into a certain number of walks such that all the walks, except possibly one, are tours (this is basically done by the algorithm Dismantle, see Lemma 2). Next, we glue the walks together and create a single walk containing all edges of the input hypergraph (this step is done by the algorithm W alk, see Lemma 4).

Let us introduce definitions and notation that we will use in this paper. For a hypergraph H, we denote by E(H) the set of edges of H. Let, for a 3-uniform hypergraph H, F (H) denote the set of all 2-element sets that are contained in at least one edge of H. Clearly, |F (H)| ≤ 3|E(H)|. Let A be a set of 3-element sets. We say that a hypergraph is induced by the set of edges A if A is the edge set of the hypergraph and the union of the edges in A is its vertex set. For a hypergraph H and an edge f in H, we denote by H -f the hypergraph induced by the set of edges E(H) -{f }.

By the edge set of a walk W = v 0 , e 1 , v 1 , e 2 , v 2 , ..., v -1 , e , v we mean the set {e 1 , e 2 , . . . , e } and we denote it by E(W ). We say that a walk (or a tour) W traverses an edge e i using vertices v i-1 and v i if the sequence (v i-1 , e i , v i ) is a subsequence of consecutive terms of the alternating sequence W . By a partition of the edge set of a hypergraph H into walks we mean a partition of the edge set of H into subsets which are edge sets of some walks.

For a 3-uniform strongly connected hypergraph H we define a graph G(H) whose vertex set is the set of edges of H. The set of edges of G(H) consists of pairs of edges of H which intersect on 2 elements. As H is strongly connected, the graph G(H) is connected. We would like to construct a depth-first tree in G(H) (starting with an arbitrary vertex e in G(H)). However, we do not want to construct the graph G(H) explicitly because the number of edges in G(H) may be quadratic with respect to m = |E(H)|. The algorithm DF -tree(H, e) described below constructs a depth-first tree T e in G(H) without explicitly constructing G(H). We shall prove in Section 3 that the algorithm DF -tree(H, e) runs in time O(m) if we choose an appropriate data structure to represent the hypergraph H.

In the algorithms DF -tree and Dismantle discussed beneath, S is a stack. We use standard stack operations push(S, g) to insert an element g onto S, pop(S) to remove the top element from S, and top(S) to return the top element of S without removing it from S. We also use a Boolean array visited indexed with all edges of H. If, for some edge f , visited[f ] = true, then we call the edge f visited. Otherwise, when visited[f ] = false, we call f unvisited. By E e we denote the set of edges of the tree constructed by the algorithm DF -tree.

Algorithm DF -tree(H, e) Clearly, line 8 of the algorithm DF -tree can be equivalently written as follows

1 for every edge f in H do visited[f ] ← false 2 S ← ∅ 3 E e ← ∅ 4 push(S,

8'

if f g is an edge in G(H), for some edge g such that visited[g] = false so DF -tree is a standard algorithm constructing a depth-first tree (rooted in e) in G(H).

Lemma 1 Let f be a vertex in the tree T e constructed by the algorithm DF -tree(H, e) and let

f 1 , f 2 be two different children of f in T e . Then |f 1 ∩ f 2 | = 1. Proof: As both f f 1 and f f 2 are edges in T e , |f ∩ f 1 | = |f ∩ f 2 | = 2, so |f 1 ∩ f 2 | ≥ 1. Suppose the lemma is not true, so |f 1 ∩ f 2 | = 2 and, consequently, f 1 f 2 is an edge in G(H).
Clearly, the vertex f had been visited before f 1 and f 2 were visited in the execution of the algorithm DF -tree(H, e). We can assume without loos of generality that f 1 had been visited before f 2 was visited. As f 1 f 2 is an edge in G(H), the vertex f 2 was visited while f 1 was still at the stack S (so in particular f was not at the top of S). Thus, f 2 is not a child of f in T e , a contradiction. Hence,

|f 1 ∩ f 2 | = 1. 2
As every child of a vertex f in T e is a 3-element set sharing 2 elements with f , Lemma 1 immediately implies the following statement.

Corollary 1 Each vertex in the tree T e has at most 3 children.

2

Let H be a 3-uniform strongly connected hypergraph and let e be an edge in H. The algorithm Dismantle(H, e), that we give below, constructs a partition of the edge set of H or H -e into tours. It will turn out that the tours in the partition are in fact short (each of them has 2 or 3 edges).

In the algorithm Dismantle, C is a list of tours in H. Let {e 1 , . . . , e k } be the edge set of some walk in H. By L(e 1 , . . . , e k ) we denote any walk (of possibly many) whose edge set is {e 1 , . . . , e k }.

Algorithm Dismantle(H, e) 1 T e ← DF -tree(H, e) 2 for every vertex

f in T e do visited[f ] ← false 3 C ← ∅ 4 S ← ∅ 5 push(S, e) 6 visited[e] ← true 7 while S = ∅ 8 do f ← top(S) 9
if visited[g] = false, for some child g of f in T e 10 then push(S, g) Proof: We observe that the list C is updated in lines 13, 16 and 19 of the algorithm only. It follows from Lemma 1 that the edges f 1 , f 2 , f 3 of H defined in line 12 form a tour. Similarly, by Lemma 1, the edges f 1 , f 2 defined in line 15 (resp. f 1 defined in line 18) and f form a tour in H (see Figure 1). Thus, the elements added to C in lines 13, 16, and 19 are tours. Consequently, the algorithm returns a list of tours in H.

11 visited[g] ← true 12 else if f has 3 children f 1 , f 2 , f 3 and all of them are leaves in T e 13 then C ← C ∪ {L(f 1 , f 2 , f 3 )} 14 remove vertices f 1 , f 2 , f 3 from T e 15 if f has 2 children f 1 , f 2 and both of them are leaves in T e 16 then C ← C ∪ {L(f 1 , f, f 2 )} 17 remove vertices f 1 , f, f 2 from T e 18 if f has 1 child f 1 and it is a leaf in T e 19 then C ← C ∪ {L(f 1 , f )} 20 remove vertices f 1 , f from T e 21 pop (
It is clear that the tours stored in the list C do not have common edges because in the algorithm Dismantle(H, e) right after adding a tour to the list C the edges that form the tour are removed from the set of vertices of T e (lines 14, 17 and 20).

It suffices to show that all vertices of T e (which are edges of H), except possibly its root e, belong to some tour in the list C when the algorithm stops. Let us denote by E the set of edges of H that do not belong to any tour in the list C when the algorithm stops and assume that E -{e} = ∅. We notice that the set of vertices not removed from the tree T e when the algorithm stops is equal to E too (see lines 13-14, 16-17 and 19-20). Next, we observe that if a vertex is removed from T e , then all its children are removed (see lines 12-20). Thus, if some vertex f of T e is in the set E, then so is its parent. Consequently, the vertices of T e which belong to E form a subtree T e of T e rooted at e. The tree T e has a vertex different from e because E -{e} = ∅. Let f be a lowest leaf in T e and let f 0 be its parent. Obviously, each vertex of T e is inserted onto the stack S exactly once and removed from S exactly once. Let us consider the pass of the while loop when the vertex f 0 is removed from S. One can easily observe that at this moment all children of f 0 are leaves in the current tree T e . As f 0 has at least one child (f is child of f 0 ), one of the conditions in lines 12, 15 or 18 is satisfied. Consequently, f is removed from T e in this pass of the while loop, so f ∈ E, a contradiction. Thus, E -{e} = ∅ and the lemma holds. 2 The algorithm W alk that we will describe later constructs an Euler tour (or walk) in a strongly connected hypergraph from an already constructed partition of the edge set of the hypergraph into tours (or tours and one walk). In this algorithm we will need an auxiliary algorithm Connect. The input to the algorithm Connect consists of a walk P , a tour C, an edge e in P , and an edge f in C. The walk P and the tour C are edge-disjoint and the edges e and f intersect on a 2-element set. The algorithm Connect produces a walk W whose edge set is the union of edge sets of the walk P and the tour C. Proof: It suffices to observe that the sequences assigned to the variable W in lines 4 and 12 of the algorithm Connect(P, e, C, f ) are ab-walks with the edge set E(P ) ∪ E(C).

x x x x x x x x x x x x x x x f f 1 f 1 f 1 f 2 f 2 f 3 f f x y z x y z y = (x, f 1 , y, f 3 , z, f 2 , x) =(x, f 1 , y, f, z, f 2 , x) x L(f 1 , f 2 , f 3 ) L(f 1 , f, f 2 ) L(f 1 , f ) = (x, f 1 , y, f, x)
2

The input C of the algorithm W alk written below is a list of walks whose sets of edges form a partition of the edge set of a strongly connected hypergraph. At most one of the walks is not a tour. We shall show (see Lemma 4) that this algorithm returns a walk whose edge set is the union of the edge sets of the walks in C.

Algorithm W alk(C) 1 P ← the only walk in C which is not a tour, if it exists, or any element of

C otherwise 2 C ← C -{P } 3 while C = ∅ 4
do Find a pair of edges e and f such that e is an edge of P , but f is not an edge of P and |e ∩ f | = 2. 5

Find a tour C ∈ C containing f . 6

P ← Connect(P, e, C, f ) 7

C ← C -{C} 8 return P Lemma 4 Let H be a strongly connected hypergraph and C a list of walks whose sets of edges form a partition of the edge set of H. At most one of the walks in C is an ab-walk which is not a tour. The algorithm W alk(C) returns an Euler ab-walk in H. This walk is an Euler tour in H, if the list C contains tours only.

Proof: Let a and b be the ends of the walk assigned to the variable P in line 1 of the algorithm. (If this walk is a tour, then a = b is any vertex of this tour.) After executing of lines 1-2 of the algorithm W alk(C), the list C contains tours in H only and the variable P contains a walk in H (which may be a tour too).

At this moment the edge sets of the tours in the list C together with the edge set of P form a partition of the edge set of H and P is an ab-walk. We claim that this property is an invariant of the while loop in lines 3-7. We observe that as long as the list C is nonempty, the instructions in lines 4-5 are feasible. Indeed, let E(P ) be the set of edges of P and let E(C) be union of the sets of edges of the walks in the list C at start of some pass of the while loop. As E(P ) ∪ E(C) = E(H), by the strong connectivity of H, there is a pair of edges e ∈ E(P ) and f ∈ E(C) such that |e ∩ f | = 2. So, the instructions in lines 4-5 are feasible as long as C = ∅. By Lemma 3, after execution of line 6, the variable P contains an ab-walk whose edge set is the sum of the edge sets of the walk which was the value of P right before execution of this line and the edge set of the tour C. Since the tour C is removed from the list C in line 7, right after execution of the analyzed pass of the while loop, the edge sets of the tours in the updated list C together with the edge set of the updated walk P form a partition of the edge set of H. This completes the proof of our claim.

At the end of the last pass of the while loop the list C is empty, so by the claim proved in the preceding paragraph, the walk P returned by the algorithm W alk is an ab-walk containing all edges of H, so it is an Euler ab-walk in H. If, at start of the algorithm, the list C contains tours only, then a = b, so the algorithm returns an Euler walk. Let C be the input list for the algorithm W alk and let m be the number of edges in the strongly connected hypergraph induced by the union of the edges of the walks in the list C. We shall show now that the algorithm W alk can be implemented to run in time O(m). We represent walks as doubly linked lists and tours as doubly linked cyclic lists of consecutive vertices and edges of these walks or tours. To reach a linear running time of the algorithm, we need a data structure which, for a given edge and a given partition of the edge set of a hypergraph into walks, enables us to find in a constant time the unique walk containing this edge and the position of this edge in this walk. Therefore, for a partition C of the set of edges of a hypergraph into walks, we define an array J C indexed with edges of the hypergraph. For every edge e of the hypergraph, J C [e] = (W e , p e ), where W e is the walk in C which contains the edge e and p e is a pointer to the edge e on the list representing the walk W e .

Lemma 7 Let H be a strongly connected hypergraph and C a list of walks whose sets of edges form a partition of the edge set of H. Moreover, at most one of the walks in C is not a tour. The algorithm W alk(C) can be implemented to run in time O(m), where m is the number of edges in H.

Proof: We assume that the hypergraph H is represented by the lists I[c], for every c ∈ F (H). At start of the algorithm we create the data structure J C . Clearly, it can be done in time O(m).

Obviously, finding the walk in line 1 of the algorithm W alk(C) takes O(m) time and executing the line 2 can be implemented to run in a constant time.

We observe that in each pass of the while loop exactly one walk is removed from the list C, so the number of passes of this loop is bounded by m. After removing a walk from the list C (in lines 2 and 7), we shall delete the edges of this walk from all the lists I[c], c ∈ F (H). Since every edge of H belongs to exactly one walk in C, the total number of such deletions is bounded by 3m. Due to these removals, at start of every execution of the while loop, the lists I[c] contain only the edges of the hypergraph H which do not belong to the current walk P .

We shall show now that the total time needed for all executions of line 4 of the algorithm W alk is O(m). We use the observation made in the preceding paragraph that e and f is a pair of edges described in line 4 of the algorithm if and only if |e ∩ f | = 2 and at the moment of execution of line 4, f is in one of the lists I[c], where c ∈ F (e), and e is an edge of the walk P . Thus, in each execution of line 4, we search for an edge e in the walk P such that for some c ∈ F (e), the list I[c] is nonempty and if it is, we choose f to be the first edge in this list. We do this search for such an edge e in the following order. First we check the edges of the walk assigned to the variable P in line 1, next the edges added to the walk P (in line 6) in the first pass of the while loop, next the edges added to the walk P in the second pass of the loop, etc. We observe that, if for an edge e in P , I[c] = ∅, for some c ∈ F (e ), then I[c] = ∅ in all executions of line 4 in the next passes of the while loop. Therefore, in executions of line 4 in each of the remaining passes of this loop, we do not check such lists I[c] any more. We start the search for an edge e satisfying the condition in line 4 from the next list I[c], for c ∈ F (e ), or from a list I(c ), for c ∈ F (e ), where e is the next edge in our order, if all the lists I[c], for c ∈ F (e ), are empty. This way no element in the lists I[c], c ∈ F (H), is checked more than once. As the sum of numbers of elements in the lists I[c] is 3m, the amount of time needed for all executions of line 4 in the algorithm is O(m).

Let us consider now line 6 of the algorithm W alk which contains a call of the algorithm Connect. The data structure J C allows us to find all the vertices (x, u, v, t, and w) needed in the procedure Connect in a constant time. The construction of the walk W in lines 4 and 12 of the algorithm Connect can be done by redirecting a constant number of pointers in the linked lists representing the walk P and the tour C. All these operations take a constant time, however after executing line 6 of the algorithm W alk, the data structure J C has to be updated because we get a new partition of the edge set of H into walks. For each edge e in the tour C, we have to change the value W e of the walk containing the edge e (from C to P ). Since, for every edge of the hypergraph H such an update is needed at most once, the total time necessary for such updates is O(m).

Each execution of line 5 of the algorithm W alk takes a constant time because we use the data structure J C . Moreover, obviously, we need a constant time to execute line 7. Therefore, as the number of passes of the while loop is bounded by m, the running time of the algorithm W alk is O(m).

2

The linearity of the algorithm EulerW alk constructing an Euler walk in a strongly connected hypergraph follows now immediately from Lemmas 5 and 7.

Theorem 2 The algorithm EulerW alk finding an Euler walk in a strongly connected hypergraph can be implemented to run in time O(m), where m is the number of edges in this hypergraph. 2

Final remarks

The linear time algorithm EulerW alk provides a constructive proof of existence of an Euler walk in a strongly connected hypergraph. Let us observe however that we do not impose any conditions regarding the ends of the constructed Euler walk. In Naroski [START_REF] Naroski | Long tours in hypergraphs[END_REF] a linear time algorithm constructing an Euler tour in a strongly connected hypergraph (if such a tour exists) was given. The algorithm is more technically complicated and requires some new ideas. This algorithm can also be used to construct in linear time an Euler ab-walk in a strongly connected hypergraph, for a specified pair of vertices a and b (if such a walk exists).

S) 22 return C Lemma 2

 2 Let H be a strongly connected 3-uniform hypergraph and e an edge in H. When the algorithm Dismantle(H, e) stops, the list C consists of tours whose sets of edges form a partition of the edge set of H or H -e.

Fig. 1 :

 1 Fig. 1: Tours added to the list C in lines 13, 16, and 19. The shaded edge f does not belong to the tour.

Fig. 2 : 3 P 2 ← 9 P 1 ←

 23291 Fig. 2: Construction of the walk W in the option else of the algorithm Connect.

Lemma 6

 6 The algorithm Dismantle can be implemented to run in time O(m), where m is the number of edges in the input hypergraph.Proof: By Lemma 5, line 1 of the algorithm Dismantle runs in time O(m). Moreover by the same argument as in the proof of Lemma 5, we show that the number of passes of the loop in lines 7-21 of the algorithm Dismantle is 2m -1. Each instruction in this loop takes a constant time (for the instruction in line 9 it follows from Corollary 1), so the running time of the algorithm Dismantle is indeed O(m). 2

Acknowledgements

We thank Armin Fügenschuh for introducing us to the subject of this paper and for pointing out some relevant references. We are also grateful to an anonymous referee whose remarks allowed us to simplify presentation of some parts of the paper. This research was supported by the Polish Ministry of Science and Higher Education in 2009-2010 under grant No. 3674/B/H03/2009/36.

We are ready now to give an algorithm which constructs an Euler walk in a strongly connected hypergraph. Recall that, for a single edge e, by L(e), we mean any walk whose edge set is {e}. 3 The running time

Algorithm

We shall first discuss the running time of the algorithm Dismantle. We start with defining a data structure to represent the input hypergraph.

Let H be a 3-uniform hypergraph. For every c ∈ F (H), we construct a doubly linked list I[c] of edges of H which contain c. Clearly, each edge occurs in three different such lists. We assume that the occurrences of the same edge in different lists are appropriately joint by pointers to enable removal of the edge from all three lists in a constant time. More precisely, if we want to remove an edge, say e, from a list, we first find using the pointers (in a constant time) the remaining two occurrences of e in the lists. To remove the edge e from each of these list, it suffices to redirect appropriately the links of the predecessor and the successor of e. It can be done in a constant time as the lists are double linked. The lists I[c] can be easily constructed in time O(m), where m = |E(H)|, if H is given in any standard way (e.g. by a list of edges or by incidence lists, i.e. lists defined for every vertex and consisting of all the edges containing this vertex).

Lemma 5

The algorithm DF -tree can be implemented to run in time O(m), where m is the number of edges in the input hypergraph.

Proof: We assume that the input hypergraph H is represented by the lists I[c], for every c ∈ F (H).

Clearly, the number of passes of the loop in line 1 is equal to m and each pass of this loop takes a constant time. In each pass of the while loop either one edge is inserted onto S (see line 9) or one is removed (see line 12). Thus, as the graph G(H) is connected, the number of passes of the loop in lines 6-12 is 2m -1 because each edge of H is one time inserted onto S and one time removed.

In each pass of this loop checking if the condition in line 8 is satisfied and finding the appropriate edge g can be implemented to run in a constant time by using the lists I[c], c ∈ F (f ). After finding an unvisited edge g in one of these three lists I[c], we remove the edge g from the lists containing it. This way each time the condition in line 8 is checked for an edge f , each list I[c], c ∈ F (f ), contains unvisited edges only (or is empty). So, every execution of line 8 takes a constant time. It is quite straightforward to check that all the remaining instructions inside the loop in lines 6-12 take constant times.

Thus, the running time of the algorithm DF -tree is indeed O(m). 2


Aneta Dudek
email: dudekane@agh.edu.pl

Andrzej Żak

On hamiltonian chain saturated uniform hypergraphs

Keywords: saturated hypergraph, hamiltonian path, hamiltonian cycle, hamiltonian chain

We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H. In this paper we ask about the smallest size of a k-uniform hamiltonian chain saturated hypergraph. We present a construction of a family of k-uniform hamiltonian chain saturated hypergraphs with O(n k-1/2 ) edges.

Introduction

Let H be a k-uniform hypergraph on the vertex set V (H) = {v 1 , ..., v n } with n ≥ k. The set of the edges -k-element subsets of V (H) -is denoted by E(H). For simplicity of notation v n+x with x ≥ 0 denotes the same vertex as v x . In [START_REF] Katona | Hamiltonian chains in hypergraphs[END_REF] the authors defined the notion of a hamiltonian chain.

Definition 1 A cyclic ordering (v 1 , v 2 , . . . , v n ) of the vertex set is called a hamiltonian chain and denoted C (k) n , if and only if {v i , v i+1 , . . . , v i+k-1 } ∈ E(H) whenever 1 ≤ i ≤ n. An ordering (v 1 , v 2 , . . . , v l ) of a subset of the vertex set is called a path and denoted P (k) l , if and only if {v i , v i+1 , . . . , v i+k-1 } ∈ E(H)

whenever 1 ≤ i ≤ l -k + 1. A path P (k)
n is a hamiltonian path.

For v ∈ V (H), let H -v be the hypergraph obtained by deleting v and all edges incident to v. We refer to this operation as removing v from H. Definition 2 We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H.

The question investigated in this paper is the following: What is the minimum number sat(n, C (k) n ) of edges in a hamiltonian chain saturated k-uniform hypergraphs on n vertices?

In fact, the above problem belongs to the much wider theory of saturated graphs and hypergraphs. Given a hypergraph F , we say that the hypergraph H is F -saturated if H has no F as a subhypergraph, but does contain F after the addition of any new edge. The minimum number of edges in an F -saturated hypergraph on n vertices is denoted by sat(n, F ) (the maximum number is denoted by ex(n, F ) and the problem of determining ex(n, F ) is the Turán's problem). There are many results on sat(n, F ) for graphs, including complete graphs [START_REF] Erdős | A problem in graph theory[END_REF], cycles [START_REF] Ashkenazi | C 3 saturated graphs[END_REF][START_REF] Barefoot | Cyclesaturated graphs of minimum size[END_REF][START_REF] Chen | Minimum C 5 -saturated graphs[END_REF][START_REF] Füredi | Cycle-saturated graphs with minimum number of edges[END_REF][START_REF] Gould | Constructive upper bounds for cycle-saturated graphs of minimum size[END_REF][START_REF] Ollmann | K 2,2 saturated graphs with a minimal number of edges[END_REF][START_REF] Zs | C 4 -saturated graphs of minimum size[END_REF], complete s-partite graphs [START_REF] Bohman | The saturation function of complete partite graphs[END_REF][START_REF] Chen | saturated graphs[END_REF][START_REF] Chen | Saturation numbers of books[END_REF][START_REF] Pikhurko | Results and open problems on minimum saturated hypergraphs[END_REF]. In particular, the problem considered in the paper is solved for graphs. Namely, sat(n, C n ) = 3n 2 (apart from a few small values of n) which follows from [START_REF] Bondy | Variations on the hamiltonian theme[END_REF][START_REF] Clark | Smallest maximally nonhamiltonian graphs[END_REF][START_REF] Clark | Smallest maximally nonhamiltonian graphs II[END_REF]. Furthermore, sat(n, P n ) = 3n-1 2 for n ≥ 54 [START_REF] Dudek | Hamiltonian path saturated graphs with small size[END_REF][START_REF] Frick | Lower bound for the size of maximal nontraceable graphs[END_REF]. Much less is known for k ≥ 3. Bollobás [START_REF] Bollobás | On generalized graphs[END_REF] generalized Erdős, Hajnal and Moons result [START_REF] Erdős | A problem in graph theory[END_REF] for complete k-uniform hypergraphs. Erdős, Füredi and Tuza [START_REF] Erdős | Saturated r-uniform hypergraphs[END_REF] obtained sat(n, F ) for some particular hypergraphs F with few edges. Pikhurko [START_REF] Pikhurko | The minimum size of saturated hypergraphs[END_REF] proved that sat(n, F ) = O(n k-1 ) for any fixed hypergraph F (generalizing previous result for graphs by Erdős, Füredi and Tuza [START_REF] Erdős | Saturated r-uniform hypergraphs[END_REF]). The same order of magnitude was conjectured for sat(n, C (k) n ) [START_REF] Katona | Hamiltonian chains in hypergraphs[END_REF] and sat(n, P

(k) n ) [12]. It is known that both sat(n, C (k) n ) and sat(n, P (k) n ) are at least n k /(k(n -k) + 1)
, see [START_REF] Dudek | Hamilton-chain saturated hypergraphs[END_REF]. Hence the lower bound is of order n k-1 . On the other hand in [START_REF] Katona | Hamiltonian chains in hypergraphs[END_REF] a construction is given of n-vertex hamiltonian path saturated k-uniform hypergraphs with

∼ 1 k! - 1 2 k k/2 ! k/2 ! n k
edges. In case when k = 3, better constructions presented in [START_REF] Dudek | Hamilton-chain saturated hypergraphs[END_REF] give hamiltonian path saturated 3uniform hypergraphs and hamiltonian chain saturated 3-uniform hypergraphs with O(n 5/2 ) edges. In this paper we present a non-obvious generalization of these construction for all k ≥ 4. As a result we obtain that

sat(n, C (k) n ) ≤ 1 k! + 1 (k -1)! n k-1/2 + o n k-1/2 .
We notice also that the same bound holds for sat(n, P

n ).

Construction

In the sequel we assume that k is a fixed integer greater than or equal to 4.

Definition 3

Let p and q be non-negative integers and U 0 , U 1 , . . . , U q be pairwise disjoint sets of vertices such that |U 0 | = p and |U i | ≥ 2 for i = 1, 2, . . . , q. Define the vertex set of the hypergraph H to be

V (H) = q i=0 U i . Let u 1 ∈ U i1 , ..., u k ∈ U i k and j = min{i 1 , ..., i k }. Then {u 1 , ..., u k } =: E ∈ E(H) if and only if j = 0 or |E ∩ U j | ≥ 2.
The family of all hypergraphs obtained by this construction is denoted by H k (p, q). Notation The above number j that is determined by the edge E is denoted by j E .

Theorem 1 Let H ∈ H k (p, q) where p, q are non-negative integers such that p ≥ 2 and q ≥ k 2 (p-1)+2.

Let |U i | = α for i = 1, ..., q-1 and α 2 (k-1) < |U q | ≤ kα,
where α is an integer satisfying α ≥ 2p(k-2). Then H does not have a hamiltonian chain.

Proof. Suppose for a contradiction that H contains a hamiltonian chain (v 1 , v 2 , ..., v n ). By removing all vertices from U 0 the chain (v 1 , v 2 , ..., v n ) falls to m parts, m ≤ p. Each part induces a path in H -U 0 or consists of at most k -1 vertices. Note that for any two adjacent edges E and E belonging to one part j E = j E . Indeed, E has only one vertex which does not belong to E. Thus, since |E ∩ U j E | ≥ 2, E contains a vertex from U j E . Hence, j E ≤ j E . Due to symmetry we have also j E ≤ j E . Therefore, every edge in a part has at least two vertices from some fixed set U j . We say that the set U j is a dominating set for this part. Let x i denote the number of vertices of the i-th part which belong to its dominating set. Let y i denote the number of remaining vertices in the i-th part. In this part consider now consecutive disjoint k-tuples and an r-tuple at the end, 0 ≤ r ≤ k -1. Let x r denote the number of vertices from the dominating set that belong to the r-tuple. Each k-tuple contains at least two vertices from the dominating set. Hence, the number of considered k-tuples does not exceed xi-xr 2 ≤ α 2 . Thus, if r ≤ k -2 then the number of vertices in the i-th part satisfies

x i + y i ≤ α 2 k + (k -2). (1)
If r = k -1 then x r ≥ 1 (because the last k vertices form an edge, too). Hence,

x i + y i ≤ α-1 2 k + (k -1), so (1) is satisfied, too. Hence, x i + y i ≤ α 2 k + (k -2) or, if a part contains vertices from only one set U j , x i + y i ≤ |U j |. In particular, x i + y i ≤ α 2 k + (k -2)
for all parts except possibly one which contains only vertices from U q (this is because

|U q | < 2( k 2 α + (k -2)
). Hence, if some part contains only vertices from U q then

(q -1)α + |U q | = |U 1 | + ... + |U q | = m i=1 (x i + y i ) ≤ m-1 i=1 k 2 α + (k -2) + |U q | ≤ (p -1) k 2 α + (k -2) + |U q |, hence q ≤ (p -1) k 2 + k -2 α (p -1) + 1 < (p -1) k 2 + 2, a contradiction.
Otherwise,

(q -1)α + |U q | = |U 1 | + ... + |U q | = m i=1 (x i + y i ) ≤ m i=1 k 2 α + (k -2) ≤ p k 2 α + (k -2) , hence (q -1)α < p k 2 α + (k -2) - α 2 (k -1), whence q < (p -1) k 2 + 2, a contradiction again. 2
Theorem 2 Let t be a positive integer and let

H ∈ H k (2t + 1, kt + 2). Let |U i | = α for i = 1, ..., kt + 1 and α 2 (k -1) < |U kt+2 | ≤ (α -k)(k -2)
, where α is an integer satisfying α ≥ (4t + 2)(k -2). Then H is hamiltonian chain saturated.

Proof. Let p = 2t + 1 and q = kt + 2. Hence, q = k 2 (p -1) + 2. Thus, by Theorem 1, H does not have any hamiltonian chain. We will prove that adding any new edge E 0 produces a hamiltonian chain in H. Let E 0 have the form {i 1 , i 2 , ..., i k } with 1 ≤ i 1 < i 2 ≤ i 3 , ..., ≤ i k ≤ q, which means that E 0 contains a vertex from set U i1 , a vertex from set U i2 , and so on. Note that E 0 contains only one vertex from U i1 since E 0 / ∈ E(H). Suppose first that i 2 = q. Thus, E 0 contains at most k -2 vertices from U q . Let j 1 < j 2 < ... < j q-3 be consecutive integers from {1, ..., q -1} \ {i 1 , i 2 }. Let C ji , i = 1, ..., p -1, be a path of the form * , ..., * k-2

, j i , j i , * , ..., * k-2 , j i , j i , • • • , * , ..., * k-2 , j i , j i , * , ..., * k-2 , j i , j i , * , ..., * k-2 , (j i )
which means that C ji contains • all vertices from U ji \ E 0 -in the positions denoted by j i (the symbol (j i ) means that C ji may or may not contain a vertex from U ji \ E 0 in this position depending on the parity of

|U ji \ E 0 |)
• some vertices from the set U jp ∪ ... ∪ U jq-3 \ E 0 -in the positions denoted by * .

Clearly, U ji is the dominating set for C ji (since i < p). Moreover, among every k consecutive vertices there are two vertices from U ji . Thus, C ji is indeed a path. Let

z ji = |U ji ∩ E 0 |. Note that a single C ji may contain α-zj i 2
k + (k -2) vertices. Thus, the paths C j1 , ..., C jp-1 together may contain (q -3)α vertices. Indeed,

p-1 i=1 α -z ji 2 k + (k -2) ≥ p-1 i=1 α -z ji -1 2 k + (k -2) (2) = α 2 k(p -1) + (p -1)(k -2) - p-1 i=1 z ji + 1 2 k = α 2 k(p -1) + (p -1)(k -2) - k 2 p-1 i=1 z ji + p-1 i=1 1 ≥ α 2 k(p -1) + (p -1)(k -2) - k 2 (k -2 + p -1) ≥ α 2 k(p -1) -α = (q -3)α, because α ≥ k 2 (k -2).
On the other hand, after removing any number of vertices outside the set U ji from a C ji we still have a path. Indeed, by removing some vertices from positions denoted by * we do not spoil the property, that among every k consecutive vertices there are at least two vertices from U ji . Therefore we can construct p -1 paths C j1 , ..., C jp-1 which together contain all vertices from U j1 ∪ ... ∪ U jq-3 \ E 0 (and do not contain any other vertex). Finally, let C i1 have the form q, ..., q

k-2 , i 1 , i 1 , q, ..., q k-2 , i 1 , i 1 , • • • , q, ..., q k-2 , i 1 , i 1 , k-2 i 3 , ..., i k , i 2 E0 i 2 q, ..., q k-2 , • • • , i 2 , i 2 , q, ..., q k-2 . Note that |U i1 ∪ U i2 | -(k -2) 2 ≥ 2α -k + 1 2 = α -k + k/2 + 1/2 > α -k + 2 = (α -k)(k -2) k -2 + 2 > |U q | k -2 .
Hence, we are able to insert all vertices from U q to C i1 . Moreover, by adding at the beginning (or at the end) of C i1 any number of vertices from U i1 \ E 0 (from U i2 \ E 0 ) we still have a path. Hence, we can construct a path C i1 which contains all vertices from U i1 ∪ U i2 ∪ U q ∪ E 0 . It is easy to see now that

C j1 , 0, C j2 , 0, • • • , 0, C jp-1 , 0, C i1 , 0
(here symbols 0 denote distinct vertices from U 0 ) is a hamiltonian chain in H. Suppose now that i 2 = q, whence E 0 is of the form {i 1 , q, ..., q}. Let j 1 < j 2 ... < j q-2 be consecutive integers from {1, ..., q -1} \ {i 1 }. We construct paths C j1 , ..., C jp-1 in a similar way as previously. This time the paths C ji may contain (q -2)α vertices. This can be verified by similar computations as previously, see [START_REF] Barefoot | Cyclesaturated graphs of minimum size[END_REF], with one difference that now z ji = 0 for each i = 1, ..., p -1. Recall, that after removing any number of vertices outside the set U ji from a C ji we still have a path. Therefore, we can construct p -1 paths C j1 , ...,C jp-1 which together contain all vertices from U j1 ∪ ... ∪ U jq-2 (and do not contain any other vertex). Now let C i1 have the form i 1 , i 1 , ..., i 1 , i 1 , q, q, ..., q E0 , q, ..., q, q and contain all vertices from U i1 ∪ U q . Therefore,

C j1 , 0, C j2 , 0, • • • , 0, C jp-1 , 0, C i1 , 0 is a hamiltonian chain in H. 2
3 Main result Theorem 3 For each n ≥ k 4 + 8k 3 + 16k 2 , there exists a k-uniform, hamiltonian chain saturated hypergraph with fewer than

1 k! + 1 (k-1)! n k-1/2 + o n k-1/2 edges.
Proof. Let t 0 := √ n 2k -1 and α := n-2t0-2 kt0+1/2+k/2 . Thus, it is easy to check that α ≥ (4t

0 + 2)k > (4t 0 + 2)(k -2). Let H ∈ H k (2t 0 + 1, kt 0 + 2) with |U i | = α for i = 1, ..., kt 0 + 1. Then n -2t 0 -1 kt 0 + 1/2 + k/2 -1 ≤ α < n -2t 0 -1 kt 0 + 1/2 + k/2
, whence

(kt 0 + 1)α + α 2 (k -1) < n -2t 0 -1 ≤ (kt 0 + 1)α + α 2 (k -1) + (kt 0 + k/2 + 1/2).
Thus, since n -2t 0 -1 = (kt 0 + 1)α + |U kt0+2 |, we have

α 2 (k -1) < |U kt0+2 | ≤ α 2 (k -1) + kt 0 + k/2 + 1/2 < (α -k)(k -2)
for k ≥ 4, α ≥ (4t 0 + 2)k and t 0 ≥ k/2. Therefore, by Theorem 2, H is a hamiltonian chain saturated hypergraph.

Moreover,

|E(H)| ≤ |U 0 | n -1 k -1 + kt0+1 i=1 α 2 n -2t 0 -1 -(i -1)α k -2 + |U kt0+2 | k ≤ (2t 0 + 1) n k-1 (k -1)! + α 2 2 kt0+1 i=1 (n -(i -1)α) k-2 (k -2)! + k k α k k! .
Comparing the sum of the areas of rectangles R i , i = 1, ..., kt 0 + 1, with sides a i = α and b i = (n -(i -1)α) k-2 with the area of the figure limited by the x-axis and the graph of the function y

= x k-2 , 0 ≤ x ≤ n + α, we obtain that kt0+1 i=1 α (n -(i -1)α) k-2 ≤ n+α 0 x k-2 dx, hence, kt0+1 i=1 (n -(i -1)α) k-2 ≤ (n + α) k-1 α(k -1) (3)
Therefore,

|E(H)| ≤ (2t 0 + 1) n k-1 (k -1)! + α(n + α) k-1 2(k -1)! + k k α k k! (4) = 1 k! + 1 (k -1)! n k-1/2 + o n k-1/2 , because t 0 ≈ √ n 2k and α ≈ 2 √ n. 2

Concluding remarks

We have constructed a family of k-uniform hamiltonian chain saturated hypergraphs. The main result is Theorem 3, which gives the hypergraphs with the smallest known number of edges. Unfortunately, since the lower bound in [START_REF] Dudek | Hamilton-chain saturated hypergraphs[END_REF] is smaller than the number of edges in our construction by a factor n 1/2 the order of magnitude for sat(C

n ) remains unknown. Note that our construction cannot be significantly improved by taking another t 0 . Indeed, if we take t 0 of order greater than n 1/2 then, the first component of ( 4) is of order greater than n k-1/2 . Otherwise, if t 0 is of order less than n 1/2 , then α is of order greater than n 1/2 , whence the second component of ( 4) is of order greater than n k-1/2 . On the other hand, the coefficient 1 2k is chosen in order to minimize (4) and satisfy all necessary conditions that the numbers p, q, α must have (some slight improvements are still possible, however).

We observe that the same bounds can be obtained in case when we consider hamiltonian paths. The upper bound can be realized by a hypergraph H ∈ H k (2t 0 , kt 0 + 2) with t 0 and α being the same as in Theorem 3.

Theorem 4 For each n ≥ k 4 + 8k 3 + 16k 2 , there exists a k-uniform, hamiltonian path saturated hypergraph with less than 1 k! + 1 (k-1)! n k-1/2 + o n k-1/2 edges.

The authors were partially supported by the Polish Ministry of Science and Higher Education.


Hengzhe Li

Xueliang Li

Yuefang Sun

The generalized 3-connectivity of Cartesian product graphs †

Keywords: Connectivity, Generalized connectivity, Internally disjoint path, Internally disjoint trees

The generalized connectivity of a graph, which was introduced by Chartrand et al. in 1984, is a generalization of the concept of vertex connectivity. Let S be a nonempty set of vertices of G, a collection {T1, T2, . . . , Tr} of trees in G is said to be internally disjoint trees connecting S if E(Ti) ∩ E(Tj) = ∅ and V (Ti) ∩ V (Tj) = S for any pair of distinct integers i, j, where 1 ≤ i, j ≤ r. For an integer k with 2 ≤ k ≤ n, the k-connectivity κ k (G) of G is the greatest positive integer r for which G contains at least r internally disjoint trees connecting S for any set S of k vertices of G. Obviously, κ2(G) = κ(G) is the connectivity of G. Sabidussi's Theorem showed that κ(G H) ≥ κ(G) + κ(H) for any two connected graphs G and H. In this paper, we prove that for any two connected graphs G and

Our result could be seen as an extension of Sabidussi's Theorem. Moreover, all the bounds are sharp.

Introduction

All graphs in this paper are undirected, finite and simple. We refer to the book [START_REF] Bondy | Graph Theory[END_REF] for graph theoretic notations and terminologies not described here. For any graph G, the connectivity κ(G) of a graph G is defined as min{|S| : S ⊆ V (G) and G -S is disconnected or trivial}. Whitney [START_REF] Whitney | Congruent graphs and the connectivity of graphs[END_REF] showed an equivalent definition of the connectivity of a graph. For each pair of vertices x, y of G, let κ(x, y) denote the maximum number of internally disjoint paths connecting x and y in G. Then the connectivity κ(G) of G is min{κ(x, y) : x, y are distinct vertices of G}.

The Cartesian product of graphs is an important method to construct a bigger graph, and plays a key role in design and analysis of networks. In the past several decades, many authors have studied the (edge) connectivity of the Cartesian product graphs. Specially, Sabidussi in [START_REF] Sabidussi | Graphs with given group and given graph theoretical properties[END_REF] derived the following prefect and well-known theorem on the connectivity of Cartesian product graphs.

Theorem 1.1 (Sabidussi's Theorem [START_REF] Sabidussi | Graphs with given group and given graph theoretical properties[END_REF]) Let G and H be two connected graphs. Then κ(G H) ≥ κ(G) + κ(H).

More information about the (edge) connectivity of the Cartesian product graphs can be found in [START_REF] Chiue | On connectivity of the Cartesian product of two graphs[END_REF][START_REF] Imrich | Product Graphs Structure and Recongnition[END_REF][START_REF] Klavžar | On the edge-connectivity of Cartesian product graphs[END_REF][START_REF] Sabidussi | Graphs with given group and given graph theoretical properties[END_REF][START_REF] Špacapan | Connectivity of Cartesian products of graphs[END_REF][START_REF] Wilfried | Topics in Graph Theory[END_REF][START_REF] Xu | Connectivity of Cartesian product graphs[END_REF].

The generalized connectivity of a graph G, which was introduced by Chartrand et al. in [START_REF] Chartrand | Generalized connectivity in graphs[END_REF], is a natural and nice generalization of the concept of vertex connectivity. A tree T is called an S-tree ({u 1 , u 2 , . . . , u k }-tree) if S ⊆ V (T ), where S = {u 1 , u 2 , . . . , u k } ∈ V (G). A family of trees T 1 , T 2 , . . . , T r are internally disjoint S-trees if E(T i ) ∩ E(T j ) = ∅ and V (T i ) ∩ V (T j ) = S for any pair of integers i and j, where 1 ≤ i < j ≤ r. We use κ(S) to denote the greatest number of internally disjoint S-trees. For an integer k with 2

≤ k ≤ n, the k-connectivity κ k (G) of G is defined as min{κ(S) | S ∈ V (G) and |S| = k}. Clearly, when |S| = 2, κ 2 (G) is nothing new but the connec- tivity κ(G) of G, that is, κ 2 (G) = κ(G)
, which is the reason why one addresses κ k (G) as the generalized connectivity of G. By convention, for a connected graph G with less than k vertices, we set

κ k (G) = 1. For any graph G, clearly, κ(G) ≥ 1 if and only if κ k (G) ≥ 1.
In addition to being a natural combinatorial measure, the generalized connectivity can be motivated by its interesting interpretation in practice. For example, suppose that G represents a network. If one considers to connect a pair of vertices of G, then a path is used to connect them. However, if one wants to connect a set S of vertices of G with |S| ≥ 3, then a tree has to be used to connect them. This kind of tree with minimum order for connecting a set of vertices is usually called a Steiner tree, and popularly used in the physical design of VLSI, see [START_REF] Sherwani | Algorithms for VLSI physical design automation[END_REF]. Usually, one wants to consider how tough a network can be, for the connection of a set of vertices. Then, the number of totally independent ways to connect them is a measure for this purpose. The generalized k-connectivity can serve for measuring the capability of a network G to connect any k vertices in G.

In [START_REF] Li | Note on the hardness of generalized connectivity[END_REF], Li and Li investigated the complexity of determining the generalized connectivity and derived that for any fixed integer k ≥ 2, given a graph G and a subset S of V (G), deciding whether there are k internally disjoint trees connecting S, namely deciding whether κ(S) ≥ k, is NP-complete. The generalized connectivity of complete bipartite graphs was studied by Okamoto and Zhang in [START_REF] Okamoto | The tree connectivity of regular complete bipartite graphs[END_REF], and Li and Li in [START_REF] Li | The generalized connectivity of complete bipartite graphs[END_REF].

Chartrand et al. [START_REF] Chartrand | Rainbow trees in graphs and generalized connectivity[END_REF] got the following result for complete graphs.

Theorem 1.2 [START_REF] Chartrand | Rainbow trees in graphs and generalized connectivity[END_REF] For every two integers n and k with 2

≤ k ≤ n, κ k (K n ) = n -k/2 .
Theorem 1.3 [START_REF] Li | Sharp bounds for the generalized connectivity κ 3 (G)[END_REF] Let G be a connected graph with at least three vertices. If G has two adjacent vertices with minimum degree δ, then κ 3 (G) ≤ δ -1.

Theorem 1.4 [START_REF] Li | Sharp bounds for the generalized connectivity κ 3 (G)[END_REF] For any connected graph G, κ 3 (G) ≤ κ(G). Moreover, the upper bound is sharp.

In this paper, we study the 3-connectivity of Cartesian product graphs and get the following result.

Theorem 1.5 Let G and H be connected graphs such that κ 3 (G) ≥ κ 3 (H). The following assertions hold:

(i) If κ(G) = κ 3 (G), then κ 3 (G H) ≥ κ 3 (G) + κ 3 (H) -1.
Moreover, the bound is sharp;

(ii) If κ(G) > κ 3 (G), then κ 3 (G H) ≥ κ 3 (G) + κ 3 (H).
Moreover, the bound is sharp.

The paper is organized as follows. In Section 2, we recall the definition and properties of Cartesian product graphs, and give some basic results about the internally disjoint S-trees. As usual, in order to get a general result, we begin with a special case. In Section 3, we study the 3-connectivity of the Cartesian product of a graph G and a tree T . This section is a preparation of Section 4. In Section 4, we study the 3-connectivity of the Cartesian product of two connected graphs G and H. Moreover, all the bounds are sharp. Our result could be seen as an extension of Theorem 1.1.

Some basic results

We use P n to denote a path with n vertices. A path P is called a u-v path, denoted by P u,v , if u and v are the endpoints of P .

Recall that the Cartesian product (also called the square product) of two graphs G and H, written as G H, is the graph with vertex set V (G) × V (H), in which two vertices (u, v) and (u , v ) are adjacent if and only if u = u and

(v, v ) ∈ E(H), or v = v and (u, u ) ∈ E(G). Clearly, the Cartesian product is commutative, that is, G H ∼ = H G. The edge (u, v)(u , v ) is called one-type edge if (u, u ) ∈ E(G) and v = v ; similarly, the (u, v)(u , v ) is called two-type edge if u = u and (v, v ) ∈ E(H).
Let G and H be two graphs with

V (G) = {u 1 , u 2 , . . . , u n } and V (H) = {v 1 , v 2 , . . . , v m }, respec- tively. We use G(u j , v i ) to denote the subgraph of G H induced by the set {(u j , v i ) | 1 ≤ j ≤ n}. Similarly, we use H(u j , v i ) to denote the subgraph of G H induced by the set {(u j , v i ) | 1 ≤ i ≤ m}. It is easy to see G(u j1 , v i ) = G(u j2 , v i ) for different u j1 and u j2 of G. Thus, we can replace G(u j , v i ) by G(v i ) for simplicity. Similarly, we can replace H(u j , v i ) by H(u j ). For any u, u ∈ V (G) and v, v ∈ V (G), (u, v), (u, v ) ∈ V (H(u)), (u , v), (u , v ) ∈ V (H(u )), (u, v), (u , v) ∈ V (G(v)), and (u, v ), (u , v ) ∈ V (G(v)). We refer to (u, v ) and (u , v) as the vertices corresponding to (u, v) in G(v ) ( = G(u, v ) ) and H(u ) ( = H(u , v) )
, respectively. Similarly, we can define the path and tree corresponding to some path and tree, respectively.

In order to show our main results, we need the following well-known theorem.

Theorem 2.1 (Menger's Theorem [START_REF] Bondy | Graph Theory[END_REF]) Let G be a k-connected graph, and let x and y be a pair of distinct vertices in G. Then there exist k internally disjoint paths P 1 , P 2 , . . . , P k in G connecting x and y.

Let G be a connected graph, and S = {x 1 , x 2 , x 3 } ⊆ V (G). We first have the following observation about internally disjoint S-trees.

Observation 2.1 Let G be a connected graph, S = {x 1 , x 2 , x 3 } ⊆ V (G), and T be an S-tree. Then there exists a subtree T of T such that T is also an S-tree such that

1 ≤ d T (x i ) ≤ 2, |{x i | d T (x i ) = 1}| ≥ 2 and {x | d T (x) = 1} ⊆ S. Moreover, if |{x i | d T (x i ) = 1}| = 3,
then all the vertices of V (T ) \ {x 1 , x 2 , x 3 } have degree 2 except for one vertex, say x with d T (x) = 3; if there exists one vertex of S, say x 1 , of degree 2 in T , then T is an x 2 -x 3 path.

Proof: It is easy to check that this observation holds by deleting vertices and edges of T . 2 Remark 2.1 (i) Since the path between any two distinct vertices is unique in T , the tree T obtained from T in Observation 2.1 is unique. Such a tree is called a minimal S-tree (or minimal {x 1 , x 2 , x 3 }-tree).

(ii) Let S = {x, y, z} ⊆ V (G). Throughout this paper, we can assume that each S-tree is a minimal S-tree. Lemma 2.1 Let G be a graph with κ 3 (G) = k ≥ 2, S = {x, y, z} ⊆ V (G). Then, the following assertions hold:

(i) If G[S] is a clique, then there exist k internally disjoint S-trees T 1 , T 2 , . . . , T k , such that E(T i ) ∩ E(G[S]) = ∅ for 1 ≤ i ≤ k -2. (ii) If G[S]
is not a clique, then there exist k internally disjoint S-trees T 1 , T 2 , . . . , T k , such that

E(T i ) ∩ E(G[S]) = ∅ for 1 ≤ i ≤ k -1.
Proof: We first prove (i). Clearly, by the definition of S-trees, we know

|{T i | E(T i ) ∩ E(G[S]) = ∅}| ≤ 3. Let {T 1 , T 2 , . . . , T k } be k internally disjoint S-trees. If |{T i | E(T i )∩E(G[S]) = ∅}| ≤ 2, we are done by exchanging subscript. Thus, suppose |{T i | E(T i ) ∩ E(G[S]) = ∅}| = 3. Without loss of generality, we assume E(T i ) ∩ E(G[S]) = ∅, where i = k -2, k -1, k. It is easy to check that T k-2 , T k-1 , T k must
have the structures as shown in Figures 1 a andc. But, for these two cases, we can obtain

T k-2 , T k-1 , T k from T k-2 , T k-1 , T k , such that E(T k-2 ) ∩ {xy, xz, yz} = ∅. See Figs. 1b
. and 1d, where the tree T k-2 is shown by dotted lines. Thus T 1 , T 2 , . . . , T k-3 , T k-2 , T k-1 , T k are our desired S-trees.

The proof of (ii) is similar to that of (i), and thus is omitted. 2

Fig. 1a. Remark 2.2 Let G be a graph with

κ 3 (G) = k ≥ 2, S = {x, y, z} ⊆ V (G). If |{T i | E(T i )∩E(G[S]) = ∅}| ≥ 2 for any collection T of k internally disjoint S-trees, then G[S] is a clique. Moreover, T k-1 ∪ T k
must have the structure as shown in Figure 1e.

3 The Cartesian product of a connected graph and a path

In this section, we show the following proposition.

Proposition 3.1 Let G be a graph and P m be a path with m vertices. The following assertions hold:

(i) If κ 3 (G) = κ(G) ≥ 1, then κ 3 (G P m ) ≥ κ 3 (G).
Moreover, the bound is sharp;

(ii) If 1 ≤ κ 3 (G) < κ(G), then κ 3 (G P m ) ≥ κ 3 (G) + 1.
Moreover, the bound is sharp.

We shall prove Proposition 3.1 by a series of lemmas. Since the proofs of (i) and (ii) are similar, we only show (ii). Let G be a graph with

V (G) = {u 1 , u 2 , . . . , u n } such that 1 ≤ κ 3 (G) < κ(G), V (P m ) = {v 1 , v 2 , . . . , v m } such that v i and v j are adjacent if and only if |i -j| = 1.
Set κ 3 (G) = k for simplicity. To prove (ii), we need to show that for any S = {x, y, z} ⊆ V (G H), there exist k + 1 internally disjoint S-trees. We proceed our proof by the following three lemmas. Lemma 3.1 If x, y, z belongs to the same V (G(v i )), 1 ≤ i ≤ m, then there exist k + 1 internally disjoint S-trees.

Proof: Without loss of generality, we assume x, y, z ∈ V (G(v 1 )). Since κ 3 (G) = k, there exist k internally disjoint S-trees T 1 , T 2 , . . . , T k in G(v 1 ). We need another S-tree T k+1 such that T k+1 and T i are internally disjoint, for i = 1, 2, . . . , k. Let x , y , z be the vertices corresponding to x, y, z in G(v 2 ), and T 1 be the tree corresponding to T 1 in G(v 2 ). Therefore, tree T k+1 obtained from T 1 by adding three edges xx , yy , zz is a desired tree. 2 Lemma 3.2 If only two vertices of {x, y, z} belong to some copy G(v i ), then there exist k + 1 internally disjoint S-trees.

Proof: We may assume x, y ∈ V (G(v 1 )), z ∈ V (G(v 2 )). In the following argument, we can see that this assumption has no influence on the correctness of our proof. Let x , y be the vertices corresponding to x, y in G(v 2 ), z be the vertex corresponding to z in G(v 1 ). Consider the following two cases.

x y y

z ′ z ′ x y z ′ x ′ y ′ z x y z ′ x ′ y ′ z 2a 2b 2d 2e y z ′ 2c x x G(v 1 ) G(v 2 ) G(v 1 ) G(v 2 )
Fig. 2: edges (or paths) of a tree are shown by the same type of lines. The lightest lines stand for edges (or paths) not contained in T * i .

Case 1: z ∈ {x, y}.

Let S = {x, y, z }, and T 1 , T 2 , . . . T k be k internally disjoint S -trees in G(v 1 ) such that

|{T i | E(T i )∩E(G(v 1 )
[S ]} = ∅| is as small as possible. We can assume that E(T i )∩E(G(v 1 )[S ]) = ∅ for each i, where 1 ≤ i ≤ k -2 by Lemma 2.1.

For a tree T i with E(T i ) ∩ E(G(v 1 )[S ]) = ∅, let T * i be the tree obtained from T i by adding z i z i and z i z, and deleting z , where z i is any one neighbor of z in T i , and z i is the vertex corresponding to z i in G(v 2 ). Without loss of generality, assume z = y. Since κ(G) > κ 3 (G) = k, by Menger's Theorem, there exist at least k + 1 internally disjoint x-y paths P 1 , P 2 , . . . , P k+1 in G(v 1 ). Assume that y i is the only neighbor of y in P i , and that y i is the vertex corresponding to y i in G(v 2 ). If x and y are nonadjacent in P i , let T i be the tree obtained from P i by adding y i y i and y i z. If x and y are adjacent in P i , let T i be the tree obtained from P i by adding yz. Since G is a simple graph, there exists at most one path P i such that x and y are adjacent on P i . Thus T i , 1 ≤ i ≤ k + 1, are k + 1 internally disjoint S-trees. Proof: We may assume that

If E(T k ) ∩ E(G(v 1 )[S ]) = ∅, say yz ∈ E(T k ) ∩ E(G(v 1 )[S ]). Let T * k = T k + zz and T * k+1 = T k + xx + yy , where T k is the tree corresponding to T k in G(v 2 ). If E(T k-1 ) ∩ E(G(v 1 )[S ]) = ∅ and E(T k ) ∩ E(G(v 1 )[S ]) = ∅. Then T k-1 ∪ T k must
x ∈ V (G(v 1 )), y ∈ V (G(v 2 )), z ∈ V (G(v 3 )).
In the following argument, we can see that this assumption has no influence on the correctness of our proof. Let y , z be the vertices corresponding to y, z in G(v 1 ), x , z be the vertices corresponding to x, z in G(v 2 ) and x , y be the vertices corresponding to x, y in G(v 3 ). We consider the following three cases.

Case 1: x, y , z are distinct vertices in G(v 1 )

Let S = {x, y , z }, and

T 1 , T 2 , . . . T k be k internally disjoint S -trees in G(v 1 ) such that |{T i | E(T i ) ∩ E(G(v 1 )[S ]) = ∅}| is as small as possible. We can assume that E(T i ) ∩ E(G(v 1 )[S ]) = ∅ for each i, where 1 ≤ i ≤ k -2 by Lemma 2.1. For each T i such that E(T i ) ∩ E(G(v 1 )[S ]) = ∅, we can obtain an S-tree T * i from T i similar to that in Subcase 1.1 of Lemma 3.2. If E(T k-1 ) ∩ E(G(v 1 )[S ]) = ∅ or E(T k-1 ) ∩ E(G(v 1 )[S ]) = ∅. Without loss of generality, we assume E(T k-1 ) ∩ E(G(v 1 )[S ]) = ∅. Let T *
k be the tree obtained from T k by adding edges y y, z z and z z, T * k+1 be the tree obtained from T k by adding x x , x x and y y, where T k is the tree corresponding to T k in G(v 3 ). Thus, Since κ(G) > κ 3 (G) = k, by Menger's Theorem, it is easy to construct k + 1 internally disjoint S-trees. See Figure 3h.

T * i s, 1 ≤ i ≤ k + 1, are k internally disjoint S-tree. Otherwise, that is, E(T k-1 )∩E(G(v 1 )[S ]) = ∅ and E(T k )∩E(G(v 1 )[S ]) = ∅. Then T k-

2

We have the following observation by the argument in the proof of Proposition 3.1.

Observation 3.1 The k + 1 internally disjoint S-trees consist of three kinds of edges -the edges of original trees (or paths), the edges corresponding the edges of original trees (or paths) and two-type edges.

Note that Q n ∼ = P 2 P 2 • • • P 2 , where Q n is the n-hypercube. We have the following corollary. Proof: Recall that κ(Q n ) = n so that Proposition 3.1 (ii) inductively applies. It is easy to check that κ 3 (Q 2 ) = 1. Suppose that the result holds for Q n-1 , where n ≥ 3. We have κ 3 (Q n ) ≥ n -1 by Proposition 3.1. On the other hand, since Q n is n-regular, we have

κ 3 (Q n ) ≤ n -1 by Theorem 1.3. Thus κ 3 (Q n ) = n -1. 2
Example 3.1 Let K 2n be the complete graph with vertex set V (K 2n ) = {u 1 , u 2 , . . . , u 2n }, and let G n be the graph obtained from K 2n by adding a new vertex u and edges uu i , 1 ≤ i ≤ n.

For any S = {x, y, z} ⊆ V (G), if u ∈ S, then there exist k internally disjoint S-trees in G n by Theorem 1.2. If u ∈ S, without loss of generality, assume x = u, y = u 1 , z = u 2 . Let T 1 be the path u, u 1 , u k+1 , u 2 , T 2 be the path u, u 2 , u k+2 , u 1 , and T i be the tree obtained from a path u, u n+i , u 1 by adding an edge

u n+i u 2 for 3 ≤ i ≤ n. Clearly, T i , 1 ≤ i ≤ n, are n internally disjoint S-trees. So κ 3 (G n ) ≥ n. Since δ(G n ) = n, κ 3 (G n ) = n by Theorem 1.4. By Proposition 3.1, κ 3 (G n K 2 ) ≥ n. Since G n has two adjacent vertices of degree n + 1, κ 3 (G n ) = n by Theorem 1.3. Moreover, clearly, κ(G) = n. Thus κ 3 (G K 2 ) = κ 3 (G) = n.
′ y ′ 3a 3b 3c y ′ z ′ y ′ z ′ x y ′ y ′ x x x x ′ x ′′ z ′ z ′′ z y ′ y y ′′ G(v 1 ) G(v 2 ) G(v 3 ) 3d. T * k and T * k+1 x x ′ x ′′ z ′ z z ′′ y ′ y y ′′ G(v 1 ) G(v 2 ) G(v 3 ) 3e T * k-1 , T * k and T * k+1 x x ′ x ′′ z ′ z ′′ z y ′ y y ′′ G(v 1 ) G(v 2 ) G(v 3 ) 3f. T * k and T * k+1 x y z G(v 1 ) G(v 2 ) G(v 3 ) 3g. T 1 , T 2 , ..., T k+1 y ′ (z ′ ) x ′ x ′′ x y z G(v 1 ) G(v 2 ) G(v 3 ) 3h. T 1 , T 2 , ..., T k+1 w w ′′ w ′
* i . G(x) G(y) G(z) G(y) G(z) G T k G T 1 k Fig. 4: The structure of G k i=1 Ti. G(x) G(w) G(y) G(z) G(x) G(w) G(y) G(z) G(x) G(y) G(z) H T 1 T 2 G (T 1 ∪ T 2 ) G T 1 G T 2 x y z w x w y z x y z Fig. 5: The structure of G (T1 ∪ T2). G i ∩ G j = G(v 1 ) ∪ G(v 2 ) ∪ G(v 3 ) for i = j. Let y , z be the vertices corresponding to y, z in G(v 1 ), respectively. If x, y , z are distinct vertices in G(v 1 ). Since κ 3 (G(v 1 )) = k, there exist k internally disjoint {x, y , z }-trees T j , 1 ≤ j ≤ k, in G(v 1 ). Let k 0 , k 1 , . . . , k be integers such that 0 = k 0 < k 1 < • • • < k = k. Similar to the proofs of Proposition 3.1, we can construct k i -k i-1 + 1 internally disjoint S-trees T i,ji , 1 ≤ j i ≤ k i -k i-1 + 1, in ( ki j=ki-1+1 T j ) T i
for each i, where 1 ≤ i ≤ . By Observations 3.1 and 3.2, T i,ji and T r,jr are internally disjoint for i = r. Thus T

i,ji , 1 ≤ i ≤ , 1 ≤ j i ≤ k i -k i-1 + 1 are k + internally disjoint S-trees.
If exactly two of x, y , z are the same vertex in G(v i ). Without loss of generality, assume y = z . Since κ(G(v 1 )) > k, there exist k + 1 internally disjoint xy paths P i , 1 ≤ i ≤ k + 1, in G(v 1 ) by Menger's Theorem. Note that at most one of them is a path of length 1. Let P k+1 be such a path if xy ∈ E(G(v 1 )), and let k 0 , k 1 , . . . , k be integers such that 0 = k 0 < k 1 < • • • < k = k + 1. Similar to the proofs of Proposition 3.1, we can construct k ik i-1 + 1 internally disjoint S-trees T i,ji , 1 ≤ j i ≤ k ik i-1 + 1, in ( ki j=ki-1+1 P j ) T i for each i, where 1 ≤ i ≤ -1, and kk -1 internally disjoint S-trees T ,j , 1 ≤ j i ≤ kk -1 , in ( k j=k -1 +1 P j ) T i . By Observation 3.1 and 3.2, T i,ji and T r,jr are internally disjoint for i = r. Thus T i,ji , 1 ≤ i ≤ , 1 ≤ j i ≤ k ik i-1 + 1 are k + internally disjoint S-trees.

If all of x, y , z are the same vertex in G(v i ). Since δ(G(v 1 )) ≥ κ(G(v 1 )) > k, x has k neighbors, say x 1 , x 2 , . . . , x k , in G(v 1 )). Let P i be the path xx i , and let k 0 , k 1 , . . . , k be integers such that 0 = k 0 < k 1 < • • • < k = k. Similar to the proofs of Proposition 3.1, we can construct k ik i-1 + 1 internally disjoint S-trees T i,ji , 1 ≤ j i ≤ k ik i-1 + 1, in ( ki j=ki-1+1 P j ) T i for each i, where 1 ≤ i ≤ . By Observation 3.1 and 3.2, T i,ji and T r,jr are internally disjoint for i = r. Thus T i,ji , 1 ≤ i ≤ , 1 ≤ j i ≤ k ik i-1 + 1 are k + internally disjoint S-trees.

We now show that bounds of Theorem 1.5 are sharp. For (i), Example 3.1 is a sharp example. Let K n be a complete graph with n vertices, and P m be a path with m vertices, where m ≥ 2. We have κ 3 (P m ) = 1, and κ 3 (K n ) = n -2 by Theorem 1.2. It is easy to check that κ 3 (K n P m ) = n -2 + 1 = n -1. Thus, K n P m is a sharp example for (ii).

2

Fig

  Fig. 1d.

Fig. 1 :

 1 Fig. 1: T k-2 , T k-1 , T k . An edge is shown by a straight line. The edges (or paths) of a tree are shown by the same type of lines.

  have one of the structures as shown in Figures 2 a, b and c by Remark 2.2. If T k-1 and T k have the structures as shown in Figure 2a, then we can obtain trees T * k-1 , T * k and T * k+1 as shown in Figure 2d. If T k-1 and T k have the structures as shown in Figure 2b, then we can obtain trees T * k-1 , T * k and T * k+1 as shown in Figure 2e. If T k-1 and T k have the structures as shown in Figure 2c, then we can obtain trees T * k-1 , T * k and T * k+1 similar to those in Figure 2d. Case 2: z ∈ {x, y}.

2 Lemma 3 . 3

 233 If x, y, z are contained in distinct G(v i )s, then there exist k + 1 internally disjoint S-trees.

  1 and T k must have the structures as shown in Figure 3a, b and c. If T k-1 and T k have the structures as shown in Figure 3a, then we can obtain trees T * k-1 , T * k and T * k+1 as shown in Figure 3d. If T k-1 and T k have the structures as shown in Figure 3b, then we can obtain trees T * k-1 , T * k and T * k+1 as shown in Figure 3e. If T k-1 and T k have the structures as shown in Figure 3c, then we can obtain trees T * k-1 , T * k and T * k+1 as shown in Figure 3f. Case 2: Two of x, y , z are the same vertex in G(v 1 ). If y = z , since κ(G) > κ 3 (G) = k, by Menger's Theorem, it is easy to construct k + 1 internally disjoint S-trees. See Figure 3g. The other cases (x = y or x = z ) can be proved with similar arguments.Case 3: x, y , z are the same vertex in G(v 1 ).

Corollary 3 . 1

 31 Let Q n be the n-hypercube with n ≥ 2. Then κ 3 (Q n ) = n -1.

Remark 3 . 1

 31 We know that the bounds of (i) and (ii) in Theorem 3.1 are sharp by Example 3.1 and Corollary 3.1.

  z

Fig. 3 :

 3 Fig. 3: The edges (or paths) of a tree are shown by the same type of lines. The lightest lines stand for edges (or paths) not contained in T * i .

Acknowledgments

We thank anonymous reviewers for their carefully reading of our work and their helpful suggestions.

Supported by NSFC No. 11071130.

Proposition 3.2 Let G be a connected graph and T be a tree. The following assertions hold:

(i) If κ 3 (G) = κ(G) ≥ 1, then κ 3 (G T ) ≥ κ 3 (G). Moreover, the bound is sharp;

Moreover, the bound is sharp.

Proof: Since the proofs of (i) and (ii) are similar, we only show (ii). It suffices to show that for any

)) be three distinct vertices. If there exists a path in T containing v i , v j and v k , then we are done from Proposition 3.1. If i, j and k are not distinct integers, such a path must exist. Thus, suppose that i, j and k are distinct integers, and that there exists no path containing v i , v j and v k . By Observation 2.1, there exists a tree

Without loss of generality, we set i = 1, j = 2, k = 3. Furthermore, we assume v i v 4 ∈ E(T ), where 1 ≤ i ≤ 3. In the following argument, we can see that this assumption has no influence on the correctness of our proof.

Let P be the unique path in T connecting v 1 and v 2 . By Proposition 3.1, we can construct k + 1 internally disjoint {x, y, z }-trees T i , 1 ≤ k + 1, in G P , where z is the vertex corresponding to z in G(v 4 ). By a similar method of Proposition 3.1, we can construct k + 1 internally disjoint S-trees in G T on the basis of these trees. 4 The Cartesian product of two general graphs

In order to show the structure of G k i=1 T i clearly, we take k copies of G(y), and k copies of G(z). Note that, these k copes of G(y) (resp. G(z)) represent the same graph.

)) be three distinct vertices in G H. We will do only the case that i, j, k are distinct integers. Other two possibilities are similar. Without loss of generality, set i = 1, j = 2, k = 3. Since κ 3 (H) = , there exist internally disjoint {v 1 , v 2 , v 3 }-trees T i , 1 ≤ i ≤ , in H. We use G i to denote G T i . By Observation 4.1, we know that G i=1 T i = i=1 G i and


Yoshio Okamoto
email: okamotoy@uec.ac.jp.

Yota Otachi
email: otachi@jaist.ac.jp.

Ryuhei Uehara
email: uehara@jaist.ac.jp.

On bipartite powers of bigraphs

Keywords: Bipartite power, Interval bigraph, Bipartite permutation graph, Closure property, NP-completeness

The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.

Introduction

For a positive integer k, the kth power G k of a graph G has the same vertex set as G, and two vertices are adjacent in G k if and only if their distance in G is at most k. If H k = G, then H is called a kth root of G. (In general, kth roots of a graph are not unique and do not necessarily exist.) The concept of graph powers has been extensively studied in graph theory and its algorithmic applications (see [START_REF] Prisner | Graph Dynamics[END_REF] and the references therein). It is known that several important graph classes are closed under the power operation. That is, for some graph class C, G ∈ C implies G k ∈ C as well. The recognition problem has also been studied for graph powers. It was shown that recognizing graph powers is NP-complete in general while it is solvable in polynomial time for some special graph classes [START_REF] Chang | Linear-time algorithms for tree root problems[END_REF]; [START_REF] Farzad | Computing graph roots without short cycles[END_REF]; [START_REF] Kearney | Tree powers[END_REF]; [START_REF] Lau | Bipartite roots of graphs[END_REF]; [START_REF] Lau | Recognizing powers of proper interval, split, and chordal graphs[END_REF]; [START_REF] Le | Hardness results and efficient algorithms for graph powers[END_REF]; [START_REF] Lin | Algorithms for square roots of graphs[END_REF]; [START_REF] Motwani | Computing roots of graphs is hard[END_REF]).

A graph is bipartite if its vertices can be partitioned into two parts in such a way that the endpoints of every edge belong to different parts. Bipartite graphs are also known as bigraphs. It is known that the class of bigraphs coincides with the class of graphs with no cycle of odd length. If a bigraph is connected and has at least three vertices, then clearly its kth power (for k ≥ 2) has a cycle of length three. Hence, the class of bigraphs is not closed under the power operation. Furthermore, any non-trivial subclass of the class of bigraphs is not closed under the power operation. [START_REF] Chandran | Chordal bipartite graphs with high boxicity[END_REF] introduced a bipartite analogue of graph powers. For odd k ∈ Z + , the kth bipartite power G [k] of a bigraph G has the same vertex set as G, and two vertices are adjacent in G [k] if and only if their distance in G is at most k and odd. It is easy to see that G [k] is also bipartite. They showed that for any tree T and for any odd k, T [k] is a chordal bipartite graph. They used this fact to prove that chordal bipartite graphs can have arbitrarily large boxicity. Recently, [START_REF] Chandran | Bipartite powers of k-chordal graphs[END_REF] have strengthened the closure-property result by showing that the class of chordal bipartite graphs is closed under the bipartite power operation.

In this paper, we complement the known closure-property results by proving that some subclasses of the class of chordal bipartite graphs are closed under the bipartite power operation. Note that the closure property of a graph class C under the bipartite power operation is not implied by the closure property of a superclass of C, and vice versa. We also focus on the computational complexity of the problem for recognizing the kth bipartite power graphs. We prove that given a bipartite graph G, the problem of determining whether there exists a bipartite graph H such that G = H [k] is NP-complete for any fixed odd k ≥ 3.

Preliminaries

In this paper, graphs are finite, simple, and undirected. We denote by N G (v) the neighborhood of a vertex v in a graph G. We denote by dist G (u, v) the distance between u and v in G.

A graph

G = (V, E) with V = {1, 2, . . . , n} is a permutation graph if there is a permutation π over V such that {i, j} ∈ E(G) if and only if (i -j)(π(i) -π(j)) < 0. A graph is a bipartite permutation graph if it is bipartite and a permutation graph. A bi-interval representation of a bigraph G = (U, V ; E) is a pair (I U , I V ) of sets of closed intervals such that I U = {[ u , r u ] | u ∈ U } and I V = {[ v , r v ] | v ∈ V }, and {u, v} ∈ E(G) if and only if [ u , r u ] ∩ [ v , r v ] = ∅ for u ∈ U and v ∈ V . A bi-interval representation (I U , I V ) is unit if for each interval [ , r] ∈ I U ∪ I V , r -= 1.
A bigraph is an interval bigraph if it has a bi-interval representation. An interval bigraph is a unit interval bigraph if it has a unit bi-interval representation. A bigraph is a chordal bipartite graph if every induced cycle is of length four. We denote the classes of bipartite permutation graphs, unit interval bigraphs, interval bigraphs, and chordal bipartite graphs by BP, UIB, IB, and CB, respectively. The following relations among these classes are known.

Theorem 2.1 [START_REF] Hell | Interval bigraphs and circular arc graphs[END_REF]; M üller (1997)) BP = UIB ⊂ IB ⊂ CB.

Closure properties of bipartite powers of bigraphs

It is known that several important (non-bipartite) graph classes are closed under the power operation. For example, the classes of unit interval graphs, interval graphs, strongly chordal graphs are closed under the kth power for any k [START_REF] Chen | Families of graphs closed under taking powers[END_REF]; [START_REF] Dahlhaus | On strongly chordal graphs[END_REF]; [START_REF] Lubiw | Doubly lexical ordering of matrices[END_REF]; [START_REF] Raychaudhuri | On powers of interval and unit interval graphs[END_REF][START_REF] Raychaudhuri | On powers of strongly chordal and circular arc graphs[END_REF]). On the other hand, few things are known on bipartite powers of bigraphs. To the best of our knowledge, the following is the only known closure property.

Theorem 3.1 [START_REF] Chandran | Bipartite powers of k-chordal graphs[END_REF]) If G is a chordal bipartite graph, then so is G [k] for any odd k ∈ Z + .

In this section, we show that the closure property holds also for smaller graph classes.

Theorem 3.2 If G is an interval bigraph, then so is G [k] for any odd k ∈ Z + . Theorem 3.3 If G is a bipartite permutation graph, then so is G [k] for any odd k ∈ Z + .
We note that the closure property is not hereditary for the graph classes. That is, Theorem 3.1 does not imply Theorem 3.2, and Theorem 3.2 does not imply Theorem 3.3.

Bipartite powers of interval bigraphs

Now we prove Theorem 3.2. Let G = (U, V ; E) be an interval bigraph, and (I U , I V ) be a bi-interval representation of G. For odd k ∈ Z + and

I w ∈ I U ∪ I V , we form a new interval I w (k) = [ w , r w (k)], where r w (k) = max{l x | dist G (w, x) is odd and at most k}.
This extension of intervals is inspired by the proof of [START_REF] Agnarsson | On powers of chordal graphs and their coloring[END_REF], who showed that the kth power of an interval graph is also an interval graph. Note that

I u ∩ I v = ∅ if and only if max{ u , v } ≤ min{r u , r v }.
The following two lemmas show that for u ∈ U , v ∈ V , and odd

k ∈ Z + , I u (k)∩I v (k) = ∅ if and only if dist G (u, v) ≤ k. Since u ∈ U and v ∈ V , clearly dist G (u, v) is odd.
Thus we have the theorem by the two lemmas.

In what follows, we assume u ∈ U and v ∈ V . We also assume that G is connected. It is easy to see that if Theorem 3.2 is valid for connected graphs, then it is also valid for disconnected graphs.

Lemma 3.4 If dist G (u, v) ≤ k, then I u (k) ∩ I v (k) = ∅. Proof: Without loss of generality, we assume u ≤ v . Since dist G (u, v) is odd and at most k, it holds that v ≤ r u (k) from the definition of r u (k). Hence v ∈ [ u , r u (k)] = I u (k), and thus I u (k) ∩ I v (k) = ∅. 2 Lemma 3.5 If I u (k) ∩ I v (k) = ∅, then dist G (u, v) ≤ k.
Proof: Without loss of generality, we assume u ≤ v . By this assumption and

I u (k) ∩ I v (k) = ∅, it holds that u ≤ v ≤ r u (k). Let v ∈ V be a vertex such that dist G (u, v ) ≤ k and r u (k) = v . Let P = (u 0 , v 1 , u 2 , . . . , u 2d , v 2d+1 ) denote a shortest u-v path in G, where u 0 = u and v 2d+1 = v . Clearly, 2d + 1 ≤ k. If {v, u i } ∈ E(G) for some i, there is a u-v path (u 0 , v 1 , u 2 . . . , v i-1 , u i , v) of length i + 1 ≤ 2d + 1 ≤ k in G
and this implies that dist G (u, v) ≤ k. Hence, we assume there is no such index i. Then, the following claim holds.

Claim 3.6 There is some index j such that I v ⊆ I vj .

Proof (Claim 3.6): Since I v does not intersect with any I ui , we can partition U ∩ V (P ) into two parts

L(P ) = {u i | r ui < v } and R(P ) = {u i | r v < ui }. By the assumption u ≤ v and {u, v} = {u 0 , v} / ∈ E(G), it holds that r u < v . Furthermore, since v ≤ r u (k) = v and {u 2d , v } = {u 2d , v 2d+1 } ∈ E(G), we have v ≤ v ≤ r u 2d . Because {u 2d , v} / ∈ E(G)
, it holds that r v < u 2d . Hence, both L(P ) and R(P ) are non-empty since u ∈ L(P ) and u 2d ∈ R(P ). Since P is a connected subgraph of G, there is a vertex v j that has neighbors both in L(P ) and in R(P ). Then, the corresponding interval I vj contains I v (see Fig. 1).

2

Since G is connected, v has a neighbor u in G. Thus, we have I v ∩I u = ∅, which implies I u ∩I vj = ∅. It is easy to see that (u 0 , v 1 , . . . , u j-1 , v j , u , v) is a u-v path of length j + 2, where j -1 ≤ 2d -2. Therefore, the lemma holds.

2

ℓ u r u ℓ u 2d r u 2d ℓ v r v L(P ) R(P ) ℓ v j r v j
Fig. 1: The bridge interval Iv j between L(P ) and R(P ).

Bipartite powers of bipartite permutation graphs

Next we prove Theorem 3.3. An asteroidal triple is a set of three pairwise non-adjacent vertices such that there is a path between any pair of them avoiding the neighbors of the third. If a graph has no asteroidal triple, then it is AT-free. We use the following characterization of bipartite permutation graphs.

Theorem 3.7 (Hell and Huang ( 2004)) A bipartite graph is a permutation graph if and only if it is ATfree.

By the theorem above, it is sufficient to show the following lemma. Our proof is inspired by the proof of [START_REF] Raychaudhuri | On powers of interval and unit interval graphs[END_REF], who proved that the kth power of an AT-free graph is also AT-free.

Lemma 3.8 If G is bipartite and AT-free, then so is G [k] for any odd k ∈ Z + .

Proof: Let v 1 , v 2 , v 3 be any pairwise non-adjacent triple of vertices in G. Without loss of generality, assume that any v 1 -v 2 path in G passes through a neighbor of v 3 . We shall prove that any v 1 -v 2 path in G [k] passes through a neighbor of v 3 .

Let P = (u 1 , u 2 , . . . , u p ) be a v 1 -v 2 path in G [k] such that u 1 = v 1 and u p = v 2 . For 1 ≤ i ≤ p -1, let P (u i , u i+1 ) denote a shortest u i -u i+1 path in G. Replacing every edge {u i , u i+1 } in P by the corresponding path P (u i , u i+1 ), we obtain a walk W P in G. Clearly,

W P contains a v 1 -v 2 path in G, and hence, N G (v 3 ) ∩ V (W P ) = ∅. Let w ∈ N G (v 3 ) ∩ V (W P ). Assume, without loss of generality, w ∈ V (P (u i , u i+1 )) for some i, 1 ≤ i ≤ p -1. Since {u i , u i+1 } ∈ E(G [k] ), dist G (u i , u i+1 ) is odd and at most k. If w ∈ {u i , u i+1 }, then N G [k] (v 3 ) ∩ V (P ) = ∅. Thus, we assume w / ∈ {u i , u i+1 }. Since P (u i , u i+1 ) is a shortest u i -u i+1 path in G and w ∈ V (P (u i , u i+1 )), we have dist G (u i , w) + dist G (w, u i+1 ) = dist G (u i , u i+1 ). Thus, dist G (u i , u i+1 ) ≤ k and w / ∈ {u i , u i+1 } together imply dist G (u i , w) < k and dist G (w, u i+1 ) < k. Hence, dist G (v 3 , u i ) ≤ k and dist G (v 3 , u i+1 ) ≤ k. Since dist G (u i , u i+1 ) is odd, one of dist G (u i , w) and dist G (w, u i+1 ) is also odd.
Without loss of generality, we assume dist G (u i , w) is odd, and dist G (w, u i+1 ) is even. Then, G has a v 3 -u i+1 path with length dist G (w, u i+1 ) + 1, which is odd and at most k. Since G is bipartite, G cannot have any v 3 -u i+1 path of even length. Hence dist G (v 3 , u i+1 ) is odd and at most k. This implies that

u i+1 ∈ N G [k] (v 3 ) and therefore, N G [k] (v 3 ) ∩ P = ∅. 2
4 Recognizing bipartite powers of bigraphs is hard

Powers of graphs are studied also in computational complexity aspects. [START_REF] Motwani | Computing roots of graphs is hard[END_REF] first showed that given a graph G, it is NP-complete to decide whether there exists a graph H such that H 2 = G. Following their result, several related results have been obtained [START_REF] Chang | Linear-time algorithms for tree root problems[END_REF]; [START_REF] Farzad | Computing graph roots without short cycles[END_REF]; [START_REF] Kearney | Tree powers[END_REF]; [START_REF] Lau | Bipartite roots of graphs[END_REF]; [START_REF] Lau | Recognizing powers of proper interval, split, and chordal graphs[END_REF]; [START_REF] Le | Hardness results and efficient algorithms for graph powers[END_REF]; [START_REF] Lin | Algorithms for square roots of graphs[END_REF]). Recently, [START_REF] Le | Hardness results and efficient algorithms for graph powers[END_REF] have shown the following hardness result.

Theorem 4.1 [START_REF] Le | Hardness results and efficient algorithms for graph powers[END_REF]) For any fixed k ≥ 2 and given a graph G, it is NP-complete to determine whether there exists a graph H such that H k = G.

In this section, we prove that the problem of recognizing bipartite powers is also hard.

Theorem 4.2 For any fixed odd k ≥ 3 and given a bipartite graph G, it is NP-complete to determine whether there exists a bipartite graph H such that

H [k] = G.
The problem is clearly in NP. Thus, it is sufficient to show that the problem is NP-hard. We reduce SET SPLITTING, a well-known NP-complete problem, to ours.

Problem: SET SPLITTING (Garey and Johnson, 1979, SP4) Instance: Collection C of non-empty subsets of a finite set S.

Question: Is there a partition of S into two subsets S 1 and S 2 such that no subset in C is entirely contained in either S 1 or S 2 ?

Without loss of generality, we assume that every element of S belongs to at least one set in C.

An auxiliary lemma

Before presenting the reduction, we show a useful lemma. In their proof of NP-hardness, Le and Nguyen (2010) used the following tail structure presented first by [START_REF] Motwani | Computing roots of graphs is hard[END_REF] and generalized later by [START_REF] Lau | Bipartite roots of graphs[END_REF]. Note that for two sets A and B, we mean by A ⊂ B that A ⊆ B and A = B; that is, A is properly included in B.

Lemma 4.3 [START_REF] Lau | Bipartite roots of graphs[END_REF]) Let G be a connected graph with {v 1 , . . . , v k+1 } ⊂ V (G) where N G (v 1 ) = {v 2 , . . . , v k+1 }, and

N G (v i ) ⊂ N G [v i+1 ] for all 1 ≤ i ≤ k. If H k = G for some graph H, then 1. N H (v 1 ) = {v 2 }, N H (v i ) = {v i-1 , v i+1 } for all 2 ≤ i ≤ k, and 2. N H (v k+1 ) \ {v k } = N G (v 2 ) \ {v 1 , v 2 , . . . , v k+1 }.
The tail structure played an important role in the proofs of NP-hardness of recognizing powers of graphs [START_REF] Lau | Bipartite roots of graphs[END_REF]; [START_REF] Le | Hardness results and efficient algorithms for graph powers[END_REF]; [START_REF] Motwani | Computing roots of graphs is hard[END_REF]). Although we cannot use the structure directly, we show the following similar structure for bipartite powers.

Lemma 4.4 Let k ≥ 3 be odd, and G be a connected bipartite graph with {v 0 , . .

. , v k+1 } ⊂ V (G) where N G (v 0 ) = {v 1 , v 3 , . . . , v k-2 , v k }, N G (v 1 ) = {v 0 , v 2 , . . . , v k-1 , v k+1 }, and N G (v i ) ⊂ N G (v i+2 ) for 0 ≤ i ≤ k -1. If H [k] = G for some bipartite graph H, then 1. N H (v 0 ) = {v 1 }, N H (v i ) = {v i-1 , v i+1 } for 1 ≤ i ≤ k, and 2. N H (v k+1 ) \ {v k } = N G (v 2 ) \ {v 0 , v 1 , . . . , v k+1 }.
To prove Lemma 4.4, we need some definitions.

A vertex u ∈ U in a bipartite graph G = (U, V ; E) is bipartite universal if N G (u) = V . We denote by N d H (v) the set of vertices in H such that the distance from v is exactly d; that is, N d H (v) = {u ∈ V (H) | dist H (u, v) = d}.
Proof (Lemma 4.4): First, observe that the vertices v 0 and v 1 are not bipartite universal in G.

Since v 0 is not bipartite universal in G = H [k] and G is connected, there is a vertex u ∈ V (H) such that dist H (v 0 , u) is finite and greater than k. This implies that N 2i+1 Next we apply a similar argument to v 1 . Since v 1 is not bipartite universal in G, N 2i+1 H (v 1 ) = ∅ for all 0 ≤ i ≤ (k -1)/2. Since N H (v 0 ) = {v 1 } and |N G (v 1 )| = |{v 0 , v 2 , . . . , v k-1 , v k+1 }| = (k + 1)/2 + 1, it follows |N H (v 1 )| = 2 and |N 2i+1 H (v 1 )| = 1 for all 1 ≤ i ≤ (k -1)/2. By the assumption N G (v i ) ⊂ N G (v i+2 ), we have N H (v 1 ) = {v 0 , v 2 } and N 2i+1 H (v 1 ) = {v 2i+2 } for 1 ≤ i ≤ (k -1)/2 (see Fig. 3). Thus the first property holds. The second property immediately follows from the first one. 2

H (v 0 ) = ∅ for all 0 ≤ i ≤ (k -1)/2. Moreover, since |N G (v 0 )| = |{v 1 , v 3 , . . . , v k-2 , v k }| = (k + 1)/2, it follows |N 2i+1 H (v 0 )| = 1 for all 0 ≤ i ≤ (k -1)/2. Then, the assumption N G (v i ) ⊂ N G (v i+2 ) implies that N 2i+1 H (v 0 ) = {v 2i+1 } for all 0 ≤ i ≤ (k -1)/2 (see Fig. 2). ... v k-2 v 5 v 3 v 1 v k N 2 H (v 0 ) N 4 H (v 0 ) N k-1 H (v 0 ) N k+1 H (v 0 ) v 0
...

v k-2 v 5 v 3 v 1 v k v 0 v k+1 v k-1 v 4 v 2

Reduction

Let (S, C) be an instance of SET SPLITTING, where S = {u 1 , . . . , u n } is the ground set, and C = {c 1 , . . . , c m } is a set of non-empty subsets of S. For any fixed odd k ≥ 3, we construct a graph G from (S, C). The vertex set V (G) of G consists of the following vertices:

• Element vertices u i for all element u i ∈ S;

• Subset vertices c 0 j , . . . , c k+1 j for all c j ∈ C; and

• Partition vertices S 0 1 , . . . , S k-2 1 and S 0 2 , . . . , S k-2 2 .

Fig. 2 :

 2 Fig. 2: Partial tail structure of vertices.

Fig. 3 :

 3 Fig. 3: Tail structure of vertices.

The edge set E(G) of G consists of the following edges: For each subset c j ∈ C,

• c p j is adjacent to c q j if p ≡ q (mod 2), • c p j is adjacent to c q j if p + q ≤ k -4 and p ≡ q (mod 2);

• c p j is adjacent to c q j if c j ∩ c j = ∅ and p + q = k -2,

• c p j is adjacent to all u i ∈ S if p is even and 0 ≤ p ≤ k -3,

• c p j is adjacent to S q 1 and S q 2 if p + q ≤ k -2 and p ≡ q (mod 2),

For each element u i ∈ S,

For each i ∈ {1, 2},

• S p i is adjacent to S q i if p ≡ q (mod 2), • S p 1 and S q 2 are adjacent if p + q ≤ k -4 and p ≡ q (mod 2).

Equivalence

Now we prove that (S, C) has a desired partition if and only if there exists a bipartite graph H such that

Lemma 4.5 If there exists a partition of S into two disjoint subsets S 1 and S 2 such that each subset in C intersects both S 1 and S 2 , then there exists a bipartite graph H such that G = H [k] .

We define E(H) as follows (see Fig. 4).

• For each c j ∈ C, {c i j , c i+1 j } ∈ E(H) for 0 ≤ i ≤ k, and {c 0 j , u i } ∈ E(H) for each u i ∈ c j .

• For each

It is a routine exercise to verify that G = H [k] . 2

Lemma 4.6 If there is a bigraph H such that H [k] = G, then there exists a partition of S into two disjoint subsets S 1 and S 2 such that each subset in C intersects both S 1 and S 2 .

To this end, we show that 1. for any c j ∈ C and ∈ {1, 2}, some u i ∈ c j has S 0 as a neighbor in H, and 2. no u i ∈ S has both S 0 1 and S 0 2 as neighbors in H.

They will conclude the proof. Let

∈ {c 0 j , . . . , c k+1 j }, every c p j -v path in H has c q j as an internal node if p > q. Hence, dist H (c p j , v) = pq + dist H (c q j , v). Note that this also holds when p ≤ q. Claim 4.7 For ∈ {1, 2} and a, b ≥ 0, dist H (c a j , S b ) = a + b + 2.

Proof (Claim 4.7): First, we show that dist

Thus, the claim holds. 2

Let ∈ {1, 2}. From Claim 4.7, we have dist

some u i ∈ c j must be adjacent to S 0 in H. Thus, we have the first property. To show the second property, we use the following fact.

Proof (Claim 4.8): By Claim 4.7, any shortest c 0 j -S k-2 2 path in H is of length k. Let P = (p 0 , p 1 , . . . , p k ) be such a path, where p 0 = c 0 j and p k = S k-2

2

. It is easy to see that p 1 = u i for some u i ∈ c j . Also, it is not difficult to see that either p 2 = c 0 j for some c j ∈ C, or p 2 = S x for some x ∈ {0, . . . , k -2} and ∈ {1, 2}. If p 2 = c 0 j , then dist H (c 0 j , S k-2

2 ) = k -2. This contradicts Claim 4.7. Hence, we have p 2 = S x . Since (c 0 j , u i , S x ) is a shortest path in H, dist H (c 0 j , S x ) = 2. Thus we have x = 0 from Claim 4.7. If k] ). Hence, we can conclude that p 2 = S 0 2 , and thus

Now we prove the second property. Suppose some u i ∈ c j has both S 0 1 and S 0 2 as neighbors in H. Then, dist H (S 0 1 , S 0 2 ) = 2. Since dist H (S 0 2 , S k-2

2 ) = k -2 by Claim 4.8,

Since there is a S 0 1 -S k-2 2 path of odd length in G and because G is bipartite, dist H (S 0 1 , S k-2

2

) is odd. Hence, {S 0 1 , S k-2

2

} ∈ E(H [k] ). This contradicts {S 0 1 , S k-2 k] ). 2