Keywords: graph theory, labeled graph, vertex-distinguishing edge coloring, labeled packing of graphs, XML tree pattern matching

Chapter 1. Introduction

Recently, graph theoretical concepts were widely used to study and model various computer applications such as image segmentation, information retrieval, networking, clustering, etc. For example in XML information retrieval, XML document and query data can be represented by a graph model, and hence, retrieving XML documents can be considered as a graph matching problem between the query tree and the document trees (i.e., document/query isomorphism).

The three major problems considered in this thesis are the graph coloring problem, the graph packing problem and the tree pattern matching. The common point between these three problems is that they deal with labeled graphs. We thus divided the thesis into three main parts, each containing two chapters, numbered from 3 to 8, where Chapter two is devoted to some basic graph theory concepts and preliminary definitions, that are needed for the understanding of the results exposed in this document.

Chapter 1

Introduction

Graph theory is an important field of mathematics and computer science. Originally, it started in 1735 with the problem of the Seven Bridges of Königsberg. The city of Königsberg in Prussia (modern Kaliningrad, Russia) was set on both sides of the Pregel River, and included two islands connected to each other and the mainland by seven bridges. The problem was to find a continuous tour through the city that would cross each bridge exactly once, ending up at the point from which it began. The Swiss mathematician, Leonard Euler, demonstrated that no such tour was possible. This result is often referred to as the first theorem in graph theory [START_REF] Euler | Solutio problematis ad geometriam situs pertinentis[END_REF]. Graphs are useful mathematical tools for modeling the relationships among objects, which are represented by vertices. In their turn, relationships between vertices are represented by edges. In this context, graph theory received considerable attention, not only from the mathematical community, but also from the whole scientific community. Over the years, there have been a large number of significant and authoritative publications in biochemistry, computer science, genetics or in sociology where there is an interesting connection with graph theory. These problems are most often modeled by finding an optimal structure in a graph, generally a structure that must satisfy some constraints. For example, some problems can be modeled by finding a maximum matching (i.e., a largest set of edges without common vertices), a maximum stable set (i.e., a largest set of vertices such that no two of them are linked by an edge), or a minimum coloring (i.e., a minimum-cardinality partition of the vertices of a graph into stable sets). Some problems can be solved efficiently, i.e., with a polynomial-time algorithm (an algorithm is polynomial if its running time is bounded by a polynomial function according to the number and size of the inputs). For example, the problem of computing a maximum matching can be solved using very efficient polynomial-time algorithms. Unfortunately, many graph problems are hard in the sense that there is (probably) no polynomial algorithm which solves these problems. More formally, these problems are proved to be NP-hard (this is the case for minimum coloring and maximum stable set problem). Another class of problems concerns those that have not been classified yet as either polynomial or NP-hard. Isomorphism between two graphs is one of the very few natural problems in this class. We say that two graphs are isomorphic if there exists a permutation of the vertices that makes both graphs identical.

Part 1: Graph coloring problem

Born with the famous Four Color Problem in 1852, the field of graph coloring has become one of the most popular areas of graph theory. Graph coloring problems come in many varieties but in general they consist in partitioning the objects (vertices, edges, faces, etc.) of a graph into different classes so that given constraints are satisfied. In its basic form, graph coloring is a way of coloring the vertices of a given graph such that adjacent vertices get different colors; this is called the proper vertex coloring problem. Similarly, a proper edge coloring problem assigns a color to each edge so that every two adjacent edges receive different colors. About forty years ago, many researchers considered the problem of assigning colors to the edges of a graph G such that any two vertices of G are uniquely identified either by sets, multisets or sums of their incident colors. The literature about these variants is reviewed in Chapter three. Chapter four is intended to define a new graph coloring parameter called the gap vertex distinguishing edge coloring number, that combines many features of the previously introduced methods. It consists in an edge-coloring of a graph G which induces a vertex distinguishing labeling of G such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. In particular, we will study this problem for various families of graphs and we will also show how this new parameter is strongly correlated to the vertex distinguishing problem by sets and multisets. As a consequence, we will provide bounds on these two problems.

Part 2: Graph packing problem

Graphs G 1 , G 2 , . . . , G k (on n vertices each) pack, if there exists an edge disjoint placement of them into the complete graph K n . This problem is a classical one in graph theory and has been extensively studied since the early 70's. However, the majority of existing works focuses on unlabeled graphs. In Chapter five, we introduce for the first time the packing problem for a vertex labeled graph. Roughly speaking, it consists in a classical graph packing which preserves the labels of the vertices. Then, we study the corresponding optimization parameter for k copies of cycles. In Chapter six, we study the labeled packing of two copies of trees and of all graphs of order n and size n -2. As an application, we will show that this new problem can be used to solve the matching problem between two labeled graphs.

Part 3: XML Tree Pattern Matching Problem

With the increasing number of available XML documents, numerous approaches for retrieval have been proposed in the literature. They usually use the tree representation of documents and queries to process them in an implicit or explicit way. Although retrieving XML documents can be considered as a tree matching problem between the query tree and the document trees, we consider in this part the matching problem from an exact point of view. In Chapter seven, we outline and compare the various features of different tree pattern algorithms. Most of these algorithms find twig pattern matching in two steps. In the first one, a query tree is decomposed into a set of binary patterns or single paths and then search for matches for these individual patterns/paths. Finally, these matches are stitched together to form the answers to the twig query. In Chapter eight, we propose a novel holistic twig join algorithm, called TwigStack++, which features two main improvements in the decomposition and matching phase. The proposed solutions are shown to be efficient and scalable, and should be helpful for the future research on efficient query processing in a large XML database.

Finally, in chapter nine, we summarize the results presented in this thesis, and we give some remarks and directions for further research.

List of publications arising from this thesis

International journals 1. M. A. Tahraoui and H. Kheddouci We assume the reader is familiar with basic concepts of graph theory and theoretical computer science. We will thus give a short overview of the terminology used in this thesis. More background information can be found in [START_REF] Chartrand | Introduction to graph theory[END_REF], [START_REF] Harary | Graph Theory[END_REF] and [START_REF] West | An Introduction to Graph Theory[END_REF].

Basic notations

Graph: a graph G = (V (G), E(G)) consists of two finite sets: V (G), the vertex set of G, which is a non-empty set of elements called vertices and E(G) ⊆ V (G) × V (G) is called set of edges. The cardinality of the vertex set V (G) is called the order of G, commonly denoted by |V (G)|. The cardinality of the edge set E(G) is the size of G, denoted by |E(G)|. A graph of order n and size m is often called an (n, m)-graph. Two distinct vertices u and v are adjacent (or neighbors) if there exists an edge uv that connects them. An edge uv is said to be incident to the vertices u and v. Two edges are adjacent if they are incident to a same vertex. A graph is simple if there is at most one edge between every two vertices. In this document, unless it is specified, the graphs which are considered will be finite simple graphs.

Degree and Neighborhood: the set of all neighbors of a vertex v in a graph G is denoted by N (v). The number of neighbors of v is called the degree of v in G, denoted by d(v). If d(v) = 0, it means that v is not adjacent to any other vertex, then v is called an isolated vertex. A vertex of degree one is called an endpoint or a pendant vertex or a leaf. The minimum degree of a graph G is δ(G) = min{d(v) : v ∈ V (G)} and the maximum degree of a graph G is denoted by △(G) = max{d(v) : v ∈ V (G)}.

Independent sets and Cliques: an independent set of G is a subset of vertices U ⊆ V , such that no two vertices in U are adjacent. An independent set is said to be maximal if no independent set properly contains it. An independent set of maximum cardinality is called a maximum independent set. A clique in a graph G Chapter 2. Preliminaries is a subset C of V (G) such that every two vertices in C are adjacent in G. The clique number ω(G) is the order of a maximum clique of G.

Distance and Connectivity: a path in an undirected graph G is a sequence of vertices (v 1 , v 2 , . . . , v k ) such that each pair v i , v i+1 is an edge in E(G). A path is called simple if all its vertices are distinct. A graph G is connected if there exists a path between any two distinct vertices of G. Otherwise, the graph G is disconnected. The distance between two vertices u, v in G, denoted by dist(u, v), is the minimum number of edges in a path connecting them. The diameter of G is the maximum distance between any two vertices of G. A graph is k-edge-connected if there are k edge-disjoint paths between each pair of vertices or, equivalently, no two vertices can be separated by removing less than k edges.

Isomorphism of graphs: two graphs G and H are said to be isomorphic (written G ∼ = H) if there is a one-to-one correspondence between their vertex-sets which preserves the adjacency of vertices. We provide an example in Figure 2.1. Subgraphs: a graph H is a subgraph of G, written H ⊆ G, if every vertex of H is a vertex of G and every edge of H is an edge of G. In other words, V (H) ⊆ V (G) and E(H) ⊆ E(G). We say that a subgraph H is a spanning subgraph, or a factor, of G if H contains all the vertices of G. Given V ′ ⊆ V , the subgraph G[V ′ ] = (V ′ , E ′ ) denotes the subgraph of G induced by V ′ , i.e., E ′ contains all the edges of E which have both endpoints in V ′ .

Some graph operations

In the following definitions, we detail some well known graph operations.

Complement graph: if G is a simple graph with vertex set V (G), its complement G is the simple graph with vertex set V (G) in which two vertices are adjacent if and only if they are not adjacent in G. Figure 2.2 shows a graph and its complement. Power of graph: the k-th power G k of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. The second power of a graph is also called its square.

Vertex removal: if v is a vertex of the graph G = (V, E), then Gv is the subgraph of G induced by the vertex set V \ {v}.

Edge removal: similarly to the previous operation, if e is an edge of the graph G = (V, E), then Ge is the graph (V, E ′ ), where E ′ is obtained by removing e from E. Note that the endpoints of e are not removed from G.

Graph union: the union G = G 1 ∪G 2 of graphs G 1 and G 2 with disjoint vertex sets V 1 and V 2 and edge sets E 1 and E 2 is the graph with

V = V 1 ∪ V 2 and E = E 1 ∪ E 2 .
This operation is sometimes also known explicitly as the graph disjoint union.

Cartesian product of graphs: the Cartesian product of two graphs G 1 and G 2 , denoted by G 1 G 2 , is the simple graph with V (G 1 ) × V (G 2 ) as its vertex set and two vertices (u 1 , v 1 ) and (u 2 , v 2 ) are adjacent in G 1 G 2 if and only if either u 1 = u 2 and v 1 , v 2 are adjacent in G 2 , or u 1 , u 2 are adjacent in G 1 and v 1 = v 2 .

Some families of graphs

We review in this section several classes of graphs that will be considered in this document.

Path graph: a graph G is called path, denoted by P n , if it is of the form: V (P ) = {v 0 , v 1 , . . . , v n }, E(P ) = {v 0 v 1 , v 1 v 2 , . . . v n-1 v n } (see Figure 2.3(a)).

Cycle graph: a graph G is called cycle, denoted by C n , if it is of the form: Complete graph: a complete graph is a graph in which every two distinct vertices are joined by exactly one edge. The complete graph with n vertices is denoted by K n . In Figure 2.4, we give five examples of complete graphs. Planar graph: a graph is planar if it can be drawn in a plane without edge crossing (i.e., edges intersect only at their common vertices). For example, the complete graph K 4 is a planar graph.

V (P ) = {v 0 , v 1 , . . . , v n }, E(P ) = {v 0 v 1 , v 1 v 2 , . . . v n-1 v n , v n v 1 } (see Figure 2.3(b)). v 1 v 2 v 3 v n-1 v n (a) v 2 v 3 v n-1 v n v 1 v i v i+1 (b)
Tree: a tree is a connected graph which has no cycle. An example of tree is given in Figure 2.5. A tree is called a rooted tree if one of its nodes is distinguished as the root, in which case the edges have a natural orientation, towards or away from the root. A vertex v in a rooted tree is a descendant of a vertex u if u lies on the unique path from the root to v. The parent of a vertex v is the last vertex before v in a path from the root to v. The depth of a vertex v in a rooted tree is the length of the path from the root to v. Thus, the depth of the root is 0.

Star graph: the star graph S n , is a tree with n vertices such that one vertex (called the center) has degree n -1 and the other n -1 vertices have degree 1 (see Figure 2.6(a)).

Caterpillar: a caterpillar is a tree which becomes a path when all its endpoints are removed, as shown in Figure 2.6(b). Bipartite graph: a bipartite graph G = (V, E) is a graph whose vertex set V can be divided into two disjoint subsets U and W , such that each edge of G has one endpoint in U and one endpoint in W , as shown in Figure 2.7. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycle. The complete bipartite graph on n and m vertices, denoted by K n,m is the bipartite graph G = (U, W, E), where U and W are disjoint sets of size n and m, respectively, and E connects every vertex in V with every vertice in U . It follows that K n,m has nm edges. There have been several studies using a variety of methods for the purpose of uniquely identifying (or distinguishing) the vertices of a graph. Many of these methods involve graph labelings or graph colorings. In several variants, certain edge colorings have given rise to vertex-distinguishing labelings. These are often referred to as vertex-distinguishing edge colorings, which is the subject of this chapter.

Introduction to graph coloring

Graph coloring is one of the oldest areas in graph theory. It is widely believed that the graph coloring problem was born in 1852 when Guthrie asked whether it was possible to color the countries of any geographical map with four or fewer colors, so that every two countries sharing a common boundary are colored differently. This is the famous Four Color Problem. The first proof of this problem was given by Kempe in 1879 and accepted for more than ten years until Heawood in 1890 found a flaw in Kempe's reasoning using a map with 18 countries. By a revision of Kempe's proof, Heawood was able to show that five colors are always sufficient. Graph coloring has become a subject of great interest for researchers, mainly because of its diverse theoretical results and unsolved problems. Furthermore, graph colorings have been proved to be paramount in other domains of graph theory (for instance in the study of connectivity, matchings, Hamilton cycles) and also in real world applications in many engineering fields, including register allocation [START_REF] Chow | The priority-based coloring approach to register allocation[END_REF], timetabling [START_REF] De Werra | An introduction to timetabling[END_REF], frequency assignment [START_REF] Gamst | Some lower bounds for a class of frequency assignment problems[END_REF], scheduling [START_REF] Leighton | A graph coloring algorithm for large sceduling problems[END_REF] and communication networks [START_REF] Woo | Resource allocation in a dynamically partitionable bus network using a graph coloring algorithm[END_REF].

Vertex coloring problem

Graph coloring problems that received the most attention deal with the vertices of a graph. A proper vertex coloring of a graph G is a mapping f :

V (G) -→ N (where N is the set of positive integers) such that f (u) = f (v) if u and v are adjacent in G.
If f (V ) has size at most k, then we refer to the coloring as a k-coloring. A subset of vertices assigned with the same color is called a color class, every such class being an independent set. Thus, a k-coloring is equivalent to a partition of V (G) into k independent sets, and the terms k-partite and k-colorable have the same meaning. The following figure illustrates an example of a proper vertex coloring with three colors. The chromatic number χ(G) of G is the minimum positive integer k for which G has a k-coloring. Determining the chromatic number of a general graph G is well-known to be a NP-hard problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Consequently, much work has been devoted to (1) determining bounds on the chromatic number of general graphs and (2) determining the chromatic number of some families of graphs. It is quite easy to see that for every graph G with maximum degree △(G), we have χ(G) ≤ △(G) + 1. However, Brooks has improved this bound as follows [START_REF] Brooks | On colouring the nodes of a network[END_REF].

Theorem 3.1 ([Bro41]) Let G be a connected graph. Then χ(G) ≤ △(G) unless G is a complete graph or an odd cycle.
A rather obvious, but often useful, lower bound for the chromatic number of a graph involves the chromatic numbers of its subgraphs.

Theorem 3.2 If H is a subgraph of a graph G, then χ(H) ≤ χ(G).
The following result is an immediate consequence of the previous theorem.

Corollary 3.3 For every graph G, χ(G) ≥ ω(G). A graph G is perfect if every induced subgraph H of G satisfies χ(H) = ω(H).
In the early 1960's, Berge observed [START_REF] Berge | Les problèmes de coloration en théorie des graphes[END_REF][START_REF] Berge | Färbung von graphen, deren sämtliche bzw, deren ungerade kreise starr sind[END_REF] that several classical families of graphs (e.g. bipartite graphs, trees, interval graphs, chordal graphs) are perfect. In [L 72], the author showed that a complement of a perfect graph is also perfect. However, there are also many graphs whose chromatic number exceeds their clique number such as the Petersen graph and the odd cycles of length 5 or more. In [START_REF] Grötschel | Polynomial algorithms for perfect graphs[END_REF], Grötschel et al. showed that the chromatic number of a perfect graph can be determined in polynomial time. This is important as perfect graphs have many connections to other combinatorial problems.

In addition to vertex coloring problems, many other types of graph coloring problems have been formulated in the literature. However, the significance of vertex coloring problems is often emphasized since many of these new problems can be reformulated in terms of vertex colorings, or strongly depend on the chromatic number. For more details on those variants, we refer the reader to the book of de Werra and Hertz [START_REF] De Werra | Graph Colouring and Variations[END_REF].

Edge coloring problem

After vertex colorings, it makes sense to study edge colorings. In this problem we are looking for the minimum number of colors necessary to be assigned to the edges of a graph such that any two incident edges are colored with different colors. This parameter is called the chromatic index and is denoted by χ ′ (G). In 1965, Vizing [START_REF] Vizing | Critical graphs with given chromatic class. Metody Diskret[END_REF] proved the famous Vizing's theorem.

Theorem 3.4 ([Viz64]) For every nonempty graph G, △(G) ≤ χ ′ (G) ≤ △(G) + 1
In [START_REF] Holyer | The np-completeness of edge-colouring[END_REF], Holyer proved that it is NP-complete to decide whether χ ′ (G) = △(G) or χ ′ (G) = △(G) + 1. The chromatic index has been determined for several classes of graphs. Indeed, bipartite graphs satisfy χ ′ (G) = △(G), while for odd cycles, we have χ ′ (G) = △(G) + 1. For planar graphs, Vizing proposed the following conjecture:

Conjecture 3.5 ([Viz65]) For every planar graph G with maximum degree △(G) = 6 or 7, we have χ ′ (G) = △(G)
This conjecture has been confirmed in [START_REF] Sanders | Planar graphs of maximum degree seven are class 1[END_REF][START_REF] Zhang | Every planar graph with maximum degree 7 is class 1[END_REF] for △(G) = 7. But the case △(G) = 6 remains an open problem.

Various generalizations of edge-coloring have been introduced and investigated in the literature. In the 1970's, Hilton and de Werra obtained many results on equitable and edge-balanced colorings in which each color appears uniformly in G [HW82, [START_REF] De Werra | Some results in chromatic scheduling[END_REF][START_REF] De Werra | A few remarks on chromatic scheduling, in combinatorial programming[END_REF]. In the 1980's Hakimi and Kariv [START_REF] Hakimi | On a generalization of edge-coloring in graphs[END_REF] proposed the following f -coloring problem: let f be a function which assigns a positive integer f (v) to each vertex v ∈ V (G), an f -coloring of a graph G is a proper edge coloring of G such that for each vertex v ∈ V , at most f (v) edges incident to v are colored with the same color. The minimum number of colors needed to f -color G is called the f -chromatic index χ ′ f (G) of G. Since the proper edge-coloring problem is NPcomplete, the f -coloring problem is also NP-complete in general. Various upper bounds on χ ′ f (G) have been provided in [START_REF] Hakimi | On a generalization of edge-coloring in graphs[END_REF][START_REF] Nakano | On the f -coloring of multigraphs[END_REF][START_REF] Seymour | Colouring series-parallel graphs[END_REF].

Total coloring problem

We now consider colorings that assign colors to both vertices and edges of a graph.

A total coloring of a graph G is an assignment of colors to the vertices and edges of G such that distinct colors are assigned to (i) every two adjacent vertices, (ii) every two adjacent edges, and (iii) every incident vertex and edge. The total chromatic number χ ′′ (G) of a graph G is the least number of colors needed in any total coloring of G. Immediately, we have that χ ′′ (G) ≥ △(G) + 1. Sánchez-Arroyo [START_REF] Sánchez-Arroyo | Determining the total coloring number is np-hard[END_REF] shown that deciding whether a given graph has χ ′′ (G) = △(G) + 2 is an NP-complete problem. The total coloring conjecture proposed independently by Behzad [START_REF] Behzad | Graphs and their chromatic numbers[END_REF] and Vizing [START_REF] Vizing | Critical graphs with given chromatic class. Metody Diskret[END_REF] claims that for every simple graph G, χ ′′ (G) ≤ △(G) + 2. This conjecture has been verified for a few important classes of graphs such as all bipartite graphs and most planar graphs except those with maximum degree 6.

Vertex-distinguishing edge coloring

A problem in graph theory that has received considerable attention in the literature concerns methods to uniquely identify the vertices of a connected graph. One of the most popular methods is due to Entringer and Gassman [START_REF] Entringer | Line-critical point determining and point distinguishing graphs[END_REF] and Sumner [START_REF] Sumner | Point determination in graphs[END_REF]. They characterized the graphs G such that every two non-adjacent vertices of G have distinct open neighborhoods. Harary and Melter [START_REF] Harary | On the metric dimension of a graph[END_REF] introduced the idea of selecting a subset A = {u 1 , u 2 , . . . , u k } and labeling each vertex of v of G with the ordered k-tuple l

(v) = (d 1 , d 2 , . . . , d k ) called distance label of v, where d i = dist(v, u i ) for 1 ≤ i ≤ k.
In this case, the vertices of G are distinguishable if distinct vertices of G have distinct distance labels. The symmetry breaking method was introduced by Harary [Har96, Har01] and, independently, by Albertson and Collins [START_REF] Albertson | Symmetry breaking in graphs[END_REF]. In this method, the distinction of the vertices of G is realized with the aid of a certain automorphism of G.

In this thesis, we are interested in another distinguishing method that is related to the graph coloring problem. Indeed, many researchers investigated the question of finding an edge coloring inducing a vertex distinguishing labeling. This is often referred to as vertex-distinguishing edge coloring. This problem has received increasing attention in the literature during the past forty years. To the best of our knowledge, four main different functions have been proposed to label each vertex v of G according to the colors of its incident edges. A vertex labeling l induced by an edge-coloring f is said to be:

1. vertex-labeling by sum if l(v) = v∋e f (e), ∀v ∈ V (see [CJL + 88, BKT05]).
2. vertex-labeling by sets if l(v) = v∋e f (e), ∀v ∈ V (see [START_REF] Burris | Vertex-distinguishing proper edge colorings[END_REF][START_REF] Cerny | Observability of a graph[END_REF][START_REF] Harary | The point-distinguishing chromatic index[END_REF]).

3. vertex-labeling by multiset if l(v) = v∋e f (e), ∀v ∈ V (see [START_REF] Aigner | Irregular assignments and vertexdistinguishing edge colorings of graphs[END_REF][START_REF] Burris | The irregular coloring number of a tree[END_REF][START_REF] Chartrand | Detectable colorings of graphs[END_REF]).

4. vertex-labeling by product if l(v) = v∋e f (e), ∀v ∈ V (see [START_REF] Kaziów | Multiplicative vertex-colouring weightings of graphs[END_REF]).

The problem of vertex-distinguishing edge colorings offers many variants and received a great interest during these last years. We refer the interested reader to Chapter 13 of Chartrand and Zhang's book [START_REF] Chartrand | Chromatic Graph Theory[END_REF]. In the next section, we give some results and open questions about this area of research.

Variations of the problem

Over the years, several vertex distinguishing edge coloring problems have been defined. In many variants, some authors used the same terminology to describe different concepts. In Table 3.1, we describe a summary of these variants depending on whether:

1. the edge coloring is proper or not, 2. the vertex labeling is induced by sum; product; set or multiset (if the edgecoloring is not proper), 3. the edge coloring must distinguish all vertices (global) or only adjacent vertices (local).

Hence, we potentially obtain fourteen variants of vertex distinguishing edge colorings, among which ten were studied in the literature (to the best of our knowledge). Each row of Table 3.1 presents a vertex-distinguishing variant, for example, the first row means that Burris and Schelp [BS97] defined a strong edge coloring of G as a proper edge coloring that induces a vertex-distinguishing labeling by sum. In Figure 3.2, we provide a coloring scheme of C 7 for each variant appearing in Table 3.1. Since the literature on these topics is very rich, we are not able to give an exhaustive list of all the relevant references. In what follows, we only mention three variants of vertex distinguishing colorings that will have a strong relation with our coloring parameter introduced in the next chapter. [START_REF] Cerny | Observability of a graph[END_REF]. In their original article on this topic, Burris and Schelp [START_REF] Burris | Vertex-distinguishing proper edge colorings[END_REF] gave values of χ ′ s for some families of graphs such as complete graphs, bipartite complete graphs, paths and cycles. Let n d (G) be the number of vertices of degree d in G, it is clear that

Strong edge coloring

χ ′ s (G) d ≥ n d for all d with δ(G) ≤ d ≤ △(G).
In [START_REF] Burris | Vertex-distinguishing proper edge colorings[END_REF], Burris and Schelp posed the following conjecture.

Conjecture 3.6 ([BS97]

) Let G be a graph with no isolated vertices or edges and let k be the minimum integer such that k

d ≥ n d for all d with δ(G) ≤ d ≤ △(G). Then χ ′ s (G) = k or k + 1.
This conjecture remains open in general and has only been determined for some classes of regular graphs [START_REF] Rudasov | Vertex-distinguishing proper edge colourings of some regular graphs[END_REF] and graphs with small components [START_REF] Balister | Vertex distinguishing colorings of graphs with △(g) = 2[END_REF].

The following result has been conjectured by Burris and Schelp [START_REF] Burris | Vertex-distinguishing proper edge colorings[END_REF] and proved in [START_REF] Bazgan | On the vertexdistinguishing proper edge-colorings of graphs[END_REF].

Theorem 3.7 ([BBLW99]

) A graph G with n vertices, without isolated edges and with at most one isolated vertex satisfies χ ′ s (G) ≤ n + 1.

This upper bound is the best possible since it is achieved for the complete graph K n where n is even. For some families of graphs, the parameter χ ′ s (G) is close to the maximum degree than to the order of the graph as shown by the following theorem. (a)

1 3 1 2 3 2 4 {2} {1,2} {1} {1,3} {3} {3,4} {2,4} (b) 1 1 2 2 3 3 4 {2,3} {1,3} {1,2} {2,3} {1,3} {1,4} {2,4} (c) 1 2 1 3 2 2 3 {2,3} {1,2} {1} {1,2} {2} {2,3} {3} (d) 1 3 1 2 3 2 4 {2,2} {1,2} {1,1} {1,3} {3,3} {3,4} {2,4} (e) 1 3 1 2 3 3 2 {2,3} {1,3} {1,1} {1,3} {3,3} {2,3} {2,2} (f)
χ ′ s (G) ≤ △(G) + 5
There have been many bounds related to some specific families of graphs. In the case of trees, Burris and Schelp have obtained the following upper bound: for any tree

T = K 2 , χ ′ s (T ) ≤ max{n 1 + 1, 6.35n 1/2 2 , 21}.
Recently, Jun-qiao and Yue-hua [START_REF] Jun-Qiao | Upper bounds on vertex distinguishing chromatic index of some halin graphs[END_REF] have found bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △(G) ≥ 4, respectively.

Detectable edge coloring

Let c(G) (called also detection number ) denote the minimum number of colors required to have an edge coloring (not necessarily proper) of G that induces a 20 Chapter 3. Vertex-Distinguishing Edge Coloring of Graphs vertex-distinguishing labeling by multisets. The following result has been stated in [START_REF] Aigner | Irregular assignments and vertexdistinguishing edge colorings of graphs[END_REF].

Theorem 3.9 ( [ATT92]) Let c be a k-coloring of the edges of a graph G. The maximum number of different labels of the vertices of degree r in G is r+k-1 r .

In other words, this means the following: Corollary 3.10 If c is a detectable k-coloring of a connected graph G of order at least 3, then G contains at most r+k-1 r vertices.

Since vertices with distinct degrees in a connected graph always have distinct labels, then, it seemed most challenging to study the graphs having many vertices of the same degree. Indeed, the parameter c(G) of complete graphs and complete bipartite graphs have been determined and detectable colorings of connected rregular graphs and trees have been studied as well (see [START_REF] Aigner | Irregular assignments and vertexdistinguishing edge colorings of graphs[END_REF], [START_REF] Burris | On graphs with irregular coloring number 2[END_REF], [START_REF] Burris | The irregular coloring number of a tree[END_REF], [START_REF] Chartrand | Detectable colorings of graphs[END_REF]).

The detection number of cycles and paths have been determined in [CEOZ06] and [START_REF] Escuadro | On detectable colorings of graphs[END_REF], respectively.

Theorem 3.11 ([CEOZ06]) Let n ≥ 3 be an integer and let l = ⌈ n 2 ⌉. Then c(C n ) = 2l -1 if 2(l -1) 2 + 1 ≤ n ≤ 2l 2 -l 2l if 2l 2 -l + 1 ≤ n ≤ 2l 2
Theorem 3.12 ([EP05]) Let n ≥ 3 be an integer and let l = ⌈ n 2 ⌉. Then

c(P n ) = 2l if 2l 2 -l + 1 ≤ n ≤ 2l 2 + 3 2l + 1 if 2l 2 + 4 ≤ n ≤ 2l 2 + 3l + 2
The following result, stated in [START_REF] Chartrand | Detectable colorings of graphs[END_REF], gives an upper bound for c(G) on a connected graph.

Theorem 3.13 ([CEOZ06]) If G is a connected graph of order n ≥ 4, then c(G) ≤ n -1.
This upper bound is obviously reached since there are many families of graphs G with the property that c(G) = n -1 such as K 1,n for n ≥ 2, K 3 , K 4 , P 3 and C 4 .

Point-distinguishing edge coloring

Let χ ′ 0 (G) denote the minimum number of colors required to have an edge coloring (not necessarily proper) of a graph G that induces a vertex distinguishing labeling by sets. Harary and Plantholt [START_REF] Harary | The point-distinguishing chromatic index[END_REF] referred to this type of coloring as the pointdistinguishing edge coloring. They proved, among other things, the exact value of

χ ′ 0 (P n ), χ ′ 0 (C n ), χ ′ 0 (Q n ) and χ ′ 0 (K n ) for n ≥ 3.
For bipartite graphs it seems that the problem of determining χ ′ 0 (K m,n ) is not easy (see [START_REF] Hornak | Localization of jumps of the pointdistinguishing chromatic index of k n,m . Discuss[END_REF][START_REF] Hornak | On the point-distinguishing chromatic index of complete bipartite graphs[END_REF][START_REF] Salvi | On the value of the point-distinguishing chromatic index of k n,n[END_REF]). Clearly we have c(G) ≤ χ ′ 0 (G) ≤ χ ′ s (G), and the following result follows from Theorem 3.7.

Theorem 3.14 A graph G with n vertices, without isolated edges and with at most one isolated vertex satisfies χ ′ 0 (G) ≤ n + 1.

During the analysis of this problem we have observed that there is no connected graph G of order n with χ ′ 0 (G) = n + 1. Thus, we propose the following conjecture.

Conjecture 3.15 For every connected graph G of order n ≥ 3,

χ ′ 0 (G) ≤ n.
If this conjecture is true, then the resulting theorem cannot be improved in general (clearly

χ ′ 0 (Q n ) = n).
In the next chapter, we will prove that Conjecture 3.15 holds for several families of graphs.

Our observations

Derived from our study of the above literature, the following three observations can be made.

1. If the problems of determining χ ′ 0 (G), χ ′ s (G) and c(G) are compared, their complexity depends on the structure of G and none of them can be stated to be more difficult than another one. For example, the exact value of χ 0 (Q n ) has been determined in [START_REF] Harary | The point-distinguishing chromatic index[END_REF], while χ ′ s (Q n ) is computed only for n ≤ 5. On the other hand, χ ′ s (K n,n ) = n + 2, while the exact value of χ 0 (K n,n ) is not easy to get. In Table 3.2, we give a summary of some important results about these three parameters.

2. The problem of vertex-distinguishing edge coloring has been the subject of a renewed interest in recent years. Perhaps the only downside of this area is the lack of applications. But do not despair, this type of coloring could be simpler and still easier to use in some areas such as the identification of nodes in networks, routing problem, etc.

3. Note that from the point of view of computational complexity, we know almost nothing about these problems (only the problem of proper coloring that distinguishes adjacent vertices by sets is known to be NP-complete, even for regular bipartite graphs).

In order to simplify the study of χ ′ 0 (G), χ ′ s (G) and c(G), we introduce the following notation: given a set S of positive integers, we denote by diam(S) the diameter of S, where diam(S) = max{xy : x, y ∈ S}. It is clear that for every two sets S 1 and S 2 , if diam(S 1 ) = diam(S 2 ), then S 1 = S 2 . Hence, we can conclude that the diameter of sets may help the vertex distinguishing property by sets or multisets. Hence, we look to extend the vertex distinguishing edge coloring problems by introducing the notion of diameter of sets, which is the subject of the next chapter.

Parameter

Exact values Upper bounds

χ ′ s (G)
paths, cycles, complete graphs, bipartite graphs, wheel graphs, chordal graphs, union of paths and union of cycles.

General graphs: χ ′ s (G) ≤ n+1, Some graph families: trees, graphs with minimum degree σ(G) > n 3 , graphs with σ ≥ 5 and △ < n(2c-1)-4

3
where c is a constant with 1 2 < c ≤ 1, cubic graphs, graphs contains both paths and cycles.

c(G)

paths, cycles, wheel graphs, complete graphs, complete bipartite graphs and union of paths General graphs: c(G) ≤ n -1, Some graph families: trees and r-regular graphs.

χ ′ 0 (G) paths, cycles, complete graphs, union of paths, bipartite graphs K m,n with m ≤ 10 or n ≥ 8m 2 -2m + 1 and wheel graphs.

General graphs: χ ′ s (G) ≤ n+1, Some graph families: bipartite graphs and complete bipartite graphs. Table 3.2: Summary of some important results about χ ′ s (G), c(G) and χ ′ 0 (G).

Conclusion

In this chapter, we have presented a short survey on vertex distinguishing edge coloring. In particular, we detailed three parameters that will be useful to study the coloring problem that will be detailed the next chapter.

Chapter 4

Gap Vertex-Distinguishing Edge Colorings of Graphs In this chapter, we define and study a new variation of the vertex-distinguishing edge coloring problem. It consists in an edge-coloring of a graph G which induces a vertex distinguishing labeling of G such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of G is called the gap chromatic number of G and is denoted by gap(G).

We study in this chapter the gap chromatic number for a large set of graphs G of order n and we even prove that gap(G) ∈ {n -1, n, n + 1}.

Definitions and preliminary results

As mentioned in the previous chapter, the problem of vertex-distinguishing edge coloring offers many variants and received a great interest during these last years. The aim of this chapter is to introduce a new variant of vertex-distinguishing edge coloring called gap vertex-distinguishing edge coloring, which is defined as follows: Definition 4.1 Let G be a graph, k be a positive integer and f be a mapping from E(G) to the set {1, 2, ..., k}. For each vertex v of G, the label of v is defined as

l(v) = f (e) e∋v if d(v) = 1 max e∋v f (e) -min e∋v f (e) otherwise
The mapping f is called a gap vertex-distinguishing edge coloring if distinct vertices have distinct labels. Such a coloring is called a gap-k-coloring.

The minimum positive integer k for which G admits a gap-k-coloring is called the gap chromatic number of G and is denoted by gap(G). Necessary and sufficient conditions for the existence of such a coloring are given by the following proposition: To illustrate these concepts, consider the graph G shown in Figure 4.1(a). A 6-edge coloring f 1 of G is given in Figure 4.1(b) and a 5-edge coloring f 2 of G is given in Figure 4.1(c). For example, in Figure 4.1(b), the vertex w is incident to two edges colored 2 and one edge colored 3, then l 1 (w) = 1, while the vertex z is incident with one edge colored 6, then l 1 (z) = 6. The resulting vertex labels are distinct for both figures. By Lemma 4.2, we have gap(G) ≥ 5, hence we can immediately conclude that gap(G) = 5.

After a strong analysis of this problem, we raised the conjecture asserting that there is no graph G of order n with gap(G) > n + 1. Conjecture 4.3 For every connected graph G of order n ≥ 3, we have gap(G) ∈ {n -1, n, n + 1}.

In the following sections, we prove this conjecture for a large set of graphs and we even decide the exact value of gap(G). The rest of this chapter is organized as follows: first, we give in Section 4.2 some motivations to investigate this new parameter. The results of Section 4.3 will confirm our conjecture for a large part of graphs with minimum degree at least 2. In Section 4.4, we prove our conjecture for some classes of graphs with minimum degree 1, such as paths, complete binary trees and all trees with at least two leaves at distance 2. This classification of our results according to δ(G) is due to the definition of our parameter, especially to the definition of labels of vertices of degree one. Finally, concluding remarks are given in the last section.

Motivation

In this section, we describe the motivation to study the gap coloring problem. First, we give the following proposition, where we recall that the diameter of a set S, denoted by diam(S) is the largest distance between any two points of the set. Proposition 4.4 Let S 1 and S 2 be two sets of positive integers, if diam(S 1 ) = diam(S 2 ), then S 1 = S 2 .

From the gap vertex labeling function (Definition 4.1), we observe that the label of every vertex v with degree at least 2 is the diameter of the set of colors incident to v. Note that this is not the case for the vertices of degree 1. Then, the gap labeling of a graph G can be seen as a strong version of set and multisets labelings (defined in the previous chapter). Indeed, according to Proposition 4.4, a gap distinguishing labeling of a graph G is also a multiset distinguishing labeling of G and a set distinguishing labeling (if δ(G) > 1). Hence, we now characterize the relationship between our coloring parameter and the two coloring parameters χ ′ 0 (G) and c(G) defined previously. The following results follows from Proposition 4.4 and the definitions of χ ′ 0 (G) and c(G).

Lemma 4.5 For every graph G without components isomorphic to either K 1 or K 2 and with minimum degree at least 2, we have

χ ′ 0 (G) ≤ gap(G)
Lemma 4.6 For every graph G, without components isomorphic to either K 1 or K 2 , we have c(G) ≤ gap(G)

We will see in Corollary 4.17 how the results of our parameter can be connected to the study of χ ′ 0 (G).

Gap chromatic number of graphs with minimum degree at least two

The main result of this section is the following:

Theorem 4.7 For every m-edge-connected graph G of order n with m ≥ 2,

gap(G) = n if G is not a cycle of length ≡ 2, 3(mod 4) n + 1 otherwise
The proof of Theorem 4.7 is the combination of several results detailed below.

Gap chromatic number of cycles

Theorem 4.8 Let C n be a cycle of order n, then

gap(C n ) = n if n ≡ 0, 1(mod 4) n + 1 otherwise Proof. Let C n = (v 1 , v 2 , . . . , v n , v n+1 = v 1 ). For each integer i with 1 ≤ i ≤ n, let e i = v i v i+1
. We consider two cases as follows:

Case 1: n ≡ 0, 1(mod 4). By Lemma 4.2, we have gap(C n ) ≥ n, it then suffices to prove that C n admits a gap-n-coloring. Two subcases are considered: Subcase 1.1: n ≡ 0(mod 4). A mapping f from E(C n ) to {1, 2, . . . , n} is defined as follows (see Figure 4.2(a)).

For

1 ≤ i ≤ n, f (e i ) =        n + 1 -i if i is odd 1 if i ≡ 2(mod 4) 2 if i ≡ 0(mod 4)
This mapping induces the following gap vertex labeling function:

For

1 ≤ i ≤ n, l(v i ) =        n -i + 1 if i ≡ 2(mod 4) n -i if i ≡ 0, 3(mod 4) n -i -1 if i ≡ 1(mod 4)
Then, it is easy to check that l is a bijection from

V (C n ) to {0, 1, . . . , n -1}. Hence gap(C n ) = n.
Subcase 1.2: n ≡ 1(mod 4). A mapping f from E(C n ) to {1, 2, . . . , n} is defined as follows (see Figure 4.2(b)):

For

1 ≤ i ≤ n, f (e i ) =        i if i is odd n -1 if i ≡ 2(mod 4) n if i ≡ 0(mod 4)

Gap chromatic number of graphs with minimum degree at least two 27

This mapping induces the following gap vertex labeling function:

For 1 ≤ i ≤ n, l(v i ) =        n -i if i ≡ 1, 2(mod 4) n -i + 1 if i ≡ 0(mod 4) n -i -1 if i ≡ 3(mod 4)
Then, it is easy to check that l is a bijection from

V (C n ) to {0, 1, . . . , n -1}. Hence gap(C n ) = n.
Case 2: n ≡ 2, 3(mod 4). We first prove that gap

(C n ) > n. Let f : V (C n ) -→ {1, 2, .
. . , n} be any edge-coloring of C n which induces a gap vertex-distinguishing function l. Now note that:

n i=1 l(v i ) =| f (e 1 ) -f (e n ) | + n i=2 | f (e i ) -f (e i-1 ) |= n(n -1) 2
In this formula, each term f (e i ) appears twice with opposite (or same) signs, hence

n(n-1) 2
is even. But this latter value is odd if n ≡ 2, 3(mod 4), which is a contradiction. Thus, gap(C n ) ≥ n + 1. It then remains to show that gap(C n ) ≤ n + 1. Two subcases are considered according to whether n mod 4 = 2 or 3. Subcase 2.1: n ≡ 3(mod 4). We know that C n+1 admits a gap-(n + 1)-coloring. Necessarily, C n+1 must contain two successive edges of same color j where 1 ≤ j ≤ n + 1. By merging these two edges into a single edge colored by j, we obtain a gap-(n + 1)-coloring of C n (see Figure 4.2(c)). Subcase 2.2: n ≡ 2(mod 4). In this subcase, we define an edge coloring f from E(C n ) to {1, 2, . . . , n, n + 1} by (see Figure 4.2(d)) : f (e n ) = f (e n-1 ) = 2, f (e n-2 ) = 3 and

For 1 ≤ i ≤ n -3, f (e i ) =        n + 2 -i if i is odd 1 if i ≡ 2(mod 4) 2 if i ≡ 0(mod 4)
This mapping induces the following gap vertex distinguishing labeling:

l(v n-2 ) = 2, l(v n-1 ) = 1, l(v n ) = 0 and For 1 ≤ i ≤ n -3, l(v i ) =        n -i if i ≡ 1(mod 4) n + 2 -i if i ≡ 2(mod 4) n + 1 -i if i ≡ 0, 3(mod 4)
Then, it is easy to check that l is a bijection from the vertex set of C n to the set {0, 1, . . . , n} \ {3}. Hence gap(C n ) = n + 1.

Gap chromatic number of m-edge-connected graphs

We first introduce a definition which plays a pervasive role in this section.

Definition 4.2 Let G be a graph of order n with V (G) = {v 1 , v 2 , . . . , v n } and let f be an edge coloring of G. For every vertex v of G, we define the interval

I(v) = [minf (e) e∋v , maxf (e) e∋v ]. We say that f is balanced if I(v 1 )∩I(v 2 )∩• • •∩I(v n ) = ∅.
The following proposition summarizes an important property of our coloring parameter.

Proposition 4.9 Let G be a graph with δ(G) ≥ 2. If there exists a spanning subgraph H of G with δ(H) ≥ 2 and there exists a gap vertex-distinguishing balanced edge coloring f of H with k colors, then gap(G) ≤ k.

Proof. Under the stated hypothesis, the gap vertex-distinguishing labeling of H is induced by a balanced edge coloring f with k colors. Therefore, there exists at least an integer j where 1 ≤ j ≤ k such that ∀v ∈ V , we have j ∈ I(v). By coloring the edges of G \ H with the color j, we obtain a gap-k-coloring of G. Hence gap(G) ≤ k.

We illustrate the interest of Proposition 4.9 by considering the following example: let G be a Hamiltonian graph of order n ≡ 0(mod 4). In the proof of Theorem 4.8 (Subcase 1.1), it is easy to check that the proposed edge coloring of C n is balanced. Indeed, for each vertex v in G, we have 2 ∈ I(v). Hence, We can extend the edgecoloring of C n to an edge-coloring of G by weighting the added edges with color 2 without affecting the gap chromatic number of C n . Thus, for every Hamiltonian graph G of order n ≡ 0(mod 4), we have gap(G) = n.

The following proposition will be useful for proving Theorem 4.7. Furthermore, it provides a useful tool for proving other results.

Gap chromatic number of graphs with minimum degree at least two 29

Proposition 4.10 If G = (V, E) is an m-edge-connected graph of order n (with m ≥ 2), different from a cycle of length ≡ 1, 2 or 3(mod 4), then for every integer a ≥ 0, there exists an (a + n)-edge-coloring f which induces a gap vertexdistinguishing labeling l : V → {a, a + 1, . . . , a + n -1}.

Proof. The proof of this proposition is done by giving a polynomial-time coloring algorithm. Let us begin with some definitions and notations. For every subset S of V , let N S denote the set of neighboring vertices of S, not included in S.

N S = {u ∈ V \ S : ∃v ∈ S for which (v, u) ∈ E}
For every two adjacent vertices u and v of G such that v ∈ S and u ∈ N S , let P (v, u) be a function which returns a path (or cycle) from v to a vertex w ∈ S that passes through u, such that the set of vertices between v and w does not belong to S.

Let f be an edge coloring of G. For every subgraph R of G, let g(R) be a function defined on the set E(R) as follows:

g(R) = min{f (E(R) \ {1, 2}}
We denote by Q the set of all graphs that are isomorphic to a cycle of order multiple of 4 or to two cycles having at least one vertex in common.

Observation Every m-edge-connected graph G (with m ≥ 2), different from a cycle of length ≡ 1, 2 or 3(mod 4) contains at least one subgraph H ∈ Q.

It is clear that if G is a 2-edge-connected graph, different from a cycle, then △(G) ≥ 3. Hence, the subgraph H can always be obtained from G. The basic idea of our algorithm is to find a balanced (a + n)-edge-coloring f of a 2-edge-connected spanning subgraph G ′ = (V ′ , E ′ ) of G. Initially, both sets V ′ and E ′ are empty. During the algorithm, the updating of V ′ and E ′ is done gradually through a specific edge coloring procedure (which is explained in more detail below). When an edge of G is colored by this procedure it is inserted into

E ′ . A vertex v ∈ V is inserted into V ′ if
and only if it is incident with at least two colored edges (e, s ∈ E ′ ). Note that when a vertex v is inserted in V ′ , we set the label l(v) as l(v) = |f (e)f (s)| and the interval I(v) at [min(f (e), f (s)), max(f (e), f (s))]. Such an edge coloring will ensure that for every interval I(v), we have 2 ∈ I(v).

In more details, the proposed algorithm starts by coloring the edges of a subgraph H ∈ Q of G of order k which induces a gap vertex-distinguishing labeling of H, where the vertices of H are labeled by distinct numbers ranging from n + ak to n + a -1. We can easily establish this labeling structure for every subgraph H of G which is isomorphic to a member of Q. Then, we propose four edge-coloring functions to color the set of edges which constructs a cycle that has an unique vertex in V ′ or a path between two vertices of V ′ . This last step is iterated until all vertices are labeled (i.e.,

|V ′ | = |V | ).
In order to color the subgraph H, we need to define several edge-coloring functions. For a proper understanding of our algorithm, we are going to present the algorithm for a graph G which contains at least one cycle of length multiple of 4. Otherwise, all other edge-coloring functions of H are described in detail in the Appendix of [START_REF] Tahraoui | Gap vertexdistinguishing edge colorings of graphs[END_REF]. The different steps of the algorithm are illustrated in the example of Figure 4.3, where a = 12.

Algorithm 1

Input: An integer a ≥ 0 and a m-edge-connected graph G = (V, E) of order n, such that m ≥ 2 and G is not isomorphic to a cycle of length ≡ 1, 2 or 3(mod 4).

Output: A balanced (a + n)-edge-coloring f of G which induces a gap vertex- distinguishing function l : V → {a, a + 1, . . . , a + n -1}.

Begin of Algorithm

Step 1:

V ′ ← ∅, E ′ ← ∅. Let an index t = 2.
Step 2: Take any subgraph

H = R 1 ∈ Q of G. 2.1 If (R 1 is a cycle of length k ≡ 0(mod 4)) Then Let H = (v 1 , v 2 , . . . , v k , v k+1 = v 1 ). For each integer i with 1 ≤ i ≤ k, let e i = v i v i+1 . A mapping f from E(R 1 ) to {1, 2, .
. . , a + n} is defined as follows:

For

1 ≤ i ≤ k, f (e i ) =        n + a -i + 1 if i is odd 1 if i ≡ 2(mod 4) 2 if i ≡ 0(mod 4)
This mapping induces the following vertex labeling of R 1 :

For

1 ≤ i ≤ k, l(v i ) =        n + a -i + 1 if i ≡ 2(mod 4) n + a -i if i ≡ 0, 3(mod 4) n + a -i -1 if i ≡ 1(mod 4)
Then, it is easy to check that l is a bijection from the vertex set of R 1 to the set {n

+ a -1, n + a -2, . . . , n + a -k}.
Otherwise all other edge-coloring functions of R 1 are described in detail in the Appendix of [START_REF] Tahraoui | Gap vertexdistinguishing edge colorings of graphs[END_REF].

2.2 V ′ ← V (R 1 ), E ′ ← E(R 1 ) and set z = g(R 1 ).
Step 3: While ( V ′ = V ) do Begin while 3.1 Take any two adjacent vertices u and v such that v ∈ V ′ and u ∈ N V ′ . 3.2 Let R t = P (v, u), we represent the obtained subgraph R t by the walk

(v 1 = v, v 2 = u, . . . , v k-1 , v k ). For each integer i with 1 ≤ i ≤ k -1, let 4.3.
Gap chromatic number of graphs with minimum degree at least two 31

e i = v i v i+1
. We now define an edge coloring f of R t . Four cases are considered according to the value of k mod 4.

Case 1: k ≡ 0(mod 4). A mapping f from E(R t ) to {1, 2, . . . , a + n} is defined as follows:

f (e k-1 ) = z -k + 2 and For 1 ≤ i ≤ k -2, f (e i ) =        z -i if i is odd 1 if i ≡ 0(mod 4) 2 if i ≡ 2(mod 4)
This mapping induces the following gap vertex labeling of

R t : l(v k-1 ) = z -k and For 2 ≤ i ≤ k -2, l(v i ) =        z -i -1 if i ≡ 1, 2(mod 4) z -i -2 if i ≡ 3(mod 4) z -i if i ≡ 0(mod 4)
Case 2: k ≡ 2(mod 4). A mapping f from E(R t ) to {1, 2, . . . , a + n} is defined as follows:

For

1 ≤ i ≤ k -1, f (e i ) =        z -i if i is even 1 if i ≡ 3(mod 4) 2 if i ≡ 1(mod 4)
This mapping induces the following gap vertex labeling of R t .

For

2 ≤ i ≤ k -1, l(v i ) =        z -i -1 if i ≡ 0, 1(mod 4) z -i -2 if i ≡ 2(mod 4) z -i if i ≡ 3(mod 4) Case 3: k ≡ 1(mod 4). A mapping f from E(R t ) to {1, 2, . . . , a + n} is defined as follows: f (e 1 ) = z -2 and For 2 ≤ i ≤ k -1, f (e i ) =        z -i if i is odd 1 if i ≡ 2(mod 4) 2 if i ≡ 0(mod 4)
This mapping induces the following gap vertex labeling of

R t : l(v 2 ) = z -3 and For 3 ≤ i ≤ k -1, l(v i ) =        z -i -1 if i ≡ 0, 3(mod 4) z -i -2 if i ≡ 1(mod 4) z -i if i ≡ 2(mod 4) Case 4: k ≡ 3(mod 4). A mapping f from E(R t ) to {1, 2, . . . , a + n} is defined as follows: f (e k-1 ) = z -k + 2 and For 1 ≤ i ≤ k -2, f (e i ) =        z -i if i is even 1 if i ≡ 3(mod 4) 2 if i ≡ 1(mod 4)

Chapter 4. Gap Vertex-Distinguishing Edge Colorings of Graphs

This mapping induces the following gap vertex labeling of R t : l(v k-1 ) = zk, and

For 2 ≤ i ≤ k -2, l(v i ) =        z -i -1 if i ≡ 0, 1(mod 4) z -i -2 if i ≡ 2(mod 4) z -i if i ≡ 3(mod 4)
Observation: In the previous four cases, it is easy to check that l is a bijection from the vertex set

V (R t ) -{v 1 , v k } to {z -3, z -4, . . . , z -k}. 2.3 V ′ ← V ′ ∪ V (R t ), E ′ ← E ′ ∪ E(R t ). Set z = g(R t ) and t = t + 1.

End while

Step 4: For all edges e ∈ E \ E ′ , set f (e) = 2.

End of algorithm.

We now present the proof of correctness of the above algorithm. We first show that this algorithm achieves its goal without blocking, i.e., both actions in Step 3 (3.1 and 3.2) satisfy the following assertions:

If |V ′ | < |V | then N V ′ = ∅. (4.1)
For every vertex u ∈ N V ′ there exists a path from u to a vertex v ∈ V ′ of order at least 2. (4.

2)

The assertion (1) follows from the connectivity hypothesis on G. For a vertex u ∈ N V ′ there exists, at last, an edge (u, v) ∈ E such that v ∈ V ′ . The 2-edgeconnectivity hypothesis of G implies that every edge of G belongs to a cycle, then the two vertices u and v belong to the same cycle. Therefore, the assertion (2) also holds.

We now prove that our coloring algorithm gives a gap vertex-distinguishing function l : V ′ → {a, a + 1, . . . , a + n -1} of G ′ induced by a balanced edge coloring f with a + n colors. At the end of the loop of Step 3, we obtain a bijection l from the set V ′ to the set {a, a + 1, ..., a + n -1}, i.e., for any two vertices u, v of V ′ , we have l(u) = l(v). It then remains to show that f is a balanced edge-coloring and for every vertex v of V ′ , we have l(v) equal to max e∋v f (e)min e∋v f (e) in G ′ . By considering the degree in G ′ of each vertex v, we have two cases. Case 1. d(v) = 2: from the algorithm, it is clear that the label of each vertex v of degree 2 which is incident with two edges e and s of

E ′ is equal to |f (e) -f (s)|. Case 2. d(v) > 2: let R(v) = {R d 1 , R d 2 , . . . , R dp } denote the set of all subgraphs having a common vertex v, where d 1 ≤ d 2 ≤ • • • ≤ d p .
From the algorithm, we can observe that (see Figure 4.3(g)):

• for any two subgraphs R i and R j of R(v), we have

E(R i ) ∩ E(R j ) = ∅.
• v is incident with exactly two edges e d 1 and

s d 1 of E(R d 1 ). Let f (e d 1 ) ≥ f (s d 1 ), then the label of v is fixed as l(v) = f (e d 1 ) -f (s d 1 ).
4.3. Gap chromatic number of graphs with minimum degree at least two 33 • for every subgraph R i of R(v), where i ≥ d 2 , we have v is incident with one or two edges of E(R i ).

(a) (b) (c) (d) (e) (f) (g) (h)
Furthermore, according to the edge coloring f , we can easily see that:

• for every vertex v of G ′ , we have 2 ∈ I(v).

• 1 ≤ f (s d 1 ) ≤ 2 and f (e d 1 ) ≥ g(R d 1 ) ≥ 2. • for every subgraph R i of R(v), where i ≥ d 2 then ∀e ∈ E(R i ) with v ∈ e, we have 2 ≤ f (e) ≤ g(R d 1 )
.

From these observations we can conclude the following:

• the edge-coloring f is balanced.

• for every vertex v of V ′ , max e∋v f (e) = f (e d 1 ) and min e∋v f (e) = f (s d 1 ).

At

Step 4 of the algorithm, we know that the obtained edge coloring f of G ′ is balanced. Hence, we can extend G ′ to G by coloring the added edges with color 2 without affecting the vertex labeling function l : V → {a, a + 1, . . . , a + n -1}.

Now, we can state the proof of Theorem 4.7. To proceed, we introduce the following result. We can now conclude that the result of Theorem 4.7 is a direct consequence of Theorem 4.8 and Theorem 4.11. Here we generalize the previous results to a special case of disconnected graphs as follows:

Theorem 4.12 If G is a graph of order n with connected components G 1 , . . . , G t , such that for every component G i of G, G i is different from a cycle of length ≡ 1, 2, 3(mod 4) and the edge connectivity of each component of G is at least 2, then gap(G) = n Proof. Let n i be the order of G i (1 ≤ i ≤ t).
The proof is essentially due to Proposition 4.10. The idea is to provide a gap vertex distinguishing edge coloring for each component of G i according to the parameter a of Proposition 4.10 as follows: by applying this proposition in sequence to G 1 , G 2 , . . . , G t , we can obtain the labeling function l : V (G i ) → {a, a + 1, . . . , a + n i -1} induced by an edge coloring f with a + n i colors such that a = n -i j=1 n j . From this, it is easy to check that l is a bijection from the vertex set of G to the set {0, 1, 2, . . . , n -1}. Thus gap(G) = n.

We believe that the result of Theorem 4.7 can be extended to all graphs of minimum degree at least 2. But we have not been able to prove it. We suggest the following conjecture: Conjecture 4.13 For every connected graph G of order n with minimum degree δ(G) ≥ 2, we have

gap(G) = n + 1 if G is a cycle of length ≡ 2, 3(mod 4)
n otherwise

Gap chromatic number of graphs with minimum degree one

In this section we give the value of gap(G) for some classes of graphs with δ(G) = 1.

Gap chromatic number of paths

Theorem 4.14 Let P n be the path of order n. Then

gap(P n ) = n -1 if n ≡ 0, 1(mod 4) n otherwise
Proof. The proof of this theorem is similar to the one of Theorem 4.8. Let

V (P n ) = (v 1 , v 2 , . . . , v n ). For each integer i with 1 ≤ i ≤ n -1, let e i = v i v i+1 .
We consider two cases as follows:

Case 1: n ≡ 0, 1(mod 4). By Lemma 4.2, we have gap(P n ) ≥ n -1, it then suffices to prove that P n admits a gap-(n -1)-coloring. Two subcases are considered: Subcase 1.1: n ≡ 0(mod 4). A mapping f from E(P n ) to {1, 2, . . . , n -1} is defined as follows (see Figure 4.4(a)).

For

1 ≤ i ≤ n -1, f (e i ) =        i 2 if i even n-2 2 if i ≡ 3(mod 4) n -1 if i ≡ 1(mod 4)
This mapping induces the following vertex labeling function:

l(v n ) = n-2 2 and for 1 ≤ i ≤ n -1, l(v i ) =            n-i-2 2 if i ≡ 0(mod 4) n -1 -i-1 2 if i ≡ 1(mod 4) n -1 -i 2 if i ≡ 2(mod 4) n-i-1 2 if i ≡ 3(mod 4)
Then, it is easy to check that l is a bijection from

V (P n ) to {0, 1, . . . , n -1}. Hence gap(P n ) = n -1.
Subcase 1.2: n ≡ 1(mod 4). A mapping f from E(P n ) to {1, 2, . . . , n -1} is defined as follows (see Figure 4.4(b)).

For

1 ≤ i ≤ n -1, f (e i ) =        i 2 if i even n-1 2 if i ≡ 3(mod 4) n -1 if i ≡ 1(mod 4)
This mapping induces the following vertex labeling function:

and for

1 ≤ i ≤ n -1, l(v i ) =            n-1-i 2 if i ≡ 0(mod 4) n -1 -i-1 2 if i ≡ 1(mod 4) n -1 -i 2 if i ≡ 2(mod 4) n-i 2 if i ≡ 3(mod 4)
Then, it is easy to check that l is a bijection from

V (P n ) to {0, 1, . . . , n -1}. Hence gap(P n ) = n -1.
Case 2: n ≡ 2, 3(mod 4). We first prove that gap

(P n ) > n -1. Let f : V (P n ) -→ {1, 2, .
. . , n-1} be any edge-coloring of P n which induces a gap vertex-distinguishing labeling l. We note that:

n i=1 l(v i ) = f (e 1 ) + f (e n-1 ) + n-1 i=2 | f (e i ) -f (e i-1 ) |= n(n -1) 2
In this formula, each term f (e i ) appears twice with opposite (or same) signs, hence

n(n-1) 2
is even. But this latter value is odd if n ≡ 2, 3(mod 4), which is a contradiction. Thus, gap(P n ) ≥ n. It then remains to show that gap(P n ) ≤ n. Two subcases are considered according to whether n mod 4 = 2 or 3. Subcase 2.1: n ≡ 3(mod 4). We know that P n+1 admits a gap-n-coloring. Necessarily P n+1 must contain two successive edges of same color j where 1 ≤ j ≤ n. By merging these two edges into a single edge colored by j, we obtain a gap-n-coloring of P n (see Figure 4.4(c)). Subcase 2.2: n ≡ 2(mod 4) In this subcase, we define an edge coloring f from

E(P n ) to {1, 2, . . . , n} (see Figure 4.4(d)) by f (e n-1 ) = n -1 and For 1 ≤ i ≤ n -2, f (e i ) =        i 2 + 1 if i even n 2 if i ≡ 3(mod 4) n if i ≡ 1(mod 4)
This mapping induces the following gap vertex distinguishing labeling:

l(v 1 ) = n, l(v n-1 ) = n 2 -1,l(v n ) = n -1 and for 2 ≤ i ≤ n -2, l(v i ) =            n-i 2 -1 if i ≡ 0(mod 4) n -i+1 2 if i ≡ 1(mod 4) n -i 2 -1 if i ≡ 2(mod 4) n-i-1 2 if i ≡ 3(mod 4)
Then, it is easy to check that l is a bijection from

V (P n ) to {0, 1, . . . , n} \ { n 2 }. Hence gap(P n ) = n. (a) (b) (c) (d)

Gap chromatic number of trees

We first determine the gap chromatic number of complete binary trees. We denote by BT h a complete binary tree of height h > 0, note that BT h has exactly 2 h+1 -1 vertices.

Theorem 4.15 For any complete binary tree BT h of order n = 2 h+1 , we have

gap(BT h ) = n -1
Proof. By Theorem 4.14, we have gap(BT 1 ) = gap(P 3 ) = 3. Then, we may restrict our attention to h ≥ 2. By Lemma 4.2, we have gap(BT h ) ≥ n -1, it then suffices to prove that BT h admits a gap-(n -1)-coloring. We define the level l(u) of vertex u of BT h as the number of edges along the unique path between it and the root. Similarly, the level of an edge e = (u, v) of BT h is l(e) = max{l(u), l(v)}. We represent the vertices and the edges of BT h , level by level, left to right by the sequence v 1 , v 2 , . . . , v n and e 1 , e 2 , . . . , e n-1 , respectively (see Figure 4.5(a)). We now define a mapping f from E(BT h ) to {1, 2, . . . , n -1} as follows.

For

1 ≤ i ≤ n -1, f (e i ) = 2h if i ≤ 2 i + 2(h -l(e i )) if i ≥ 3
This mapping induces the following gap vertex labeling:

l(v i ) = i -1 for 1 ≤ i ≤ n.
Then it is easy to check that l is a bijection from V (BT h ) to {0, 1, . . . , n -1}. Thus gap(BT h ) = n -1. The following theorem gives an upper bound on the gap chromatic number of general trees. Theorem 4.16 Let T = (V, E) be a tree of order n which has at least two leaves u and v at distance two, then gap(T ) ≤ n

Proof. The proof of this theorem is done by giving a polynomial-time algorithm. We first start with some definitions used in the following. Let R 1 = (u, w, v) be a path of T (where u, v are leaves) and let R be the subtree of T rooted at w and induced by the set V \ {u, v} (see Figure 4.6(a)). Let h be the depth of R. For every level i of R, let L i denote the set of leaves at level i. Let S be a subset of V (R) and for every vertex x of V (R) \ S, let P (x, S) be the function which returns a path from x to a vertex y ∈ S, such that the set of vertices between x and y does not belong to S.

Let l be a vertex labeling of V (T ). For every path P of T , let g(P ) be the function defined as follows:

g(P ) = min{l(v) : ∀v ∈ V (P )}
The different steps of Algorithm 2 are illustrated in the example of Figure 4.6. Algorithm 2 Input: A tree T = (V, E) of order n with two leaves u and v at distance 2.

Output: A gap-n-coloring of T . Begin of Algorithm Set f : E(R 1 ) → {1, n} as follows: f (vw) = n, f (uw) = 1.
This mapping induces the following gap vertex labeling of R 1 :

l(v) = n, l(w) = n-1 and l(u) = 1. Let S = {w}, z = n -1 and t = 2.
For i = 1 to h do Begin For For every vertex x of L i in the subtree R do Begin For Let R t = P (x, S). We denote the path R t by the sequence of vertices

v 1 = x, v 2 , . . . v k-1 , v k . For each integer i with 1 ≤ i ≤ k -1, let e i = v i v i+1 . Set an edge coloring f of R t as follows:
For

1 ≤ i ≤ k -1, f (e i ) = z -i+1 2 if i odd i 2 otherwise
This mapping induces the following gap vertex labeling of R t .

For (c),(d),(e),(f) illustrates the coloring of R 2 , R 3 , R 4 , R 5 , respectively. (g) A gap-14coloring of T . Now, we present the proof of correctness for the above algorithm. At the end of this algorithm, we obtain a bijection l from V to the set {1, 2, ..., n}. It then remains to show the property of our coloring parameter. By considering the degree of each vertex v of T , we have three cases:

1 ≤ i ≤ k -1, l(v i ) = z -i S ← S ∪ V (R t ), z ← g(R t ), t ← t + 1. End for End for End of Algorithm (a) (b) (c) (d) (e) (f) (g)
Case 1. d(v) = 1: from the algorithm, it is clear that l(v) = f (e) e∋v .
Case 2. d(v) = 2: from the algorithm, it is clear that the label of vertex v of degree 2 which is incident with two edges e and s of

E equals |f (e) -f (s)|. Case 3. d(v) > 2: let R(v) = {R d 1 , R d 2 , . . . , R dp } denote the set of all paths having the vertex v in common, where d 1 ≤ d 2 ≤ • • • ≤ d p .
We represent the distance between two vertices x, y ∈ V by dist(x, y). From the algorithm, we can observe that:

• every path R i of R(v) contains a leaf l i of T which is an endpoint of R i . We can see that dist(v, l d 1 ) ≤ dist(v, l d 2 ) ≤ • • • ≤ dist(v, l dp ).
• for any two paths R i and

R j of R(v), E(R i ) ∩ E(R j ) = ∅.
• the vertex v is incident with exactly two edges e d 1 and

s d 1 of E(R d 1 ). Let f (e d 1 ) ≥ f (s d 1 ), then the label of v is fixed as l(v) = f (e d 1 ) -f (s d 1 ). • for every path R i of R(v), where i ≥ d 2 , the vertex v is incident to exactly one edge e i of E(R i ).
Furthermore, according to the edge-coloring f , we can see that:

• f (s d 1 ) = ⌈ dist(v,l d 1 ) 2 ⌉.
• for every path R i of R(v), where i ≥ d 2 , we consider two cases for the value of f (e i ) (with v ∈ e i ) according to the distance between v and l i :

• dist(v, l i ) is even. We have f (e i ) = dist(v,l i ) 2 . Hence f (s d 1 ) ≤ f (e i ) ≤ g(R d 1 ) ≤ f (e d 1 ). • dist(v, l i ) is odd. We have f (e i ) = g(R i ) + dist(v,l i )-1 2 . Hence f (s d 1 ) ≤ f (e i ) ≤ g(R d 1 ) ≤ f (e d 1 ).
From these observations, we can conclude that for every vertex v of V , f (e d 1 ) = max e∋v f (e) and f (s d 1 ) = min e∋v f (e). Hence, T admits a gap-n-coloring.

Conclusion

In this chapter, we studied a new variant of graph edge coloring that induces a vertex distinguishing labeling. Exact results are given for paths, cycles, some trees and all m-edge-connected graphs with m ≥ 2. Our results are summarized in the follwoing table.

Graph classes gap(G)

Cycle C n of order n ≡ 2, 3(mod 4) gap(C n ) = n + 1 Cycle C n of order n ≡ 0, 1(mod 4) gap(C n ) = n m-edge connected graph G (with m ≥ 2) different from a cycle gap(G) = n Path P n of order n ≡ 2, 3(mod 4) gap(P n ) = n Path P n of order n ≡ 0, 1(mod 4) gap(P n ) = n -1 complete binary tree BT h of order n = 2 h+1 gap(BT h ) = n -1
Tree T of order n which has at least two leaves u and v at distance two gap(G) ≤ n Table 4.1: Our summary results on the gap chromatic number

The study of the relationships between our parameter and the point distinguishing problem gives the following result which is a direct consequence of Lemma 4.5 and Theorem 4.12.

Corollary 4.17 If G is a graph of order n with connected components G 1 , . . . , G t , such that for every component G i of G, G i is different from a cycle of length ≡ 1, 2, 3(mod 4) and the edge connectivity of each component of G is at least 2, then χ ′ 0 (G) ≤ n.
Part II

Graph Packing Problem

Chapter 5

Labeled Packing of Graphs In this chapter, we focus on graph packing problems, which are a well-known field of graph theory for over 30 years. We start in Section 5.1 by presenting a variety of results, some quite recent, concerning the packing of unlabeled graphs. We then discuss the relationship between the embedding of graphs and the structure of the embedding permutations. In Section 5.2, we introduce and study a new variant of the graph packing problem, called the labeled packing of graphs. In particular, we present some results and conjectures about cycles.

Packing and embedding of unlabeled graphs

Basic definitions

We here consider only finite simple graphs and use standard terminology notation from Chapter 2 except when indicated. We recall that if a graph G has order n and size m, we say that G is an (n, m)-graph. For more brevity, we will call an unlabeled graph simply a graph.

A permutation σ is an one-to-one mapping of a set S into itself. We say that an element e of S is a fixed point of a given permutation σ if σ(e) = e. Then, a permutation σ is called fixed-point-free if σ has no fixed point. Any permutation σ of a finite set can be written as the disjoint union of cycles (two cycles are disjoint if they do not have any common element). Here, a cycle (a 1 , a 2 , . . . , a n ) is a permutation sending a i to a i+1 for 1 ≤ i ≤ n -1 and a n to a 1 . This representation is called the cyclic decomposition of σ and is denoted by C(σ). In this context, the cycles of length one correspond to fixed points of σ.

The study of graph packing was initiated in the 1970s by Bollobás and Eldridge [Bol78, BE78], Sauer and Spencer [START_REF] Sauer | Edge disjoint placement of graphs[END_REF], and Catlin [START_REF] Catlin | Subgraphs of graphs[END_REF].

Definition 5.1 Let G 1 , G 2 , . . . , G k be k graphs of order n. We say that there is a packing of G 1 , . . . , G k (into the complete graph K n ) if there exist k permutations σ i : V (G i ) -→ V (K n ), i = 1, . . . , k, such that σ * i (E(G i )) ∩ σ * j (E(G j )) = ∅ for i = j, where the mapping σ * i : E(G i ) -→ E(K n ) is the one induced by σ i .
By definition, two graphs, G 1 and G 2 , of the same order

pack if G 1 is a subgraph of the complement G 2 of G 2 , or, equivalently, if G 2 is a subgraph of the complement G 1 of G 1 . A packing of k copies of the same graph G into K n will be called a k-placement of G. A packing of two copies of G in K n (i.e., a 2-placement) is called an embedding of G (into its complement G).
In other words, an embedding of a graph G is a permutation σ on V (G) such that if an edge vu belongs to E(G) then σ(v)σ(u) does not belong to E(G). If there exists an embedding of G into K n , we say that G is embeddable. For example, the following figure presents a packing of two copies of P 4 ∪ P 3 into K 7 , where the dotted edges represent the second copie of P 4 ∪ P 3 . This embedding can also be represented by the following cyclic decomposition: (x 2 )(x 7 )(x 4 )(x 1 , x 6 )(x 3 , x 5 ).

G 1 (V 1 , E 1 ) and G 2 (V 2 , E 2 ) with |V (G 1 )| = |V (G 2 )|, G 1 is isomorphic to G 2 if and only if (1) G 1 and G 2 are packable into K n and (2) G 1 and G 2 are packable into K n .
Example 5.3 The independence number α(G) (α(G) represents the size of the largest independent set of G) of a graph G of order n is at least p if and only if G and the graph K p ∪ (np)K 1 (i.e., the graph consisting of the k-clique and np isolated vertices) are packable into K n .

In 1959, Erdős and Gallai [START_REF] Erdős | On maximal paths and circuits of graphs[END_REF] proved that every graph G with n vertices and more than n(k-1) 2 edges contains a path of length k. Motivated by this result, Erdős and Sós made the following conjecture in 1963.

Conjecture 5.1 If G is a graph of order n and E(G) > n(k-1)

2

, then G contains every tree T of size k.

Example 5. [START_REF] Tahraoui | Labeled packing of Graphs[END_REF] We can easily see that if

|E(G)| > n(k-1) 2 then |E(G)| < n(n-k) 2 .
Thus, Conjecture 5.1 can be formulated as follows: let G be a graph of order n and T any tree of order k, with k < n.

If |E(G)| < n(n-k) 2
then there exists a packing of G and T into K n .

Packing of graphs is a heavily studied subject having many applications in computer science (see e.g. [START_REF] Bollobás | Packing of graphs and applications to computational complexity[END_REF][START_REF]An ω(n 4 3 ) lower bound on the randomized decision tree complexity of graph properties[END_REF]). The reader can find a good survey on packing of graphs in [START_REF] Wozniak | Packing of graphs and permutations-a survey[END_REF] and [START_REF] Yap | Packing of graphs-a survey[END_REF]. In general, the review of existing literature identifies three different lines of research. The first one is about packing of general graphs having small size in K n (e.g. (n, m)-graphs with m ≤ n). The second one deals with packing of graphs with bounded maximum degree and bounded girth in K n . The last one considers some additional properties of permutations in the packing construction. We present in the following some important results in these areas.

Packing of graphs of small size in a complete graph

In 1978, Bollobás and Eldridge [START_REF] Bollobás | Packing of graphs and applications to computational complexity[END_REF] made the following conjecture about the existence of a k-packing of graphs of small size, which is generally considered to be one of the most important open problems in graph packing theory.

Conjecture 5.2 ([BE78]) Let G 1 , G 2 . . . G k be k graphs of order n. If |E(G i )| ≤ n -k, i = 1, 2, . . . k, then G 1 , G 2 , . . . G k are packable into K n .
So far only the cases k = 2 and k = 3 of this conjecture were proved in [START_REF] Sauer | Edge disjoint placement of graphs[END_REF] and [START_REF] Kheddouci | On the packing of three graphs[END_REF], respectively. This shows the hardness of the problem and motivates future research. In what follows, we survey some of the well known results relative to the number of graphs to pack.

Packing of two graphs

The following theorem was independently proposed in [Bol78, BS77, SS78].

Theorem 5.3 ([Bol78, BS77, SS78]) Let G = (V, E) be a graph of order n. If |E(G)| ≤ n -2 then G can be embedded in its complement.
The example of the star S n shows that Theorem 5.3 cannot be improved by raising the size of G even in the case when G is a tree. However, in this case we have the following theorem, proved in [START_REF] Burns | Embedding (n, n -1)-graphs in their complements[END_REF], which completely characterizes the embedding of (n, n -1) graphs.

Theorem 5.4 ([BS78]) Let G = (V, E) be a graph of order n. If |E(G)| ≤ n -1 then either G is embeddable in its complement or G is isomorphic to one of the following graphs: K 1,n-1 , K 1,n-4 ∪ K 3 with n ≥ 8, K 1 ∪ K 3 , K 2 ∪ K 3 , K 1 ∪ 2K 3 , K 1 ∪ C 4 .
Among the exceptions mentioned in this theorem, the star K 1,n-1 is the only graph which is connected. Therefore, we have the following immediate consequence (proved also in [START_REF] Hedetuiemi | A note on packing two trees into k n[END_REF]).

Theorem 5.5 ([HHS81])

Let T be a tree of order n, T = K 1,n-1 . Then T is contained in its own complement.

These results has been improved in many ways. In Section 5.1.4, we are interested in improvements that deal with some additional properties of the permutation structure.

Packing of three graphs

We are now going to consider the problem of packing of three graphs. We begin with a theorem about the 3-placement of (n, n -2)-graphs, proved in [START_REF] Wozniak | Triple placement of graphs[END_REF], which can be considered as an extension of Theorem 5.3.

Theorem 5.6 ([WW93]) Let G = (V, E) be a graph of order n. If |E(G)| ≤ n -2 then either there exists a 3-placement of G or G is isomorphic to K 3 ∪ 2K 1 or to K 4 ∪ 4K 1 .
The following theorem refines Theorem 5.6 by specifying the permutation structure of the 3-placement of G (see [START_REF] Wozniak | Embedding graphs of small size[END_REF]).

Theorem 5.7 ([Woz94]) Let G = (V, E) be a graph of order n, G = K 3 ∪ 2K 1 , K 4 ∪ 4K 1 . If |E(G)| ≤ n -2, then there exists a permutation σ on V (G) such that σ 1 , σ 2 , σ 3 define a 3-placement of G.
Moreover, all cycles of σ have length 3, except for 1 of length one if n ≡ 1(mod 3) or two of length 1 if n ≡ 2(mod 3). Now, consider the packing of three copies of a tree. Obviously, if there is a packing of three copies of T into K n , then we have

3(n -1) ≤ n(n -1) 2
which implies n ≥ 6. Furthermore, since every vertex v of T with degree d(v) = △(T ) must be mapped with two other vertices with degree at least one, then, we must assume that △(T ) ≤ n -3. However, Huang and Rosa [START_REF] Huang | Decomposition of complete graphs into trees[END_REF] observed that these two necessary conditions are not sufficient as shown by the graph of Figure 5.2. In [START_REF] Wang | Packing three copies of a tree into complete graph[END_REF], Wang and Sauer characterized all the trees T such that T is 3placeable. The packing of three different trees into K n has been considered by Wozniak [START_REF] Wozniak | Packing three trees[END_REF], who proved the following theorem.

Theorem 5.8 ([Woz96]) Let T 1 , T 2 , T 3 be three trees of order n. Then there is a packing of T 1 , T 2 , T 3 into K n+1 . To the best of our knowledge, only two graph packing results are known for the general case [START_REF] Brandt | On cyclic packing of a tree[END_REF][START_REF] Zak | A note on k-placeable graphs[END_REF]. In [START_REF] Brandt | On cyclic packing of a tree[END_REF], Brandt and Wozniak considered another special case of Conjecture 5.2. In particular, they considered the packing of k copies of a tree into K n , where k = ⌊ n 2 ⌋.

Theorem 5.9 ([BW04]) Let T be a tree of size ⌈ n 2 ⌉. Then there exists a packing of ⌊ n 2 ⌋ copies of T into K n .

Recently, Zak [START_REF] Zak | A note on k-placeable graphs[END_REF] studied for the first time the packing problem for all k, and proved the following result.

Theorem 5.10 ( [START_REF] Zak | A note on k-placeable graphs[END_REF]) Let k be a positive integer and G be a graph of order

n ≥ 2(k -1) 3 . If |E(G)| ≤ n -2(k -1) 3 , then G is k-placeable.
On the basis of Conjecture 5.2, the bound on the size of a graph in Theorem 5.10 is rather far from what can be expected. However, to the best of our knowledge, this work is the first attempt that consider the general case of Conjecture 5.2.

Packing graphs with bounded maximum degree and bounded girth in a complete graph

The graph packing theory also investigates two important directions concerning graphs with bounded maximum degree and bounded girth. The two main conjectures in this area were given by Bollobás and Eldridge [START_REF] Burns | Embedding (n, n -1)-graphs in their complements[END_REF] and Faudree et al.

[FRSS81], respectively.

Conjecture 5.11 ([BE78])

Let G 1 and G 2 be two graphs of order n with maximum degrees △ 1 and △ 2 . If (△ 1 + 1)(△ 2 + 1) ≤ n + 1, then there is a packing of G 1 and G 2 . If Conjecture 5.11 is true, then Conjecture 5.11 would be sharp, and considered as an extension of the Hajnal-Szemerédi theorem [START_REF] Hajnal | Proof of conjecture of erdos[END_REF] on equitable colorings. Indeed, the Hajnal-Szemerédi theorem is a special case of Conjecture 5.11 when G 2 is the disjoint union of cliques of the same size. This conjecture has been proved in the case △ 1 ≤ 2 by Aigner and Brandt [START_REF] Aigner | Embedding arbitrary graphs of maximum degree two[END_REF], and independently by Alon and Fischer [START_REF] Alon | 2-factors in dense graphs[END_REF]. The case when △ 1 = 3 and n is huge has been proved by Csaba et al. in [START_REF] Csaba | Proof of a conjecture of bollobás and eldridge for graphs of maximum degree three[END_REF]. Bollobás et al. [START_REF] Bollobás | Packing d-degenerate graphs[END_REF] proved a strengthening of the conjecture when G 1 is d-degenerate and d < △ 1 40 . Eaton [START_REF] Eaton | A near packing of two graphs[END_REF] showed that under the given condition, there is a near-packing of degree 1 of G 1 and G 2 , that is, an embedding of the two graphs into a common vertex set such that the maximum degree of the subgraph defined by the edges common to both copies is at most 1. Recently, Kaul et al. [START_REF] Kaul | On a graph packing conjecture by bollobás, eldridge and catlin[END_REF] proved Conjecture 5.11 for graphs with large maximum degrees. They proved in particular that for

△ 1 , △ 2 ≥ 300, if (△ 1 + 1)(△ 2 + 1) ≤ 0.6n + 1, then G 1 and G 2 pack.
In [START_REF] Faudree | Embedding graphs in their complements[END_REF], Conjecture 5.12 was proved for every graph G with n vertices and no more than 6 5 n -2 edges. Wozniak [START_REF] Wozniak | A note on embedding raphs without short cycles[END_REF] proved that a graph G without cycles of length at most 7 is embeddable. This result was improved later by Brandt [START_REF] Burris | The irregular coloring number of a tree[END_REF] who showed that a graph G without cycles of length at most 6 is embeddable. Recently, Görlich and Zak [START_REF] Görlich | A note on packing graphs without cycles of length up to five[END_REF] proved that a graph G without cycles of length at most 5 is embeddable.

Graph packing and permutation structure

In this section, we review some results concerning the relationship between the embedding of graphs and the structure of the embedding permutations. This study allows us to obtain some results concerning our graph packing problem which will be introduced in Section 5.2. Let us start by the permutations with no fixed point. In [START_REF] Schuster | Fixed-point-free embeddings of graphs in their complements[END_REF], Schuster proved the following theorem.

Theorem 5.13 ([Sch78]) Let G = (V, E) be a graph of order n. If |E(G)| ≤ n -2
then there exists an embedding σ of G such that σ has no fixed point.

The above theorem cannot be improved by increasing the number of edges as shown by the graphs K 1,2 ∪ K 3 and K 1,3 ∪ K 3 . However, all the other (n, n -1)-graphs that are contained in their complements can be embedded without fixed points. More precisely, we have the following theorem (proved also in [START_REF] Schuster | Fixed-point-free embeddings of graphs in their complements[END_REF]).

Theorem 5.14 ( [START_REF] Schuster | Fixed-point-free embeddings of graphs in their complements[END_REF]) Let G = (V, E) be a graph of order n with E(G) ≤ n-1. If (i) G is not an exceptional graph of Theorem 5.4 and (ii) G = K 1,2 ∪ K 3 and G = K 1,3 ∪ K 3 , then there exists a fixed-point-free embedding of G.

Other work deal with the study of families of embeddable graphs such that the corresponding permutation is cyclic. First of all, we formulate some results proved in [START_REF] Wozniak | On cyclically embeddable graphs[END_REF] in the following theorem. 3. cycles C n for n ≥ 6.

4. unicyclic graphs, except graphs that are not embeddable at all (See [START_REF] Faudree | Embedding graphs in their complements[END_REF])

and five graphs given in Figure 5.3.

G = K 1,2 ∪ K 3 , K 1,3 ∪ K 3 , K 1 ∪ C 5 .
Then there exists a cyclic embedding of G.

Assume that an embedding σ of G is expressed as the product of disjoint cycles (consedring σ as a permutation). The previous results can be improved in another direction by specifying the size and the number of cycles occurring in the embedding permutation. We begin with a theorem about embedding of (n, n-1)-graphs, proved in [START_REF] Benhocine | On self-complementation[END_REF], which can be considered as an improvement of Theorem 5.14. Theorem 5.17 ( [START_REF] Benhocine | On self-complementation[END_REF]) Let G = (V, E) be a graph of order n, n ≡ 0, 1(mod4). If E(G) ≤ n -1 then either there exists an embedding σ of G having all its cycles of length 4, except for one of length 1 if n is odd, or G is isomorphic to one of the following graphs:

K 1,n-1 , K 1,n-4 ∪ K 3 , n ≥ 8, K 1 ∪ C 4 , K 1 ∪ K 3 , K 2 ∪ K 3 .
The other cases (where n ≡ 2, 3(mod 4)) have been investigated by Wozniak in [START_REF] Wozniak | Embedding graphs of small size[END_REF]. Another possibility for improvement of Theorem 5.13 is the following theorem proved in [START_REF] Wozniak | Embedding graphs of small size[END_REF]. Finally, it is also interesting to note that another way to study the graph packing problem is to consider the placement of graphs into a (partial) subgraph of a complete graph. In this case, it is necessary to consider more information about the permutation structure. We can mention for example the paper of Kheddouci [START_REF] Kheddouci | A note on packing of two copies of some trees into their third power[END_REF] that considers the packing of trees in their third power.

Our observations

The graph packing problem has attracted considerable attention from many researchers. However, the most of existing work focuses on unlabeled graphs. Therefore, it is interesting to consider this problem on labeled graphs, which we will be done in the rest of this part. To the best of our knowledge, this variant has not been studied so far.

Labeled Packing Problem

In this section, we introduce and study the packing problem for a vertex labeled graph.

Definitions and general results

We first give the formal definition of our packing problem. Roughly speaking, it consists of a graph packing which preserves the labels of the vertices. Definition 5.2 Let p be an integer greater than one and let G 1 , G 2 , . . . , G k be k copies of a graph G = (V, E). Let f be a mapping from V (G) to the set of labels {1, 2, . . . , p}. The mapping f is called a p-labeled packing of k copies of G into K n if there exist permutations σ i : V (G i ) -→ V (K n ), where i = 1, . . . , k, such that:

1. σ * i (E(G i )) ∩ σ * j (E(G j )) = ∅ for all i = j. 2. for every vertex v of G, we have f (v)=f (σ 1 (v))=f (σ 2 (v)) • • • =f (σ k (v)).
For example, the following figure presents a 5-labeled packing of two copies of P 4 ∪ P 3 , where the dotted edges represent the second copie of P 4 ∪ P 3 . From the previous definition, we define our packing parameter as follows: Naturally, the existence of a packing of k copies of a graph G is a necessary and sufficient condition for the existence of a p-labeled packing of k copies of G (where p ≥ 1). Indeed, it suffices to choose the mapping f : V (G) -→ {1}. Then, we obtain the following proposition.

Proposition 5.19 For every graph G, if there exists a k-placement of G into K n , then

λ k (G) ≥ 1.
The following lemma is a direct consequence of Definition 5.2.

Lemma 5.20 Let G be a graph of order n and let H be a spanning subgraph of G.

If there exists a packing of k copies of G into K n , then

λ k (H) ≥ λ k (G).
Let us introduce the following notations: let G be a graph of order n and f be a mapping from V (G) to {1, 2, . . . , p}. We define S(f ) as the subset of labels that occur only once in f (V (G)) and let V S(f ) consist of the vertices colored with the labels of S(f ). Thus it is obvious that |V S(f ) | = |S(f )|. Throughout this part, a labeled packing of two copies of G will be called a labeled embedding of G.

The following lemma gives an upper bound on the labeled embedding number λ 2 (G).

Lemma 5.21 Let G be a graph of order n and let I be a maximum independent set of G. If there exists an embedding of G, then

λ 2 (G) ≤ |I| + ⌊ n -|I| 2 ⌋
Proof. Let f be a mapping from V (G) to {1, 2 . . . , p} corresponding to a p-labeled embedding of G with p maximum, (i.e., p = λ 2 (G)). A necessary condition for the existence of a p-labeled embedding of G is that for every two adjacent vertices of G, one of their labels must occur at least twice in f (V (G)). Hence, it is easy to see that all vertices of V S(f ) form an independent set in G. Then, we have

|V S(f ) | ≤ |I| and p ≤ |V S(f ) | + ⌊ n-|V S(f ) | 2 ⌋. Since g(x) = x + ⌊ n-x 2 ⌋ is an increasing function of x, it follows that p ≤ |I| + ⌊ n-|I|
2 ⌋, giving the desired result.

Using the same sketch of proof as before, we can show a similar upper bound on λ 3 (G) as follows:

Lemma 5.22 Let G be a graph of order n and let I be a maximum independent set of G. If there exists a 3-placement of G into K n , then Remark We explain in this observation a fundamental congruence relation between the labeled embedding number and the permutation structure. For any labeled embedding of a graph G induced by a permutation σ, we can see that the vertices of every cycle of C(σ) share the same label. Hence, we can say that the labeled embedding number of G denotes the maximum number of cycles induced by a permutation of G. The following lemma is thus obtained. Lemma 5.23 Let G be a graph. If G has an embedding σ with p cycles, then λ 2 (G) ≥ p Therefore, we can observe that the graph packing can be used to distinguish some vertices of G as follows: let f be a mapping from V (G) to {1, 2, . . . , p} and let σ be a permutation embedding on V (G), where for every two vertices u, v ∈ V (G), we have

λ 3 (G) ≤ |I| + ⌊ n -|I| 3 ⌋ (a) (b)
f (u) = f (v) if u, v belong to the same cycle in σ(T ) f (u) = f (v)
otherwise.

In Section 5.1.4, we have presented some results on graph embedding that deal with some additional properties of the embedding permutation. These results can be exploited to obtain a lower bound on λ 2 (G) for some families of graphs. For example, from the statements of Theorem 5.18 and Lemma 5.23, we can deduce the following corollary:

Corollary 5.24 Let G = (V, E) be a graph of norder n. If |E(G)| ≤ n -2 then λ 2 (G) ≥ ⌊ n 3 ⌋
In the same way, the following corollary is an immediate consequence of Theorem 5.17 and Lemma 5.23.

Corollary 5.25 Let G = (V, E) be a graph of order n ≡ 0, 1(mod )4. If |E(G)| ≤ n-1 then λ 2 (G) ≥ ⌊ n 4 ⌋ or G is isomorphic to one of the following graphs K 1,n-1 , K 1,n-4 ∪ K 3 , n ≥ 8, K 1 ∪ C 4 , K 1 ∪ K 3 , K 2 ∪ K 3 , K 1 ∪ 2K 3 .
As seen previously, graph packing is a very hard problem; the main results concern graphs of small size ((n, nq) graphs where q ≥ 0). Two studies are possible for the labeled graph packing problem: (i) packing an important number of sample graphs (or copies of a given graph) in a complete graph; or (ii) packing a fixed number (usually two) of non trivial graphs in a subgraph of K n . For the first study of labeled packing of graphs, we opt for the first possibility. We will give some results concerning the labeled packing number of k copies of cycles (where k ≥ 2).

Given a graph G, the generalization of Lemma 5.21 for any k is not trivial. Yet, it becomes easier when G is a cycle. We know that any complete graph K n can be decomposed into n-1 2 Hamilton cycles if n is odd and n-2 2 Hamilton cycles plus a perfect matching if n is even (see [START_REF] Lucas | Récréations mathématiques[END_REF]). Thus, C n cannot admit a packing of k copies in K n if n ≤ 2k.

Lemma 5.26 For every cycle C n of order n ≥ 2k + 1, we have

λ k (C n ) ≤ ⌊ n 2 ⌋ + ⌊ n -⌊ n 2 ⌋ k ⌋ Proof.
Let f be a mapping from V (G) to {1, 2, . . . , p} corresponding to a p-labeled packing of k copies of C n with p maximum. Let us introduce the following notation: for a set S ⊆ V (G), we denote by N (S) the neighborhood of S, i.e., the set of all vertices of G which have a neighbor in S. Then, two necessary conditions for the existence of p-labeled packing of k copies of C n are that:

1. the labels of N (V S(f ) ) must occur at least k times in f (V (C n )).

the labels of

V \ (V S(f ) ∪ N (V S(f ) )) must occur at least twice in f (V (C n )).
Hence, we have

p ≤ |V S(f ) | + ⌊ |N (V S(f ) )| k ⌋ + ⌊ n -|V S(f ) | -|N (V S(f ) )| 2 ⌋ Since k ≥ 2, the maximum value p is obtained when |V S(f ) | = ⌊ n 2 ⌋ and |N (V S(f ) )| = n -⌊ n
2 ⌋, giving the desired result.

Labeled-packing of k copies of cycles with order at least 4k

In this section, we determine the exact value of the labeled packing number of k copies of cycles of order n ≥ 4k. It is done by proving that the upper bound of Lemma 5.26 is reached for all n = 4k + x, where k > 2 and x mod 4 = 2.

Theorem 5.27 For every cycle C n of order n = 2km + x, where k, m ≥ 2 and x < 2k, we have

λ k (C n ) =        n 2 + 1 if (x mod 4, m) = (2, 2) and k > 2. ⌊ n 2 ⌋ + m + 1 if x = 2k -1. ⌊ n 2 ⌋ + m otherwise.
Proof. Several cases are considered in this proof according to the values of x and m. In Figure 5.6, we outline the general scheme of our proof. Case 1 :

x mod 4 = 2. Let C n = (v 1 , v 2 , .
. . , v n ) be a cycle of order n, where n ≥ 4k. From Lemma 5.26, we have

λ k (C n ) ≤ ⌊ n 2 ⌋ + ⌊ n-⌊ n 2 ⌋ k ⌋, it then suffices to prove that C n admits a (⌊ n 2 ⌋ + ⌊ n-⌊ n 2 ⌋ k ⌋)
-labeled packing of k copies. In order to simplify our proof, we consider three subcases according to the values of m and x as follows:

= k + x 2m such that for 0 ≤ i ≤ p -1, b i = {v i 1 , v i 2 , . . . , v i 2m }
, where v i j = v 2im+j . These notations are illustrated in the example of Figure 5.7 , where n = 16 and k = 3. A mapping f from V (C n ) to {1, 2, . . . , ⌊ n 2 ⌋ + m} is now defined as follows: for every set b i in B, let

f (v i 2j+1 ) = im + j + 1 for 0 ≤ j ≤ m -1. f (v i 2j ) = n 2 + j for 1 ≤ j ≤ m. Let σ 0 (C n ), σ 1 (C n ), σ 2 (C n ), . . . , σ k-1 (C n ) be a packing of k copies of C n into K n
under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively, where for 0 ≤ t ≤ k -1,

σ t (v i 2j+1 ) = v i 2j+1 for all (i, j) satisfying 0 ≤ i ≤ p -1 and 0 ≤ j ≤ m -1. σ t (v i 2j ) = v (i+t) mod p 2j
for all (i, j) satisfying 0 ≤ i ≤ p -1 and 1 ≤ j ≤ m. From the set of permutations, we can easily see that for every vertex

v i in V (C n ), we have f (v i ) = f (σ 1 (v i )) = f (σ 2 (v i )) = • • • = f (σ k-1 (v i )). It then remains to show that the set of cycles σ 0 (C n ) = C n , σ 1 (C n ), σ 2 (C n ) . . . , σ k-1 (C n ) are edge-disjoint into K n .
To prove this, it suffices to show that for every vertex v i of V (C n ), we have:

For 0 ≤ t = l ≤ k -1, if σ t (v i ) = σ l (v i ), then σ t (v i+1
) and σ t (v i-1 ) must be different from both σ l (v i+1 ) and σ l (v i-1 ).

From the set of permutations, we can observe that for every two distinct integers l, t ∈ {0, 1, . . . , k -1} and for every set b i of B, we have v i 2j+1 , where 0 ≤ j ≤ m -1. Then for every set b i of B, we consider two cases according to whether j = 1 or j = 1.

σ l (v i 2j+1 ) = σ t (v i 2j+1 ) = (
1. for j = 3, 5 . . . 2m -1, we have σ l (v i j+1 ), σ l (v i j-1 ) ∈ b (l+i) mod p and σ t (v i j+1 ), σ t (v i j-1 ) ∈ b (t+i) mod p . It follows that (l + i) mod p = (t + i) mod p = i.
2. for j = 1, we can easily see that σ l (v i 2 ) and σ l (v i-1 2m ) are both different from σ t (v i 2 ) and σ t (v i-1 2m ).

Hence, according to the two previous observations, we can see that

C n , σ 1 (C n ), σ 2 (C n ), . . . , σ k-1 (C n ) are k pairwise edge-disjoint cycles, thus the mapping f is a (⌊ n 2 ⌋ + m)-labeled-packing of k copies of C n .
Subcase 1.2: x = 2k -1. In this case, the partition Using the same proof as in Subcase 1.1, we can show that the mapping f is a

B = {b 0 , b 1 , . . . , b k-1 } of V (C n ) is defined as follows: for 0 ≤ i ≤ k -2, b i = {v i 1 , v i 2 , . . . , v i 2(m+1) } and b k-1 = {v k-1 1 , v k-1 2 , . . ., v k-1 2m+1 }, where v i j = v 2i(m+1)+j . A mapping f from V (C n ) to {1, 2, . . . , ⌊ n 2 ⌋ + m + 1} is now defined as follows: for every set b i in B, let f (v i 2j+1 ) = i(m + 1) + j + 1 for 0 ≤ j ≤ m and (i, j) = (k -1, m). f (v k-1 2m+1 ) = n-1 2 + m + 1. f (v i 2j ) = n-1 2 + j for 1 ≤ j ≤ m + 1 and (i, j) = (k -1, m + 1). Let σ 0 (C n ), σ 1 (C n ), . . . , σ k-1 (C n ) be a packing of k copies of C n into K n under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively, where σ 0 (C n ) = C n and for 1 ≤ t ≤ k -1, let σ t (v i 2j+1 ) = v i 2j+1 for all (i, j) satisfying 0 ≤ i ≤ k -1, 0 ≤ j ≤ m and (i, j) = (k -1, m). σ t (v i 2j ) = v (i+t) mod k 2j for all (i, j) satisfying 0 ≤ i ≤ k -1, 1 ≤ j ≤ m + 1 and (i, j) = (k -t -1, m + 1). σ t (v k-1 2m+1 ) = v t-1 2m+2 . σ t (v k-t-1 2m+2 ) = v k-1 2m+1 = v n .
(⌊ n 2 ⌋ + m + 1)-labeled-packing of k copies of C n . Subcase 1.3: x mod 2m = 0 and x = 2k -1. Let B = {b 0 , b 1 , . . . , b p-1 } be a partition of V (C n ) into p = k + ⌈ x 2m ⌉ sets such that for 0 ≤ i ≤ p -2, b i = {v i 1 , v i 2 , . . . , v i 2m } and b p-1 = {v p-1 1 , v p-1 2 , . . . , v p-1 x mod 2m }, where v i j = v 2im+j . We let r = x mod 2m. A mapping f from V (C n ) to {1, 2, . . . , ⌊ n 2 ⌋ + m} is defined as follows: f (v i 2j+1 ) = im + j + 1 for all (i, j) satisfying 0 ≤ i ≤ p -2, 0 ≤ j ≤ m -1. f (v i 2j ) = ⌊ n 2 ⌋ + j for all (i, j) satisfying 0 ≤ i ≤ p -2, 1 ≤ j ≤ m. f (v p-1 2j+1 ) = (p -1)m + j + 1 for 0 ≤ j ≤ ⌈ r-1 2 ⌉ -1. f (v p-1 2j ) = ⌊ n 2 ⌋ + j for 1 ≤ j ≤ ⌊ r-1 2 ⌋. f (v p-1 r ) = ⌊ n 2 ⌋ + m. Let σ 0 (C n ), σ 1 (C n ), . . . , σ k-1 (C n ) be a packing of k copies of C n into K n under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively, where σ 0 (C n ) = C n and for 1 ≤ t ≤ k -1, let σ t (v i 2j+1 ) = v i 2j+1 for all (i, j), 0 ≤ i ≤ p -2 and 0 ≤ j ≤ m -1. σ t (v i 2j ) = v (i+t) mod p 2j
for all (i, j),

0 ≤ i ≤ p -2 and 1 ≤ j ≤ ⌊ r-1 2 ⌋. σ t (v i 2j ) = v (i+t) mod (p-1) 2j
for all (i, j), Using the same proof as in Subcase 1.1, we can show that the mapping f is a

0 ≤ i ≤ p -2 and ⌊ r-1 2 ⌋ + 1 ≤ j ≤ m -1. σ t (v i 2m ) = v (i+t) mod p 2m for 0 ≤ i = p -t -1 ≤ p -2. σ t (v p-t-1 2m ) = v p-1 r = v n . σ t (v p-1 2j+1 ) = v p-1 2j+1 for 0 ≤ j ≤ ⌈ r-1 2 ⌉ -1. σ t (v p-1 2j ) = v t-1 2j for 1 ≤ j ≤ ⌊ r-1 2 ⌋. σ t (v p-1 r ) = v t-1 2m .
(⌊ n 2 ⌋ + m)-labeled-packing of k copies of C n .
Case 2: x mod 4 = 2. We consider three subcases according to the value of k and m as follows: Subcase 2.1: k > 2 and m = 2. We first prove that λ k (C 4k+x ) < n 2 + 2. From Lemma 5.26, it follows that the value n 2 + 2 is an upper bound of λ k (C 4k+x ). We assume that there exists a mapping f :

V (C 4k+x ) -→ L = {1, 2, . . . , n 2 + 2} which is a ( n 2 + 2)-labeled-packing of C 4k+x . Let σ 0 (C 4k+x ), σ 1 (C 4k+x ), . . . , σ k-1 (C 4k+x
) be a packing of k copies of C 4k+x into K 4k+x under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively. We know that the vertices colored with the labels of S f form an independent set in C 4k+x (implying that |S f | ≤ n 2 ). We consider two cases according to the cardinality of S f as follows:

(a): |S f | < n 2 .
We know that each label of L\S f occurs at least k times in f (C 4k+x ). This requires at least 5k

+ x 2 -1 vertices in C 4k+x , which is a contradiction since k > 2. (b): |S f | = n 2 .
It means that the vertices colored with the labels of S f form a maximum independent set in C 4k+x . Then the two labels of L \ S f are attributed to the remaining vertices such that each label occurs at least k times. With this labeling scheme, there exist necessarily three vertices v i-1 , v i and v i+1 such that f (v i ) ∈ S f and f (v i-1 ), f (v i+1 ) = c ∈ L \ S f . This requires that the label c must occur at least 2k times in C 4k+x , yielding a contradiction. Hence λ k (C 4k+x ) < n 2 +2.

We now prove that λ k (C 4k+x ) = n 2 + 1. Let f be the mapping from V (C n ) to {1, 2, . . . , n 2 + 1} defined as follows:

f (v 2j+1 ) = j + 1 for j = 0, 1, . . . , n 2 -1. f (v 2j ) = n 2 + 1 for j = 1, 2 . . . , n 2 . Let σ 0 (C n ), σ 1 (C n ), . . . , σ k-1 (C n ) be a packing of k copies of C n into K n under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively, where σ 0 (C n ) = C n and for 1 ≤ t ≤ k -1: σ t (v 2j+1 ) = v 2j+1 for j = 0, 1, . . . , n 2 -1. σ t (v 2j ) = v 2(j+2t) mod n
for j = 1, 2 . . . , n 2 . According to this scheme, Figure 5.11 presents a 8-labeled-packing of three copies of C 14 .

= k + x 2m such that for 0 ≤ i ≤ p -1, b i = {v i 1 , v i 2 , . . . , v i 2m }, where v i j = v 2im+j . A mapping f from V (C n ) to {1, 2, . . . , ⌊ n 2 ⌋ + m} is defined as follows: for every set b i in B, let f (v i 2j+1 ) = im + j + 1 for 0 ≤ j ≤ m -1. f (v i 2j ) = n 2 + j for 1 ≤ j ≤ m. f (v n-1 ) = n 2 . f (v n ) = n 2 + m -1.
Let σ 0 (C n ), σ 1 (C n ), . . . , σ k-1 (C n ) be a packing of k copies of C n into K n under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively, where σ 0 (C n ) = C n and for 1 ≤ t ≤ p -1:

σ t (v i 2j+1 ) = v i 2j+1 for all (i, j) satisfying 0 ≤ i ≤ p -1, 0 ≤ j ≤ m -1. σ t (v i 2j ) = v (i+t) mod p 2j for all (i, j) satisfying 0 ≤ i ≤ p -1, 1 ≤ j ≤ m and j = m -1. σ t (v i 2m-2 ) = v (i+t) mod (p+1) 2m-2 for 0 ≤ i ≤ p -1 and i = p -t. σ t (v p-t 2m-2 ) = v n . σ t (v n-1 ) = v n-1 . σ t (v n ) = v t-1
2m-2 . Using the same proof as in Subcase 1.1, we can show that the mapping f is a (⌊ n 2 ⌋ + m)-labeled-packing of k copies of C n . To illustrate this case, Figure 5.13 presents a 13-labeled-packing of three copies of C 20 .

Labeled packing of k copies of cycles of order at most 4k -1

In the case where n is relatively small compared to k, some additional difficulties arise naturally, and λ k (C n ) has to be estimated differently. We know that any complete graph K n can be decomposed into n-1 2 Hamilton cycles if n is odd and n-2

2 Hamilton cycles plus a perfect matching if n is even. Thus, C n cannot admit a packing of k copies if n ≤ 2k. After deep analysis, we raise the following conjecture.

Conjecture 5.28 For every cycle C n of order n = 2k + x, where k ≥ 2 and 1 ≤ x ≤ 2k -1, then

λ k (C n ) = 2 if x = 1
and k is even.

x + 2 otherwise .

This conjecture asserts that the upper bound of Lemma 5.26 is reached for all n = 4k -1, 4k -2 and 4k -3, where (k, n) = (2, 5). We report in the following the results of our attempt to give some support to Conjecture 5.28 for some particular cases. 5). We know that a maximum independent set of C n has size ⌊ n 2 ⌋. Then, from Lemma 5.26, we have

Theorem 5.29 For every cycle

C n of order n = 2k + x, where k ≥ 2, 2k -3 ≤ x ≤ 2k -1 and (k, n) = (2, 5), we have λ k (C n ) = x + 2 Proof. Let C n = (v 1 , v 2 , . . . , v n ) be a cycle of order n = 2k + x, where 2k -3 ≤ x ≤ 2k -1 and (k, n) = (2,
λ k (C n ) ≤ ⌊ n 2 ⌋ + ⌊ n-⌊ n 2 ⌋ k ⌋ = x + 2,
it then suffices to prove that C n admits a (x + 2)-labeled packing of k copies. In what follows, we give the proof only for the case x = 2k -1, since the proofs of the other cases are similar.

Assume that x = 2k -1 and let

B = {b 0 , b 1 , . . . , b k-1 } be a partition of V (C n ) into k sets, such that for 0 ≤ i ≤ k -2, b i = {v i 1 , v i 2 , v i 3 , v i 4 },
{v k-1 1 , v k-1 2 , v k-1 3 }, where v i j = v 4i+j .
A mapping f from V (C n ) to {1, 2, . . . , 2k + 1} is defined as follows: We now present our results concerning the cycles of order 2k + 1 and 2k + 2.

f (v i 2j+1 ) = 2i + j + 1 for all (i, j) where 0 ≤ j ≤ 1, 0 ≤ i ≤ k -2. f (v i 2 ) = 2k for 0 ≤ i ≤ k -2. f (v i 4 ) = 2k + 1 for 0 ≤ i ≤ k -2. f (v k-1 1 ) = 2k -1. f (v k-1 2 ) = 2k. f (v k-1 3 ) = 2k + 1. Let σ 0 (C n ), σ 1 (C n ), . . . , σ k-1 (C n ) be a packing of k copies of C n into K n under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively, where σ 0 (C n ) = C n and for 1 ≤ t ≤ k -1, let σ t (v i 2j+1 ) = v i 2j+1 for all (i, j) satisfying 0 ≤ i ≤ k -2, 0 ≤ j ≤ 1. σ t (v i 2j ) = v (i+t) mod k 2j for all (i, j) satisfying 0 ≤ i ≤ k -2, 1 ≤ j ≤ 2. and (i, j) = (k -t -1, 2). σ t (v k-t-1 4 ) = v (k-1) 3 . σ t (v k-1 1 ) = v (k-1) 1 . σ t (v k-1 2 ) = v (t-1) 2 . σ t (v k-1 3 ) = v (t-1) 4 .
Theorem 5.30 For every prime number k > 2, we have λ k (C 2k+1 ) < 4.

Labeled Packing Problem 65

Proof. Let C 2k+1 = (v 1 , v 2 , . . . , v 2k+1 , v 2k+1 = v 1 ). We assume that there exists a mapping f : V (C 2k+1 ) -→ L = {1, 2, 3, 4} which is a 4-labeled packing of C 2k+1 . Let σ 0 (C 2k+1 ), σ 1 (C 2k+1 ), . . . , σ k-1 (C 2k+1 ) be a packing of k copies of C 2k+1 into K 2k+1 under the permutations σ 0 , σ 1 , . . . , σ k-1 , respectively. We consider two cases according to the cardinality of S f (which is defined in Section 5.2.1).

Case 1. |S f | = 0. In this case, each label occurs at least twice in f (V (C n )). Let us introduce the following notation: for every label i of L, let V i be the subset of vertices with color i. We know that σ

0 (C 2k+1 ) ∪ σ 1 (C 2k+1 ) ∪ • • • ∪ σ k-1 (C 2k+1 ) = K 2k+1 .
We know that all vertices of the complete graph are neighbors. Then, for every label i of L, the number of edges in the subgraph of K 2k+1 induced by the set

V i is |V i |(|V i |-1)

2

. Then, for every cycle σ i (C 2k+1 ) of the packing, we must have exactly

|V i |(|V i |-1) 2k
= p i edges between the vertices colored with i in the cycle σ i (C 2k+1 ). Hence, the following system of equations must have at least one solution.

|V i |(|V i | -1) = 2kp i for 1 ≤ i ≤ 4 (1) |V 1 | + |V 2 | + |V 3 | + |V 4 | = 2k + 1 (2)
From hypothesis, it is clear that the equation (1) has a solution if and only if

|V i | or |V i | -1 are multiples of k (where 1 ≤ i ≤ 4) since k is prime. Then we have |V 1 | + |V 2 | + |V 3 | + |V 4 | > 2k + 1
, therefore this system of equations has no solution which is a contradiction for k > 2.

Case 2. |S f | ≥ 1. Let v i be any vertex of V S(f ) . Then we consider two cases according to the labels of the neighbors vertices of v i .

Subcase 1. f (v i-1 ) = f (v i+1 ) = c. In this case, we must have at least 2k vertices colored with c. This requires at least 2k + 3 vertices in C 2k+1 , which is a contradiction.

Subcase 2. f (v i-1 ) = f (v i+1 ). From hypothesis, each of the two labels f (v i-1 ) and f (v i+1 ) must occur at least k times. This requires at least 2k + 2 vertices in C 2k+1 . Hence, we also reached a contradiction and the theorem is proved.

Using the same proof as in the above theorem, we obtain the following results. Theorem 5.31 For every even number k ≥ 2, where k is a power of 2, we have λ k (C 2k+1 ) = 2. Theorem 5.32 For every even number k ≥ 2, we have λ k (C 2k+2 ) < 5.

Summary and concluding remarks

In this section, we have proved the exact value of λ k (C n ) for all k ≥ 2 and n ≥ 4k-3. Our results are summarized in the follwoing table.

value of n λ 2 (C n ) n ≤ 4 no packing n = 5 2 n ≥ 6 ⌊ 3n 4 ⌋ n = 2km + x, where x < 2k and k > 2 λ k (C n ) n ∈ {3, 4, . . . , 2k} no packing n ∈ {2k + 1, 2k + 2, . . . , 4k -4} remains to prove n ≥ 4k -3 and (x mod 4 = 2 or m ≥ 3 ) ⌊ n 2 ⌋ + ⌊ n-⌊ n 2 ⌋ k ⌋ x mod 4 = 2 and m = 2 ⌊ n 2 ⌋ + ⌊ n-⌊ n 2 ⌋ k ⌋ -1
As a corollary, the exact value of the 2-labeled packing number of cycles is a direct consequence of Theorem 5.27, Theorem 5.29 and Theorem 5.31.

Corollary 5.33 Let C n be a cycle of order at least 5. Then Similarly, from Theorem 5.27 and Theorem 5.29, we immediately obtain the exact value of λ 3 (C n ) for all n ≥ 9. Then, it follows from Theorem 5.30 and Theorem 5.32 that λ 3 (C 7 ) < 4 and λ 3 (C 8 ) < 5. The 3-labeled packing and 4-labeled packing of three copies of C 7 and C 8 are shown in Figure 5.15 and Figure 5.16, respectively. Hence, we obtain the following corollary.

λ 2 (C n ) = ⌊ 3n 4 ⌋ if n > 5. 2 n = 5.
Corollary 5.34 Let C n be a cycle of order at least 7. Then

λ 3 (C n ) =            3 if n = 7. 4 if n = 8. 8 if n = 14. ⌊ n 2 ⌋ + ⌊ n-⌊ n 2 ⌋ 3 ⌋ otherwise.

Conclusion

In this chapter, we have introduced and studied a new graph packing problem, called labeled packing of graphs. One may consider two important issues: (i) packing important number of sample graphs (or copies of a given graph) in a complete graph; or (ii) packing a fixed number (usually two) of non trivial graph in a subgraph of K n . Our first contribution opted for the first possibility. In particular, we have studied the labeled packing number of k copies of cycles, in which the exact value of λ k (C n ) have been shown for all n ≥ 4k -3. A conjecture was given for the remaining cases.

In the next chapter, we will continue to study the labeled packing of graphs of small size such as trees and (n, n -2) graphs.

Chapter 6

Labeled Embedding of Trees and (n, n -2)-graphs This chapter deals with the labeled embedding of trees and (n, n -2)-graphs. In Section 6.1, we will introduce a new labeled embedding problem called labeled fixedpoint-free embedding of graphs (i.e., a labeled embedding without fixed vertices). Then we will show that the correlation between this problem and the labeled embedding problem allows to derive some results on λ 2 (G). In Section 6.2, we present some results on the labeled embedding number of a tree. Finally, in Section 6.3, an upper bound on the labeled embedding number of (n, n -2)-graphs is proposed.

Labeled fixed-point-free embedding of graphs

In correlation with the labeled embedding number, we introduce a new embedding problem called labeled fixed-point-free embedding of graphs. Definition 6.1 Let f be a mapping from V (G) to L = {1, 2, . . . , p}, which is a labeled embedding of G with p labels under the permutation σ. We say that f is a labeled fixed-point-free embedding if σ is a fixed-point-free permutation.

The maximum positive integer p for which G admits a labeled fixed-point-free embedding of G is called the labeled fixed-point-free embedding number and is denoted by α 2 (G).

The following lemma shows an upper bound on α 2 (G). Lemma 6.1 Let G be a graph of order n. If there exists an embedding of G into

K n , then α 2 (G) ≤ ⌊ n 2 ⌋.
Proof. We can easily verify that a necessary condition for the existence of p-labeled fixed-point-free embedding of G is that every label of L occurs at least twice in G, i.e., the upper bound of α 2 (G) is reached if and only if we find an embedding of G having all its cycles of length two (except one of length three if n is odd). Hence,

α 2 (G) ≤ ⌊ n 2 ⌋.
Given a graph G, the following lemma shows a lower bound on λ 2 (G) in terms of α 2 (G) as follows:

Lemma 6.2 Let G be a graph of order n and let X be any set of end vertices of G.

If there exists a fixed-point-free embedding of G[V \ X] with p labels into K n , then

λ 2 (G) ≥ |X| + p
Proof. By hypothesis, there exists a permutation σ ′ on V (T ) such that σ ′ is a fixed-point-free embedding with p labels. This permutation can be extended to a permutation σ on G as follows:

σ(x) = x for all x ∈ X and σ(y) = σ ′ (y) for all y ∈ V \ X From this permutation function, it is clear that for every edge xy ∈ E(G) such that x ∈ X and y ∈ V \ X, we have σ(x)σ(y) / ∈ E(G). Hence λ 2 (G) ≥ |X| + p.

We can conclude that the correlation between the two parameters λ 2 (G) and α 2 (G) allows to reach the upper bound of Lemma 5.21 if there is a maximum independent set in G with only vertices of degree 1.

As we have seen in Lemma 5.23, we can obtain the following lower bound on α 2 (G) which is related to the permutation structure. Lemma 6.3 Let G be a graph. If G has a fixed-point-free embedding σ with p cycles, then α 2 (G) ≥ p.

We note that the parameter α 2 (G) will be used frequently to prove the main results of the next section.

Labeled-embedding and labeled fixed-point-free embedding of paths

We first determine the exact value of the labeled embedding number of paths. It is done by proving that the upper bound of Lemma 5.21 is reached for all paths of order at least 5.

Theorem 6.4 Let P n be a path of order at least 4. Then

λ 2 (P n ) =            ⌊ 3n 4 ⌋
if n mod 4 = 0, 2, 3 and n > 4,

⌊ 3n 4 ⌋ + 1 if n mod 4 = 1 and n > 5, 3 if n = 5, 1 if n = 4.
Proof. Let P n = (v 1 , v 2 , . . . , v n ) be a path of order n where n ≥ 4. We consider four cases as follows:

Case 1: n mod 4 = 0, 2, 3 and n > 4. From Lemma 5.21, we have λ 2 (P n ) ≤ ⌊ 3n 4 ⌋, it then suffices to prove that P n admits a ⌊ 3n 4 ⌋-labeled embedding. Since P n is a spanning subgraph of C n , By putting together Lemma 5.20 and Corollary 5.33, we get λ

2 (P n ) ≥ λ 2 (C n ) = ⌊ 3n 4 ⌋.
Case 2: n = 4m + 1 and m ≥ 2. A mapping f : V (P n ) -→ {1, 2, . . . , ⌊ 3n 4 ⌋ + 1} is defined as follows:

f (v 2i+1 ) = i + 1 for i = 0 . . . 2m. f (v 2i ) = 2m + i + 1 for i = 1 . . . m. f (v 2i ) = m + i + 1 for i = m + 1 . . . 2m.
Let σ(P n ) be the embedding of P n in K n under the permutation σ where

σ(v 2i+1 ) = v 2i+1 for i = 0 . . . 2m. σ(v 2i ) = v 2(m+i) for i = 1 . . . m. σ(v 2i ) = v 2(i-m) for i = m + 1 . . . 2m.
This permutation induces the following path:

σ(P n ) = v 1 , v 2m+2 , v 3 , v 2m+4 . . . v 2m+1 , v 2 , v 2m+3 , v 4 , v 2m+5 . . . v 2m , v 4m+1
According to the permutation σ, it is clear that for every vertex v i in V (P n ), we have f

(v i ) = f (σ(v i ))
. It now remains to show that P n and σ(P n ) are edge-disjoint.

To do so, it suffices to show that:

for every vertex v i of P n , if σ(v i ) = v i then σ(v i+1 ) / ∈ {v i-1 , v i+1 }.
From the permutation σ, we have σ(v i ) = v i if and only if i is odd. Then we consider four cases for the vertices σ(v i+1 ) and σ(v i-1 ):

1. for i = 1, we have σ(v 2 ) = v 2m+2 .
2. for i = 3, 5, . . . 2m-1, we have v i-1 , v i+1 ∈ {v 2 , v 4 , . . . , v 2m } and σ(v i-1 ), σ(v i+1 ) ∈ {v 2m+2 , v 2m+4 , . . . , v 4m }.

for

i = 2m + 1, we have σ(v 2m ) = v 4m and σ(v 2m+2 ) = v 2 .
Case 3: n = 5. We first prove that λ 2 (P 5 ) < 4. We assume that there exists a mapping f : V (P 5 ) -→ L = {1, 2, 3, 4} which is 4-labeled embedding of P 5 . We can easily see that the existence of this 4-labeled embedding requires the existence of three independent vertices v 1 , v 3 and v 5 colored with three different labels {c 1 , c 2 , c 3 } ⊂ L, then the two vertices v 2 and v 4 are colored with the same label of L \ {c 1 , c 2 , c 3 }. We can easily see that this coloring scheme is not 4-labeled embedding of P 5 which is a contradiction with the hypothesis. We conclude that λ 2 (P n ) < 4. It then remains to show that λ 2 (P 5 ) = 3. This is proved by Figure 6.1. Case 4: n = 4. We can easily see that there is an unique embedding of P 4 into K 4 (Figure 6.2). This embedding scheme gives λ 2 (P 4 ) = 1. We now study the labeled fixed-point-free embedding number of paths. This result is crucial for the proof of our result in the next section. Theorem 6.5 Let P n be a path of order at least 4, then

α 2 (P n ) = ⌊ n 2 ⌋ if n > 5, 1 if n = 4, 5.
Proof. Let P n = (v 1 , v 2 , . . . , v n ) be a path of order n where n ≥ 4. We consider two cases depending on whether n > 5 or n ≤ 5.

Case 1: n > 5. From Lemma 6.1, we know that α(P n ) ≤ ⌊ n 2 ⌋. It now suffices to prove that P n admits a ⌊ n 2 ⌋-labeled fixed-point-free embedding into K n . We consider two subcases as follows: Subcase 1: n is even. We divide P into three subpaths as follows:

P 1 = (v 1 , v 2 , . . . , v n 2 -3 ) = (x 1 , x 2 , . . . , x n 2 -3 ). P 2 = (v n 2 -2 , v n 2 -1 , . . . , v n 2 +3 ) = (y 1 , y 2 , . . . , y 6 ). P 3 = (v n 2 +4 , v n 2 +5 , . . . , v n ) = (z 1 , z 2 , . . . , z n 2 -3
). We define the permutation σ of P as follows:

σ(P ) = (y 1 , y 3 )(y 2 , y 5 )(y 4 , y 6 )(x 1 , z 1 )(x 2 , z 2 )(x 3 , z 3 ) . . . (x n 2 -3 , z n 2 -3
). It is clear that all cycles of σ have length two. Hence, we have α

2 (P n ) = n 2 if n is even.
Subcase 2: n is odd. In this case the path P is divided as follows:

P 1 = (v 1 , v 2 , . . . , v n-7 2 ) = (x 1 , x 2 , . . . , x n-7 2
).

P 2 = (v n-7 2 +1 , v n-7 2 +2 , . . . , v n-7 2 +7 ) = (y 1 , y 2 , . . . , y 7 ). P 3 = (v n-7 2 +8 , v n-7 2 +9 , . . . , v n ) = (z 1 , z 2 , . . . , z n-7 2 -3
). We define the permutation σ of P as follows:

σ(P ) = (y 1 , y 3 )(y 2 , y 5 )(y 4 , y 6 , y 7 )(x 1 , z 1 )(x 2 , z 2 )(x 3 , z 3 ) . . . (x n-7 2 , z n-7 2 ).
Hence, we have α

2 (P n ) = n-1 2 if n is odd.
Case 2: n = 4, 5. Using the same proof idea as in the proof of Theorem 6.4 (Case 4), we show that α 2 (P 4 ) = α 2 (P 5 ) = 1.

Labeled embedding of caterpillars

A caterpillar is a tree which becomes a path when all its end vertices are removed.

The following theorem shows the exact value of the embedding number of caterpillars.

Theorem 6.6 Let C be a non-star caterpillar of order n with n ≥ 4 and let I be a maximum independent set of C. Then Proof. Let C be a non-star caterpillar; a maximum independent set I of C can be computed as follows: let I = S 1 ∪ S 2 , where S 1 is the set of vertices with degree one in C and S 2 is a maximum independent set of the subgraph of C induced by the vertices of degree two. Then, it follows from this construction that the vertices of V \ I belong to the central path of C. Hence, we can deduce the following observation:

λ 2 (C) =            |I| + ⌊ n-|I| 2 ⌋ if |V \ I| ≥ 5 or if C is isomorphic to one of the graphs of Figure 6.3, |I| + ⌊ n-|I| 2 ⌋ -1 if C is isomorphic to one of the graphs of Figure 6.4, |I| + ⌊ n-|I| 2 ⌋ -2 if C is isomorphic to
Chapter 6. Labeled Embedding of Trees and (n, n -2)-graphs

(a) (b) (c) (d) >0 >=0 v 2 v 3 v 4 v 5 >0 v 1 (e) (f) (g) >0 v 1 v 2 v 3 v 4 >0 >0 v 5 (h) Figure 6.3: Caterpillars with λ 2 (G) = |I| + ⌊ n-|I| 2 ⌋ Observation 6.7 The induced subgraph G[V \ I] is a set of paths.
Let f be a vertex labeling of C and let σ(C) be an embedding of C into K n under the permutation σ. We distinguish three cases according to the cardinality of V \ I as follows:

>1 >0 v 2 v 3 v 4 >1 v 1 (a) >1 v 1 v 2 v 3 >0 v 4 >1 >0 v 5 (b) (c) (d) Figure 6.4: Caterpillars with λ 2 (G) = |I| + ⌊ n-|I| 2 -1⌋ >0 >0 v 2 v 3 v 1 v 4 (a) >1 >1 v 2 v 3 v 4 v 1 (b) Figure 6.5: Caterpillars with λ 2 (G) = |I| + ⌊ n-|I| 2 -2⌋ Subcase 1: |V \ I| ≥ 6. Let H = C[V \ I].
The vertices of I are considered as fixed points under σ, i.e., for every vertex v of I, σ(v) = v and f (v) = f (σ(v)). Let P = (v 1 , v 2 , . . . , v m ) be the central path of C. We augment the edge set E(H) by connecting the two vertices v i-1 , v i+1 for all i such that v i ∈ I. Since v i is a fixed point, the edge v i-1 , v i+1 allows to avoid the following situation: σ(v i-1 ) = v i+1 or σ(v i+1 ) = v i-1 . From Observation 6.7, the induced subgraph H is a path of order at least 6. Then, we can derive from Theorem 6.5 a ⌊ |V \I| 2 ⌋-labeled fixed-point-free embedding of H. Therefore, we obtain by Theorem 6.2 that λ 2 (T ) = |I| + ⌊ n-|I| 2 ⌋.

Subcase 2: |V \ I| = 5. From Observation 6.7, we have that C[V \ I] is a set of paths. We create a path H as follows: let

H = C[V \ I] ∪ {v}, where v is a vertex of I which is adjacent to an end-vertex of C[V \ I].
Then, the subgraph H is a set of paths of order 6. From Theorem 6.5, we know that α 2 (C[V \ I]) = 3. Hence we obtain from Lemma 6.2 that λ 2 (C) = |I| + 2. For every vertex u i of S, f

(u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 3 ) = m + 1 and f (v 2 ) = f (v 5 ) = m + 2, σ(v 1 ) = v 3 , σ(v 3 ) = v 1 , σ(v 2 ) = v 5 and σ(v 5 ) = v 2 . 2. Figure 6.3(b): let S = L ∪ {v 3 , v 5 } = {u 1 , u 2 , . . . , u m },
For every vertex u i of S, f

(u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 4 ) = m + 1 and f (v 2 ) = f (v 6 ) = m + 2. σ(v 1 ) = v 4 , σ(v 4 ) = v 1 , σ(v 2 ) = v 6 and σ(v 6 ) = v 2 . 3. Figure 6.3(c): let S = L ∪ {v 2 , v 4 , v 6 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 5 ) = m + 1 and f (v 3 ) = f (v 7 ) = m + 2. σ(v 1 ) = v 5 , σ(v 5 ) = v 1 , σ(v 3 ) = v 7 and σ(v 7 ) = v 3 . 4. Figure 6.3(d): let S = L ∪ {v 2 , v 5 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 4 ) = m + 1, f (v 3 ) = f (v 6 ) = m + 2 . σ(v 1 ) = v 4 , σ(v 4 ) = v 1 , σ(v 3 ) = v 6 and σ(v 6 ) = v 3 . 5. Figure 6.3(e): let S = (L \ {v 1 }) ∪ {v 4 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 3 ) = m + 1 and f (v 2 ) = f (v 5 ) = m + 2. σ(v 1 ) = v 3 , σ(v 3 ) = v 1 , σ(v 2 ) = v 5 and σ(v 5 ) = v 2 . 6. Figure 6.3(f ): let S = L ∪ {v 4 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 3 ) = m + 1 and f (v 2 ) = f (v 5 ) = m + 2. σ(v 1 ) = v 3 , σ(v 3 ) = v 1 , σ(v 2 ) = v 5 , and σ(v 5 ) = v 2 . 7. Figure 6.3(g): let S = (L \ {v 1 , v 5 }) ∪ {v 4 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 3 ) = m + 1 and f (v 2 ) = f (v 5 ) = m + 2. σ(v 1 ) = v 3 , σ(v 3 ) = v 1 ,σ(v 2 ) = v 5 , and σ(v 5 ) = v 2 . 8. Figure 6.3(h): let S = (L \ {v 5 }) ∪ {v 4 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 3 ) = m + 1 and f (v 2 ) = f (v 5 ) = m + 2. σ(v 1 ) = v 3 , σ(v 2 ) = v 5 , σ(v 3 ) = v 1 and σ(v 5 ) = v 2 .
Case 2: C is isomorphic to one of the graphs of Figure 6.4. We can easily check that λ 2 (C) ≤ |I|+⌊ n-|I| 2 ⌋-1. It then suffices to prove that λ 2 (C) ≥ |I|+⌊ n-|I| 2 ⌋-1 for every graph of Figure 6.4.

1. Figure 6.4(a): let S = L \ {v 1 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 2 ) = f (v 3 ) = f (v 4 ) = m + 1. σ(v 1 ) = v 3 , σ(v 2 ) = v 1 , σ(v 3 ) = v 4 and σ(v 4 ) = v 2 . 2. Figure 6.4(b): let S = L{u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 2 ) = f (v 3 ) = f (v 4 ) = m + 1. σ(v 1 ) = v 3 , σ(v 2 ) = v 1 , σ(v 3 ) = v 4 and σ(v 4 ) = v 2 . 3. Figure 6.4(c): let S = (L ∪ {v 1 , v 5 }) ∪ {v 2 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 4 ) = m + 1, f (v 3 ) = f (v 5 ) = m + 2. σ(v 1 ) = v 4 , σ(v 4 ) = v 1 , σ(v 3 ) = v 5 and σ(v 5 ) = v 3 . 4. Figure 6.4(d): let S = (L \ ∪{v 3 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 2 ) = f (v 3 ) = f (v 4 ) = m + 1. σ(v 1 ) = v 3 , σ(v 2 ) = v 1 , σ(v 3 ) = v 4 and σ(v 4 ) = v 2 .
Case 3: C is isomorphic to one of the graphs of Figure 6.5. In this case, we can also check that λ 2 (C)

≤ |I| + ⌊ n-|I| 2 ⌋ -2. It then suffices to prove that λ 2 (T ) ≥ |I| + ⌊ n-|I|
2 ⌋ -2 for every graph of Figure 6.5.

1. Figure 6.5(a):

let S = L \ {v 1 , v 4 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i . f (v 1 ) = f (v 2 ) = f (v 3 ) = f (v 4 ) = m + 1. σ(v 1 ) = v 2 , σ(v 2 ) = v 4 , σ(v 3 ) = v 1 and σ(v 4 ) = v 3 . σ(x) = t, σ(t) = x, σ(y) = v and σ(v) = y.
For every vertex u of degree 1 in T , where u / ∈ {t, v}, σ(u) = u.

For every vertex

u i ∈ U , σ(u i ) = u (i+1) mod m if i is odd , u i-1 otherwise.
From this permutation scheme, we can see that the number of cycles of σ is at least

|X|+⌊ n-|X| 2 ⌋-1
, where X is the set of end-vertices of T . Since for a tree of diameter

4, |X| ≥ ⌊ n-1 2 ⌋, we get |X| + ⌊ n-|X| 2 ⌋ -1 ≥ ⌊ 3n 4 ⌋ -2.
Hence, σ is good permutation of T . The following theorem gives our first lower bound on the labeled embedding number of general trees. Theorem 6.10 Let T = (V, E) be a tree of order n. If T = K 1,n-1 , then there exists an embedding σ of T such that σ is good.

Proof. The proof is done by induction on the number of vertices n. For n = 4, there is only one tree which is not a star, namely P 4 . By Theorem 6.4, we have λ 2 (P 4 ) = 1. Then, our theorem is true for n = 4. Let n ≥ 5 and suppose that the theorem has been proved for all n ′ < n. We shall consider two main cases as follows: Case 1: diam(T ) = 3. We choose a set of vertices X ⊂ V such that T \ X = P 4 . The induction hypothesis guarantees the existence of a good permutation σ ′ on P 4 . We can easily see that σ ′ is fixed-point-free permutation. Then, σ ′ can be extended to a good permutation σ of T as follows: for every vertex x ∈ X, σ(x) = x. Hence σ is a good permutation of T . Case 2: diam(T ) = 4. It follows by Theorem 6.9 that λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. Case 3: diam(T ) ≥ 5. We choose D = (u 1 , u 1 , . . . , u m ) as a diameter of T and we root T at a vertex r / ∈ (V (T u 2 ) ∪ V (T u m-1 )) as shown in Figure 6.7. Two main subcases are considered as follows: Subcase 3.1: d(u 2 ) = 2 or d(u m-1 ) = 2. Wlog, assume that d(u 2 ) = 2. We consider the tree T ′ = T \ (V (T u 2 ) ∪ V (T u m-1 )). We can easily see that if T ′ is a star then T is a caterpillar. Hence we have by Theorem 6.6 that λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. We Suppose now that T ′ = K 1,m-1 , then the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). Let us we consider the following

σ(u 2 ) = x 1 if * holds, u m-1 otherwise. σ(u m-1 ) = u 1 if * holds, u 2 otherwise. σ(x 1 ) = u 2 if * holds, u 1 otherwise. σ(u 1 ) = u m-1 if * holds,
x 1 otherwise. From this permutation scheme, we obtain the following equation:

λ 2 (T ) ≥ λ 2 (T ′ ) + |V (T u 2 )| + |V (T x 1 )| + |V (T u m-1 )| -2.
By hypothesis, we have that λ 2 (T ′ ) ≥ ⌊ 3n ′ 4 ⌋ -2, and thus

λ 2 (T ) ≥ ⌊ 3(n-|V (T u 2 )|-|V (T x 1 )|-|V (T u m-1 )|) 4 ⌋ + |V (T u 2 )| + |V (T x 1 )| + |V (T u m-1 )| -4. Since |V (T u 2 )| + |V (T x 1 )| + |V (T u m-1 )| ≥ 8, we get λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. Hence σ is a good permutation of T . (b) diam(T u 3 ) = 3 or diam(T u m-2 ) = 3.
Wlog, assume that diam(T u 3 ) = 3. We consider the tree T ′ = T \ (V (T u 3 ) ∪ V (T u m-1 )). We can easily see that if T ′ is a star then T is a caterpillar. Hence we have by Theorem 6.6 that λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. We Suppose now that T ′ = K 1,m-1 , then the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). The permutation σ ′ can be extended to a good permutation σ of T as follows:

σ(u 1 ) = u 3 , σ(u 3 ) = u 1 , σ(u 2 ) = u m-1 and σ(u m-1 ) = u 2 . for every vertex v ∈ (V (T u 3 ) ∪ V (T u m-1 )) \ {u 1 , u 2 , u 3 , u m-1 }, σ(v) = v. for every vertex v ∈ V (T ′ ), σ(v) = σ ′ (v).
From this permutation scheme, we obtain the following equation:

λ 2 (T ) ≥ λ 2 (T ′ ) + |V (T u 3 )| + |V (T u m-1 )| -2.
By hypothesis, we have that

λ 2 (T ′ ) ≥ ⌊ 3n ′ 4 ⌋ -2 and thus λ 2 (T ) ≥ ⌊ 3(n-|V (T u 3 )|-|V (T u m-1 )|) 4 ⌋ + |V (T u 3 )| + |V (T u m-1 )| -4. Since |V (T u 3 )| + |V (T u m-1 )| ≥ 8, we get λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. Hence σ is a good permutation of T . (c) diam(T u 3 ) = 2 and diam(T u m-2 ) = 2. Consider the tree T ′ = T \ (V (T u 2 ) ∪ V (T u m-1 )).
We can easily see that if T ′ is a star then T is a caterpillar. Hence we have by Theorem 6.6 that λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. We Suppose now that T ′ = K 1,m-1 , then the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). Since u 2 and u m-1 are two end-vertices in T ′ , we get by the property (4) of σ ′ that σ ′ (u 2 ) = u m-1 and σ ′ (u m-1 ) = u 2 . Then, the permutation σ ′ can be extended to a good permutation σ of T as follows:

σ(u 2 ) = u m-1 and σ(u m-1 ) = u 2 . for every vertex v ∈ (V (T u 2 ) ∪ V (T u m-1 )) \ {u 2 , u m-1 }, σ(v) = v. for every vertex v ∈ V (T ′ ), σ(v) = σ ′ (v).
From this permutation scheme, we obtain the following equation:

λ 2 (T ) ≥ λ 2 (T ′ ) + |V (T u 2 )| + |V (T u m-1 )| -1.
By hypothesis, we have that

λ 2 (T ′ ) ≥ ⌊ 3n ′ 4 ⌋ -2 and thus λ 2 (T ) ≥ ⌊ 3(n-|V (T u 2 )|-|V (T u m-1 )| 4 ⌋ + |V (T u 2 )| + |V (T u m-1 )| -3. Since |V (T u 2 )| + |V (T u m-1 )| ≥ 6, we get λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. So σ is a good permutation of T .
We now give a second lower bound on λ 2 (T ) that depends on the number of endvertices of T . Theorem 6.11 Let T be a tree of order n and let X be the set of end-vertices of

T . If T \ X = K 1,n-1 , then λ 2 (T ) ≥ |X| + ⌊ n -|X| 2 ⌋ -1.
We can clearly see that Theorem 6.11 can be proved as a consequence of Lemma 6.2 and the following theorem.

Theorem 6.12 Let T = (V, E) be a non star tree of order n, then

α 2 (T ) ≥ ⌊ n 2 ⌋ -1.
In the following, a permutation σ of V (T ) will be called good for T if and only if:

1. σ is an fixed-point-free embedding of T .

2. σ has at least ⌊ n 2 ⌋ -1 cycles.

Using the same proof technique as in Theorem 6.9, we can show the following: Theorem 6.13 Let T be a tree of order n and diameter 4, then

α 2 (T ) ≥ ⌊ n 2 ⌋ -1.
Proof of Theorem 6.12. The proof is done by induction on the number of vertices n. The theorem is true for n = 4, 5. Let n ≥ 6 and suppose that the theorem has been proved for all n ′ < n. We shall consider four main cases as follows:

Case 1: diam(T ) = 3. We use the notation of Figure 6.9 which represents a double star with two non leaf vertices. Three subcases are considered as follows:

Subcase 1: d(v 2 ) ≥ 4 or d(v 3 ) ≥ 4. Wlog, assume that d(v 2 ) ≥ 4.
Then, let x 1 and x 2 be two end-vertices adjacent to v 2 . Consider the tree T ′ = T \ {x 1 , x 2 }. Thus, the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). This permutation can be extended to a good permutation σ of T as

v 4 v 2 v 1 v 3 x 1 x p y 1 y q
x 2 y 2 Figure 6.9: A double star notation.

follows:

σ(x 1 ) = x 2 , σ(x 2 ) = x 1 and for every vertex v ∈ V (T ′ ), σ(v) = σ ′ (v).
Subcase 2: d(v 2 ) = 3 and d(v 3 ) = 3. We consider the tree

T ′ = T \ {x 1 , y 1 } = P 4 .
We know that there exists a good permutation σ ′ on V (T ′ ) such that σ(v 2 ) = v 3 and σ(v 3 ) = v 2 . This permutation can be extended to a good permutation σ of T as follows: σ(x 1 ) = y 1 , σ(y 1 ) = x 1 and for every vertex

v ∈ V (T ′ ), σ(v) = σ ′ (v).
Case 2: diam(T ) = 4. It follows by Theorem 6.13 that α 2 (T ) ≥ ⌊ n 2 ⌋ -1. Case 3: diam(T ) ≥ 5. Two subcases are considered as follows: Subcase 3.1: there exists a vertex v in T such that v is adjacent to at least two end vertices of T . Let x and y be two end vertices of T which is adjacent to v. Consider the tree T ′ = T \ {x, y}. Thus, the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). This permutation can be extended to a good permutation σ of T as follows: σ(x) = y and σ(y) = x. Hence σ is a good permutation of T . Subcase 3.2: For every vertex v of T , v is adjacent is adjacent to at most one end vertex of T . We choose D = (u 1 , u 1 , . . . , u m ) as a diameter of T and we root T at a vertex r / ∈ (V (T u 2 ) ∪ V (T u m-1 )). Three cases are considered according to whether diam(T u 3 ) = 4, 3 or 2. (a): diam(T u 3 ) = 4. The vertex u 3 has at least two children vertices of degree 2 (see Figure 6.10). Consider the tree T ′ = T \ {x 1 , y 1 , x 2 , y 2 , u m-1 , u m }. Suppose that

x 1 u 3 u 2 u 1 y 1 x 2 y 2 x p y p Figure 6.10: T u 3 T ′ = K 1,m-1
, the case where T ′ = K 1,m-1 is left to the reader. Thus, the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). This permutation can be extended to a good permutation σ of T as follows:

σ(x 1 ) = x 2 , σ(x 2 ) = x 1 , σ(y 1 ) = u m , σ(u m ) = y 1 , σ(y 2 ) = u m-1 , σ(u m-1 ) = y 2 and for every vertex v ∈ V (T ′ ), σ(v) = σ ′ (v).
Hence σ is a good permutation of T . (b): diam(T u 3 ) = 3. In this case, the vertex u 3 is adjacent to two children vertices: an internal vertex u 2 and an end vertex x. Consider the tree T ′ = T \{u 1 , u 2 , x, u m }. Suppose that T ′ = K 1,m-1 , the case where T ′ = K 1,m-1 is left to the reader. Thus, the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). This permutation can be extended to a good permutation σ of T as follows:

σ(u 1 ) = u m , σ(u m ) = u 1 , σ(x) = u 2 , σ(u 2 ) = x and for every vertex v ∈ V (T ′ ), σ(v) = σ ′ (v).
Hence σ is a good permutation of T . (c): diam(T u 3 ) = 2. Consider the tree T ′ = T \ {u 1 , u 2 , u 3 , u m }. Suppose that T ′ = K 1,m-1 , the case where T ′ = K 1,m-1 is left to the reader. Thus, the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). This permutation can be extended to a good permutation σ of T as follows:

σ(u 1 ) = u 3 , σ(u 3 ) = u 1 , σ(u 2 ) = u m , σ(u m ) = u 2 and for every vertex v ∈ V (T ′ ), σ(v) = σ ′ (v).
Hence σ is a good permutation of T .

Labeled embedding of (n, n -2) graphs

In this section, a permutation σ on V (G) is said to be a good permutation for G if σ is an embedding of G and the number of its cycle is at least ⌊ 2n 3 ⌋. So we will prove that if |E(G)| ≤ n -2 then there exists a good permutation for G. More formally, we have to prove that.

Theorem 6.14 Let G be a (n, n -2) graph, then λ 2 (G) ≥ ⌊ 2n 3 ⌋.
Proof. The proof is by induction on n. Without loss of generality, we can assume that |E(G)| = n -2, the theorem is true for n = 3, 4, 5. Assume it is true for every graph of order n ′ < n, where n ′ ≥ 6. The components of G must include at least two non-trivial trees T and H. Let D 1 = (x 1 , x 2 , . . . , x p-1 , x p ) and D 2 = (y 1 , y 2 , . . . , y q-1 , y q ) be the diameter of T and H, respectively. We root T and H at the leaves x p and y q , respectively. We shall consider four main cases as follows:

Case 1: p, q ≥ 4. We consider three subcases as follows:

Subcase 1.1: d(x 2 ) = 2 or d(y 2 ) = 2. Wlog, assume that d(x 2 ) = 2. Consider the graph G ′ = G \ (V (T x 2 ) ∪ V (Hy 2 ))
. So the induction hypothesis guarantees the existence of a good permutation σ ′ on V (G ′ ). The permutation σ ′ can be extended to a good permutation σ of G as follows:

for every vertex v ∈ (V (T x 2 ) ∪ V (Hy 2 )) \ {x 1 , x 2 , y 2 }, σ(v) = v. For every vertex v ∈ V (G ′ ), σ(v) = σ ′ (v). σ(x 2 ) = x 2 if σ ′ (x 3 ) = y 3 , y 2 otherwise. σ(y 2 ) = x 1 if σ ′ (x 3 ) = y 3 , x 2 otherwise. σ(x 1 ) = y 2 if σ ′ (x 3 ) = y 3 ,
x 1 otherwise. From this permutation scheme, we obtain the following equation:

λ 2 (G) ≥ λ 2 (G ′ ) + |V (T x 2 )| + |V (Hy 2 )| -1. By hypothesis, we have that λ 2 (G ′ ) ≥ ⌊ 2n ′ 3 ⌋, then λ 2 (G) ≥ ⌊ 2(n-|V (T x 2 )|-|V (Hy 2 )|) 3 ⌋ + |V (T x 2 )| + |V (Hy 2 )| -1.
6.3. Labeled embedding of (n, n -2) graphs 85 By hypothesis, we have that

|V (T x 2 )| + |V (Hy 2 )| ≥ 4, hence λ 2 (G) ≥ ⌊ 2n 3 ⌋. So σ is a good permutation of G.
Subcase 1.2: d(x 2 ) ≥ 3 and d(y 2 ) ≥ 3. Three cases are considered as follows: (a) diam(x 3 ) = 4 or diam(y 3 ) = 4. Wlog, assume that diam(T x 2 ) = 4 (see Figure 6.11). Consider the graph G ′ = G \ (V (T x 2 ) ∪ V (T z 1 ) ∪ V (Hy 2 )). So the induction hypothesis guarantees the existence of a good permutation σ ′ on V (G ′ ). The permutation σ ′ can be extended to a good permutation σ of G as follows:

for every vertex v ∈ (V (T x 2 ) ∪ V (T z 1 ) ∪ V (Hy 2 )) \ {x 1 , x 2 , z 1 , y 2 }, σ(v) = v. For every vertex v ∈ V (G ′ ), σ(v) = σ ′ (v). σ(x 2 ) = z 1 if σ ′ (x 3 ) = y 3 , y 2 otherwise. σ(y 2 ) = x 1 if σ ′ (x 3 ) = y 3 , x 2 otherwise. σ(x 1 ) = y 2 if σ ′ (x 3 ) = y 3 , z 1 otherwise. σ(z 1 ) = x 2 if σ ′ (x 3 ) = y 3 ,
x 1 otherwise. From this permutation scheme, we obtain the following equation:

λ 2 (G) ≥ λ 2 (G ′ ) + |V (T x 2 )| + |V (T z 1 )| + |V (Hy 2 )| -2. By hypothesis, we have that λ 2 (G ′ ) ≥ ⌊ 2n ′ 3 ⌋, then λ 2 (G) ≥ ⌊ 2(n-|V (T x 2 )|-|V (T z 1 )|-|V (Hy 2 )|) 3 ⌋ + |V (T x 2 )| + |V (T z 1 )| + |V (Hy 2 )| -2. By hypothesis, we have that |V (T x 2 )| + |V (T z 1 )| + |V (Hy 2 )| ≥ 8, hence λ 2 (G) ≥ ⌊ 2n 3 ⌋. So σ is a good permutation of G. x 3 x 2 x 1 z 1 z p Figure 6.11: T x 3 . (b) diam(x 3 ) = 3 or diam(y 3 ) = 3. Wlog, assume that diam(T x 2 ) = 3. Consider the graph G ′ = G \ (V (T x 3 ) ∪ V (Hy 2 ))
. So the induction hypothesis guarantees the existence of a good permutation σ ′ on V (G ′ ). The permutation σ ′ can be extended to a good permutation σ of G as follows:

σ(x 1 ) = x 3 , σ(x 3 ) = x 1 , σ(x 2 ) = y 2 and σ(y 2 ) = x 2 . for every vertex v ∈ (V (T x 3 ) ∪ V (Hy 2 )) \ {x 1 , x 2 , x 3 , y 2 }, σ(v) = v. for every vertex v ∈ V (G ′ ), σ(v) = σ ′ (v).
From this permutation scheme, we obtain the following equation:

λ 2 (G) ≥ λ 2 (G ′ ) + |V (T x 3 )| + |V (Hy 2 )| -2.
By hypothesis, we have that

λ 2 (G ′ ) ≥ ⌊ 2n ′ 3 ⌋, then λ 2 (T ) ≥ ⌊ 2(n-|V (T x 3 )|-|V (Hy 2 )|) 3 ⌋ + |V (T x 3 )| + |V (Hy 2 )| -2. By hypothesis, we have that |V (T x 3 )| + |V (Hy 2 )| ≥ 8, hence λ 2 (G) ≥ ⌊ 2n 3 ⌋. So σ
Case 4: all previous cases are not satisfied. In this case G contains only isolated vertices (at least two) and non-tree components. Two subcases are considered as follows:

Subcase 4.1: G has a vertex x of degree at least 3. Let u, v be two isolated vertices of G. Consider the graph G ′ = G \ {u, v, x}). Then there exists a good permutation for G ′ , say

σ ′ . Putting σ(u) = u, σ(v) = x, σ(x) = v and for y ∈ V (G ′ ), σ(y) = σ ′ (y)
we get a good permutaion for G.

Subcase 4.2: all the components of G are cycles and isolated vertices. In this case we can easily show that G has a good permutation.

From the proof above, we can conclude that λ 2 (G) ≥ ⌊ 2n 3 ⌋.

To improve Theorem 6.14, we propose the following conjecture which is probably true but it seems difficult to prove it!

Conjecture 6.15 Let G be a graph of order n, if |E(G)| ≤ n -2, then λ 2 (G) ≥ ⌊ 3n 4 ⌋ -2

Conclusion

In this chapter, we have studied the labeled embedding of trees and (n, n-2) graphs.

In particular, we have proved the exact value of the labeled embedding number of paths and caterpillars. We have also shown the interest to study the fixed-point-free labeled embedding in order to improve the lower bound of the labeled embedding number of general trees and (n, n -2) graphs. We end this part by reflecting on the applicability of labeled packing to the graph matching problem. If we consider the example of XML documents that are modeled as ordered labeled trees, we can see that querying an XML document is equivalent to searching an embedding of the query in the data tree. Therefore, it would be interesting to exploit tree embedding techniques in order to define a coherent similarity measure between two labeled trees. The XML pattern matching is the subject of the next part of this thesis.

Part III

XML Tree Pattern Matching Problem

Chapter 7

Tree Matching and XML Retrieval Among all the available formats used to represent information (from text to video or audio), the XML (eXtensible Markup Language) [W3C98b] format is now extensively used. The simple, self-description nature of the XML standard promises to enable a broad suite of next-generation Internet applications, ranging from intelligence Web searching and querying to e-commerce.

The growing number of XML documents leads to the need for appropriate retrieval methods which are able to exploit the specific features of this type of documents. Indeed, in XML documents, textual content (data) is hierarchically structured with tags. As opposed to other markup languages (like HTML for example), tags are used to specify semantic information about the content, and not for presentation purposes. Although structure allows to organize content in XML documents, it is not always used with the same intent. XML documents can be either data-oriented, where structure is intensively used to organize data, and where XML components can be seen as database records, or text-oriented, where structure is irregular and documents are designed to be used by humans.

Many approaches have been proposed in the literature for XML retrieval. However, most of them propose ab nihilo solutions, whereas the use of graph theoretical concepts could be of interest. Indeed, the underlying data model of XML documents allows to consider them as a particular kind of graphs, i.e., trees [W3C98a]. More precisely, they can be considered as labeled trees of element nodes, where each element can be either an atomic data item or a composite data collection consisting of references (represented as edges) to child elements in the XML tree. The same representation can be used for structured queries. Considering this data model for retrieval, the retrieval process can thus be seen as a matching problem between query and document trees.

In this chapter, we aim at studying and discussing what are the solutions proposed by graph theory for the tree-matching problem in a general perspective, and how they have been exploited in XML retrieval. In particular, we will focus our attention on the exact tree matching problem.

Querying XML Data: Key points

Before giving some algorithms used in graph theory for tree matching, it seems of great importance to recall some background about XML documents and query languages, and to detail issues behind the retrieval of XML information.

Tree representation of XML documents

In XML documents, tags are used to hierarchically and semantically organize information. In the document presented in Figure 7.1 for example, content is organized within a header and a body tag. The body tag contains section elements, which are in turn composed of title and paragraph elements, etc.

An element begins with an opening tag <tag> and ends with a closing tag </tag>. It may contain atomic data (as for example author element), other elements (as for example one of the section elements) or a mixture of both (one talk about mixed content). Elements are also called components.

Thanks to this data model, XML documents can be represented as labeled trees [W3C98a]. In an XML tree, the whole document is represented by the root node, elements are represented by internal nodes (i.e., non terminal nodes) and the content itself is in leaf nodes (i.e., terminal nodes). These nodes are linked with edges showing their hierarchical relations. The tree representation of the document in Figure 7.1 is given in Figure 7.2.

As previously mentioned, XML documents can be classified into two groups of documents: data-oriented documents or text-oriented documents Documents of the first category have a fine granularity, are highly structured and do not contain mixed contents. The order of the children of a given element is often without any importance. Elements can be considered as database records, there are On the other hand, text-oriented documents are loosely structured. They are designed to be used by humans; books, articles, electronic messages are good examples of this type of documents. Their structure is irregular, and they can contain many mixed contents. Moreover, the order of elements is very paramount for the understanding of documents. For example, in the text-oriented document of Figure 7.1, section elements should be read in the good order to make the whole article Boundaries between the two types of approaches are however nowadays not so strict. As explained by Lalmas and Baeza-Yates in [START_REF] Lalmas | Structured document retrieval[END_REF]: "From a terminology point of view, structured text retrieval and querying semi-structured data, in terms of end goals, are the same, i.e., finding elements answering a given query. The difference comes from the fact that in information retrieval, the structure is added, and in databases, the structure is loosened."

In the following, we will thus present only approaches from the database community (exact tree matching, section 7.3). Whatever the considered approach, the problem is to match a document tree with a query tree. The following paragraph presents the different query languages proposed in the literature for XML retrieval.

Query languages

Queries for XML retrieval can be classified into content-only and content-andstructure queries.

Content-only queries are composed of simple keywords terms, and have historically been used in traditional information retrieval. They are also suitable for XML retrieval, in retrieval scenarios where the user does not know the structure of documents he/she is querying. In this thesis, we are not interested in such queries, since open issues when considering this type of queries are different. Indeed, with content-only queries, the main problem is to find the good granularity of information to be returned to users, and not to match documents and queries trees.

In content and structure queries, users provide content conditions linked with structure conditions. They are two reasons a user might add structural constraints to a query [START_REF] Trotman | Processing structural constraints[END_REF]:

• the first is to constraint the size of the result,

• the second is to restrict the search to document parts that are supposed to be appropriate.

According to [START_REF] Amer-Yahia | XML search: languages, INEX and scoring[END_REF], there are three main categories of content and structure query languages:

• tag-based queries allow users to express very simple conditions concerning the tag of the element in which the required content should be. They are of the form: "tag: content condition". For example the query "section: search engines" means that the user is looking for a section element about "search engines".

• path-based queries are based on the XPath [W3C07b] syntax. They include content conditions in a XPath-based syntax. Examples of languages allowing path-based queries are the NEXI language [START_REF] Trotman | Narrowed EXtended Xpath I (NEXI)[END_REF] or FuzzyXPath [CDG + 09].

• clause-based queries have a structure similar to the one of SQL. They contain nested clauses that allow to express the used need. In XML retrieval, one can cite XQuery [W3C07a] or XQuery full-text [W3C11] as examples for clausebased queries.

If we now purely consider the structure conditions of queries, XQuery and XPath [W3C07a], [W3C07b] queries can be basically divided into two main groups: path queries and twig queries. Path queries are simple queries against XML document, which contain path expressions, i.e., child axis "/" and descendant axis "//". Twig queries are represented as node-labeled twig patterns, i.e., small trees. They are also named tree pattern queries.

An example of a twig query is represented in Figure 7.4.

Figure 7.4: A twig query

Whatever the query language used, content and structure queries, in the same manner than XML documents, can be represented as labeled trees. The retrieval process can thus be summarized to a tree matching process. In the following section, we give a short survey for exact tree matching problem. For more information about approximate tree matching we refer to our survey paper [TPSN + 12], which was submitted to ACM Computing Surveys.

Algorithms for exact tree pattern matching

This section describes state-of-the-art algorithms for exact tree matching. In order to state the problem, the terminology of labeled tree and their components has to be defined first.

Notation and terminology

A rooted labeled tree is denoted by T = (V, E, r, µ), where

V = {v 1 , v 2 , . . . , v n } is a finite set of nodes, E ⊆ {(u, v)|u, v ∈ V } is a set of edges.
The node r is a distinguished node called the root, and µ is a labeling function which maps each node of T to a label in a finite set L = {l 1 , l 2 , ..., l k }. For brevity, in the remaining of this chapter, we call a rooted labeled tree simply a tree. We denote the level of a vertex v by l(v). We recall that an ordered tree is a rooted tree for which an ordering is specified for the children of every node, and it is unordered otherwise.

We give below the formal definition of the exact tree matching problem.

Definition 7.1 Let target T 1 = (V 1 , E 1 , r 1 , µ 1
) and pattern T 2 = (V 2 , E 2 , r 2 , µ 2 ) be two ordered labeled trees. T 2 matches T 1 at node x 1 = r 1 if there exists a one-to-one injective function from the nodes of T 2 into the nodes of T 1 such that:

1. the root of T 2 maps to x 1 , 2. if v 2 ∈ V 2 maps to v 1 ∈ V 1 , then µ 1 (v 1 ) = µ 2 (v 2 ), 3. if v 2 ∈ V 2 maps to v 1 ∈ V 1
and v 1 is not a leaf, then each child of v 2 maps to some child of v 1 .

Figure 7.5 shows an example of a tree pattern matching between pattern tree P and target tree T , where the one-to-one mappings is represented by dotted lines. The tree pattern matching problem has been largely studied and has many important applications such as term rewriting systems, transformational programming systems, code-generator generators, theorem provers, and a variety of functional languages with equational function definitions (see [START_REF] Hoffman | Pattern matching in trees[END_REF]). The following is a brief overview of general exact tree pattern matching algorithms.

Algorithms

Given a tree pattern P and a target T of order m and n, respectively, where m ≤ n, a naive tree pattern matching algorithm takes O(mn) in the worst case. The basic idea is to visit all nodes of T in a pre-order walk, for each visited node a special recursive procedure is applied to check for possible occurrence of P at that node v. The matching procedure is terminated as soon as a mismatch is detected. Several attempts were made to improve the naive O(mn) steps algorithm. Hoffmann and O'Donnell [START_REF] Hoffman | Pattern matching in trees[END_REF] proposed two approaches, called bottom-up and topdown matching algorithms with the same worst case bound. Top-down algorithm is efficient in space, but matching time is non-linear. The main idea of this algorithm is to encode the root-to-leaf paths as strings. It then finds all occurrences of each string in the target tree according to the string pattern matching algorithm of Aho and Crasick [START_REF] Aho | Efficient string matching: An aid to bibliographic search[END_REF]. On the contrary, the key idea of the bottom-up technique is to find, for each node in the target tree, all patterns and all parts of patterns that match this node. Bottom-up techniques achieve matching in linear time. However, auxiliary space is required to store and establish the table encoding of all nodes in the target tree.

Hoffmann and O'Donnell's work stimulated a number of additional studies offering heuristic for space improvements. Among these improvements, we can mention the following significant approaches: [START_REF] Chase | An improvement to bottom-up tree pattern matching[END_REF], [START_REF] Burghardt | A tree pattern matching algorithm with reasonable space requirements[END_REF], [START_REF] Kosaraju | Efficient tree pattern matching[END_REF], [START_REF] Dubiner | Faster tree pattern matching[END_REF], [START_REF] Cole | Tree pattern matching and subset matching in randomized o(nlog 3 m) time[END_REF] and [START_REF] Cole | Tree pattern matching to subset matching in linear time[END_REF]. Chase's method [START_REF] Chase | An improvement to bottom-up tree pattern matching[END_REF] received considerable attention in the literature. This method was able to improve bottom-up solutions presented by Hoffmann and O'Donnell by exploiting the deeper structure of the pattern P to avoid some useless operations of the bottom-up algorithm. Chase proved that this transition map utilizes space much better than Hoffmann and O'Donnells. In [START_REF] Burghardt | A tree pattern matching algorithm with reasonable space requirements[END_REF], Burghardt proposed a tree pattern algorithm, which consists of two phases. In the first phase a matching automaton is built from a given pattern set. For this, it generalizes the string matching algorithm of Aho and Corasick [START_REF] Aho | Efficient string matching: An aid to bibliographic search[END_REF] such that each pattern is linearized according to the position ordering relation. Then these pattern strings are merged into an automaton by sharing as long initial parts as possible. In the second phase, one or more target trees are put into the automaton, by walking through the automaton graph according to the target tree and collecting the match information.

Kosaraju [START_REF] Kosaraju | Efficient tree pattern matching[END_REF] gave a new algorithm with improved complexity bound from O(nm) to (nm

Exact tree pattern matching for XML retrieval

As we have seen in Section 7.1, XML uses a tree-structured model for representing data and twig patterns for expressing queries. Finding all occurrences of such a twig pattern in an XML database is clearly a core operation in XML query processing. There has been a great deal of interest in recent years to overcome efficiently this problem. Most of the proposed approaches in the literature are interested in structural properties of queries and can be classified into four groups:

• structural join approaches,

• holistic twig join approaches,

• sequence matching approaches,

• other important exact XML tree matching algorithms.

In the following, we present an overview of the main algorithms and results available in each group.

Structural join approaches

In this section, we review the join based approach, a very important native idea, which usually includes three parts: (1) decomposition, (2) matching and (3) merging. Firstly, a twig pattern is decomposed into a set of basic parent-child and ancestor-descendant relationships between pairs of nodes. In the second phase, each binary relationship is separately executed using structural join techniques and its intermediate results are stored for further processing. The final result is formed by merging the intermediate results. We describe in the following the two main structural join algorithms proposed in the literature.

(i) Multi-predicate merge join algorithm

The key to the efficiency of this algorithm is in the use of a containment labeling scheme [ZND + 01] that encodes each element in an XML database by its positional information. The main purpose of this representation is that the structural relationship between two vertices u, v can be determined easily without knowledge of the intermediate nodes on the path between u, v. For more information, this labeling scheme (called also region encoding) will be described in detail in the next chapter.

Based on the containment labeling scheme, Zhang et al. [ZND + 01] proposed the multi-predicate merge join (MPMGJN ) algorithm, which is the first structural join to find all occurrences of the basic structural relationships. This mechanism is an extension of the classical merge-join algorithm developed in relational query optimizers for equi-joins. The results of Zhang showed that for many XML queries, MPMGJN is more than an order-of-magnitude faster than the standard Relational Database Management System (RDBMS) join implementations. The behavior of these two algorithms is explained by analytical results. In particular, the Stack-Tree algorithm was shown to be both I/O and CPU optimal, and practically as efficient as Tree-Merge family for evaluating containment queries.

Holistic twig join approaches

Until now, the holistic twig join approach was regarded as the most efficient family in the literature. Bruno et al. [START_REF] Bruno | Holistic twig joins: optimal XML pattern matching[END_REF] proposed the first holistic XML twig pattern matching algorithm to avoid producing large intermediate results. This approach constituted the major attempt for several subsequent works in order to make the twig pattern matching very efficient. In the following, we present an overview of the basic ideas and results of the main holistic twig join algorithms available in the literature.

(i) TwigStack algorithm

The main disadvantage of twig query decomposition into multiple binary relationships is that this approach generates a large amount of intermediate query results even when the input and output size are more manageable. Frequently, such intermediate results cannot be held in main memory and must be stored on disk. This will result in high disk I/O cost. In order to overcome this weakness, Bruno et al. [START_REF] Bruno | Holistic twig joins: optimal XML pattern matching[END_REF] proposed a novel holistic twig join algorithm, called TwigStack, wherein no large intermediate results are created.

The idea behind this approach is to use a chain of linked stacks to compactly represent partial results of individual query root-to-leaf paths, which are then composed to produce the final solutions. This decomposition method avoids computing large redundant intermediate results. This algorithm will be described in detail in the next chapter. The main advantage of this approach is to avoid storing intermediate results unless they contribute to the final results when the query twig has only ancestor-descendant edges. The analytical results of this approach demonstrate that TwigStack is I/O and CPU optimal among all sequential algorithms that read the entire input. This analysis is confirmed by experimental results on a range of real synthetic data and query twig patterns. The experimental results suggest that the holistic approach has more than six-fold faster query processing performance than the Stack-Tree approach coupled with the optimal join order.

(ii) Improvements on TwigStack

The idea of holistic twig join has been adopted in several works in order to make the structural join algorithm very efficient. This section is devoted to a structured review of these advances.

Improvement 1: efficient processing of parent-child edge query. As mentioned before, when all edges in query patterns are ancestor-descendant queries, TwigStack ensures that each root-to-leaf intermediate solution contributes to the final results. However, this algorithm still cannot control a large number of intermediate results for parent-child edge query. In the first improvement attempt, many efficient algorithms for XML twig pattern have been proposed to efficiently handle twig queries with parent-child relationships. Among them, Lu et al. [START_REF] Lu | Efficient processing of XML twig patterns with parent child edges: a look-ahead approach[END_REF] extended TwigStack by proposing TwigStackList algorithm. This algorithm has the same performance than TwigStack for query patterns with only ancestor-descendant edges, but also produces much less useless intermediate solutions than TwigStack for queries with parent-child relationships. The main technique of TwigStackList algorithm is to look-ahead read more elements in the input streams and saves some of them (only those that might contribute to final answers) into lists in the main memory, so that we can make a more accurate decision to determine whether an element can contribute to the final solution or not. The experimental results obtained by authors demonstrate the significant superiority of TwigStackList on TwigStack according to the size of intermediate results for queries with parent-child edges. Chen et al. [START_REF] Chen | On boosting holism in XML twig pattern matching using structural indexing techniques[END_REF] suggested another algorithm, called iTwigJoin, which can be used on various data streaming strategies (e.g. Tag+Level Streaming and Prefix Path Streaming). Tag+Level streaming can be optimal for both ancestor-descendant and parent-child only twig patterns whereas Prefix Path streaming could be optimal for ancestor-descendant only, parent-child relationship only. The experiments in [START_REF] Chen | On boosting holism in XML twig pattern matching using structural indexing techniques[END_REF] show that Tag+Level streaming guarantees very few useless intermediate solutions in most case tested. None of the previous algorithms can avoid useless intermediate solutions completely. Li and Wang [START_REF] Li | Twigbuffer: avoiding useless intermediate solutions completely in twig joins[END_REF] proposed the first algorithm, called TwigBuffer that completely avoids the useless partial solutions for arbitrary twig patterns. TwigBuffer use the same idea of buffering like TwigStackList to buffers some elements from the input streams in order to check the parent-child relationships. The experimental results show that TwigStackList and TwigBuffer have the same performance when the queries that do not have parent-child edges or parent-child edges happen under non-branching nodes. However TwigBuffer performs better than TwigStackList when the queries have parent-child edges under branching nodes.

Improvement 2: elimination of redundant computations. The existing holistic twig join algorithms may perform many redundant checks of XML elements. Indeed, an improvement strategy consists in avoiding these unnecessary computations. TSGeneric+ [START_REF] Jiang | Holistic twig joins on indexed XML documents[END_REF] makes improvements on TwigStack by using XR-Tree to effectively skip some useless elements that do not contribute to the final results. The motivation to use XR-tree is that, the ancestors (or descendants) of any XML element indexed by an XR-tree can be derived with optimal worst case I/O cost. However, TSGeneric+ may still output many useless intermediate path solutions like TwigStack for queries with parent-child relationship. Guoliang et al. [START_REF] Li | Efficient holistic twig joins in leaf-to-root combining with root-to-leaf way[END_REF] proposed the TJEssential algorithm based on three optimization rules to avoid some unnecessary computations. They presented two algorithms incorporated with these optimization rules to effectively answer twig patterns in leaf-to-root combining with root-to-leaf way. A novel holistic twig join algorithm, called TwigStack+ is proposed in [START_REF] Zhou | Twigstack+: Holistic twig join pruning using extended solution extension[END_REF], it is based on holistic twig join guided by extended solution extension to avoid many redundant computations. It significantly improves the query processing cost, simply because it can check whether other elements can be processed together with current one.

Improvement 3: eliminate the merging phase. Another improvement consists in reducing the cost of queries execution. Indeed there exist very interesting approaches that eliminate the second phase of merging of individual solutions [CLT + 06], [START_REF] Qin | Twiglist: make twig pattern matching fast[END_REF], [JLH + 07], [START_REF] Li | Fast matching of twig patterns[END_REF]. However, these algorithms need to load the entire document tree in memory. Chen et al. [CLT + 06] proposed the first tree pattern solution, called Twig2Stack that avoids any post path join. Twig2Stack algorithm uses a hierarchical-stack to capture the ancestor-descendant relationships for the elements in the same query node. In this way, Twig2Stack can process path matching efficiently without a redundant relationships checking. Twig2Stack algorithm has shown a better performance in query processing than TwigStack and TJ-Fast [START_REF] Lu | From region encoding to extended Dewey: On efficient processing of XML twig pattern matching[END_REF] (see below). However, maintaining the hierarchical structure among stacks in Twig2Stack algorithm has a critical impact on the performance processing of twig query. Aiming to avoid this complex hierarchical-stacks, Qin et al. [START_REF] Qin | Twiglist: make twig pattern matching fast[END_REF] proposed an algorithm, called TwigList, which is a refined version of Twig2Stack. In fact, the main difference between both methods is that TwigList has only changed the complicated stacks used in Twig2Stack to simple list structures. The experimental studies of Qin et al. [START_REF] Qin | Twiglist: make twig pattern matching fast[END_REF] show that TwigList algorithm outperforms Twig2Stack as well as TwigStack. In the same context a novel algorithm, called HolisticTwigStack was developed in [JLH + 07]. The authors proposed a novel complex stack structure like Twig2Stack to preserve the holisticity of the twig matches, without generating intermediate solutions. However, a considerable amount of time is taken to maintain the stack structure. HolisticTwigStack were evaluated better than both TwigStack and Twig2Stack in terms of time complexity, memory space and I/O. complexity. Dao and Gao [START_REF] Dao | A glance on current XML twig pattern matching algorithms[END_REF] reviewed and analyzed both of the Holis-ticTwigStack and TwigList algorithm on processing for XML twig pattern matching. The statistics from this analysis clearly indicate that the TwigList algorithm seems to be significantly more efficient in the most tested cases.

Improvement 4: benefit the properties of some labeling schemes. Most of the existing holistic twig join algorithms are based on region encoding scheme (which will be explained in detail in the following chapter) to capture the structural relationship between XML elements. However, there exist other approaches which exploit others labeling scheme. Among them, Dewey labeling scheme has been widely used in XML query processing. A Dewey label of a node v represents the path from the document root to v. Based on the Dewey labeling, Lu et al. [START_REF] Lu | From region encoding to extended Dewey: On efficient processing of XML twig pattern matching[END_REF] proposed TJFast algorithm which uses a new encoding scheme, called the extended Dewey code, which allows to combine effectively the types and identifiers of elements in a label. The main advantage of this labeling is that, the ancestors of any XML element can be derived from its label alone. Thus, TJFast typically access much less elements than algorithms based on region encoding and can efficiently process queries with wildcards in internal nodes. More recently, based on the preliminary idea of extended Dewey labeling scheme and TJFast algorithm, Lu et al. [START_REF] Lu | Indexing and querying XML using extended dewey labeling scheme[END_REF] proposed three novel holistic twig join algorithms GTJFast, TJFastTL and GTJFastTL. The first algorithm GTJFast allows to compactly represent the intermediate matching solutions and avoid the output of non-return nodes to reduce the I/O cost. Both TJFastTL and GTJFastTL algorithms are proposed by extending TJFast and GTJFast algorithm based on tag +level streaming scheme. In tag +level streaming, XML elements with the same label but different level numbers have been separated to different streams. This level information is used to prune some useless streams. The authors proved that TJFastTL and GTJFastTL guarantee the I/O optimality for queries with only parent-child relationships. The experimental results reported in [START_REF] Lu | Indexing and querying XML using extended dewey labeling scheme[END_REF] show that these algorithms are superior to existing approaches in terms of the number of scanned elements, the size of intermediate solutions and query performance.

Sequence matching approaches

As opposed to the holistic twig join algorithm, the sequence matching approaches use an indexing method to transform both XML documents and queries into sequences and evaluate queries based on sequence matching. Querying XML data is equivalent to find subsequence matches. In [START_REF] Zezula | Tree signatures and unordered XML pattern matching[END_REF] and [START_REF] Zezula | Tree signatures for XML querying and navigation[END_REF], the authors use the pre-order and post-order ranks to linearize the tree structures and apply the sequence inclusion algorithms for strings. They proposed a novel strategy that include three parts. Firstly, a query decomposition process is applied to transform pressions are not directly executed on the XML document, but they first evaluated against a guidance structure, called QueryGuide. The information extracted from the QueryGuide is an abstraction of the XML document. It describes the structure of XML document by its paths, such as the nodes of XML data are labeled by Dewey labeling scheme. The experimental results of [START_REF] Izadi | S 3 : Evaluation of tree-pattern XML queries supported by structural summaries[END_REF] confirm that S 3 substantially outperforms TwigStack , TJFast, and TwigList in terms of response time, I/O overhead, and memory consumption-critical parameters.

Summary

Table 7.1 depicts the various approaches presented in this section. These approaches are categorized into four classes by considering three basic features: the decomposition technique, the labeling technique, and a boolean parameter which indicates whether the merging phase is used in the query processing or not.

Conclusion

Much research effort has been devoted on efficient XML query processing. As a core operation in XML data, finding all occurrences of a query pattern in XML documents attracted more and more attention. In this chapter, we gave a structured overview of the numerous recent advances in the exact tree matching for querying XML data. As mentioned before, a very large volume of algorithms were proposed in the literature, and it seems nearly impossible to consider all related works. It is however difficult to decide what is the best algorithm that performs the query processing efficiently. For example, the one-phase holistic twig join algorithm eliminates completely the second phase of merging at the expense of huge memory requirement. Of course, holistic twig join algorithms are good candidates for physical operators supporting query evaluation in XDBMSs. Therefore, the development of new structural join algorithms is still valuable, the next chapter follows this line of research, In particular, we will propose a new efficient holistic twig join algorithm, called TwigStack++, which can greatly improves query processing performance of XML documents. In order to address the above weaknesses, we propose in this chapter a new efficient holistic twig join algorithm, which can greatly improve query processing performance. Our contributions can be summarized as follows:

1. We first introduce a new buffering technique that allows to eliminate many unnecessary computations in the matching phase.

Chapter 8. TwigStack++: A New Efficient Holistic Twig Join Algorithm 2. We propose a new structural decomposition of a twig query, called star-path twig decomposition which decomposes the twig query into a set of star and path queries. The main objective of this decomposition is to decrease the number of join operations and the number of join attributes in the merging phase.

3. We implemented our proposed method and conducted an extensive performance evaluation using real and synthetic datasets. The results showed that our algorithm achieved high efficiency and outperformed existing proposals.

The rest of this chapter is organized as follows. We start describing the containment labeling scheme in the next section. Section 8.3 is dedicated to present the sub-optimality of TwigStack. Then, TwigStack++ algorithm is proposed in detail in Section 8.4. Section 8.5 reports experimental results, and we conclude the chapter in Section 8.6.

Containment labeling scheme of an XML document

Containment labeling scheme is one of the most popular XML labeling schemes [ZND + 01]. This labeling scheme (called region encoding) uses a textual-position of start and end tags in XML document such that the position is represented by the 4-tuple (docId, start, end, level) for an XML element and (docId, start, level) for a string value, where (i) docId is the identifier of the document; (ii) start and end can be generated by counting word numbers from the beginning of the XML document with identifier docId until the start of the element and the end of the element, respectively. And (iii) level is the nesting depth of the element (or string value) in the document. For example, Figure 8.1 shows an example of tree data with containment labels. The structural relationship between tree nodes in this representation can be determined easily without knowledge of the intermediate nodes on the path. Formally, let two nodes x 1 and x 2 whose positions in the XML database are encoded as (d 1 , s 1 , e 1 , l 1 ) and (d 2 , s 2 , e 2 , l 2 ), respectively. We have 1. Ancestor-Descendant relationship: an element x 1 is an ancestor of another element x 2 if and only if d 1 = d 2 , s 1 < s 2 and e 2 < e 1 .

2. Parent-Child relationship: an element x 1 is a parent of another element x 2 if and only if d 1 = d 2 , s 1 < s 2 , e 2 < e 1 and l 2 = l 1 + 1.

Sub-optimality of TwigStack

TwigStack algorithm constituted the major attempt for several subsequent holistic twig join algorithms. The idea behind this approach is to use a chain of linked stacks to compactly represent partial results of individual query root-leaf paths, which are then composed to produce the final solutions. The main technique of TwigStack is to make use of two data structures: stack S q and stream T q for each node q in twig query. The stream T q contains the positional representation of all elements of tag q. At any time during the algorithm, the elements in stack S q are guaranteed to lie on a root-to-leaf path in the XML document and the chain of stacks contains a compact encoding of partial results to the twig query. The insertion and deletion elements over stacks are operated in the following way:

1. An element x q from stream T q is pushed to the stack S q if and only if (i) x q has a descendant x q i in each T q i , where q i is a child of q and (ii) each node e q i recursively has the first property.

2. An element x q is popped out from its stack if all matches involving it have been output.

For example, consider the query and data tree in Our observation: existing holistic twig join algorithms avoid storing intermediate results unless they contribute to the final results when the query twig has only ancestor-descendant edges. However, they have to recursively call the getNext function (or other functions based on the getNext) many times, which is a core function for the holistic algorithms. Each time, getNext returns a node q and ensures that: (i) the current element in stream q has a descendant element in each stream q i , for every child q i of q, and (ii) each current element in stream q i recursively satisfies the first property. But, most of these calls are unnecessary and could be avoided. Hence, they involve many unnecessary computations. In the previous example, TwigStack calls getNext(a), getNext(b), getNext(c), getNext(d), many times respectively (see Table 8.1), but only a few times are useful and pivotal, and other times can be pruned. In the next section, we will demonstrate how to avoid those unnecessary computations using a new buffering technique. The main idea is to look-ahead read some matching nodes in input data steams and buffer a limited number of them in the main memory.

Another overhead incurred in the merging phase of holistic twig join algorithms could be large because the cost to input and output of the individual matches and finally merge them to form twig matches can be substantial, especially when the number of matching paths is large. To address this problem, we propose a new structural decomposition of the twig query which reduces significantly the number of pieces to be joined.

A new algorithm: TwigStack++

In this section, we present a new holistic twig join algorithm, we start with some notations and definitions that will be used later.

Notations

Consider a tree T , we use V (T ) to denote the vertex set of T . Let x be an internal node of T and let N be a subset of vertices in V (T ), we define the function star(T, x, N ) which returns a star S consisting of a rooted node x and all of its children nodes which are not in the set N . For each vertex x of T , let subtree(T, x) to be the function which returns a subtree of T consisting of a rooted node x and all of its descendants in T .

Given a twig pattern query Q and XML document D conforming to XML schemas. For better understanding of our algorithm, we make use of the following node operations. The self-explaining functions isRoot(q) and isLeaf (q) are used to examine whether q is a root node or a leaf node. The function children(q) returns all child nodes of q and parent(q) gets the parent node of q. The function end(Cq) returns a boolean value that indicates whether the current position Cq is at the end of the stream T q. We use Cq.element to denote the element pointed by Cq. We can access the attribute values of Cq by Cq.start, Cq.end and Cq.level. The cursor can be forwarded to the next element in T q with the procedure advance(T q). Initially, all the cursors point to the head of the corresponding stream. Similar to TwigStack, we make use a chain of linked stacks to compactly represent partial results. Indeed, each internal query node q in a twig pattern Q is associated with a stack Sq. The operations over stacks are: pop, push, top and empty.

We associate a list F q instead of stack with every leaf query node q in Q. Each data node in the list consists of a pair: (positional representation of an element from T q, pointer to Sparent(q)), where Sparent(q) is the stack associated with the parent of q. The operations over list F q are: Fq.getLastElement(), F q.append(e, pointer to Sparent(q)) and F q.clearList(). The first operation returns the element at the end of F q. The second operation appends pair information at the end of F q. The last Algorithm operation removes all elements from F q.

The main technique of TwigStack++ is to make use of buffer Lq for each node q in twig pattern query. For each node q, the operations over Lq are Lq.remove and Lq.append(e). The first operation removes and returns the element at the end of Lq and the last operation appends element e at the end of Lq.

TwigStack++ description

We now present our algorithm TwigStack++ for processing twig pattern matching queries. TwigStack++ preserves the main idea of TwigStack. The objective here is to reduce the amount of I/O and CPU cost by introducing two major improvements as follows.

Star-path decomposition

As a first improvement, we propose a new structural decomposition of a twig query, called star-path twig decomposition, which decomposes the twig query into a set of star and path queries. This decomposition strategy is shown in Algorithm 1 given below, which takes as input a twig query Q. The variable SP is used to save progressively the set of components to be generated from Q. Initially, the forest SP is a null graph (a graph which has no vertices). For example, the structural star-path decomposition corresponding to the query of Figure 8.4(a) is shown in Figure 8.4(b). Our decomposition algorithm consists of two main steps as follows: for every vertex u of degree greater than 2:

1. path decomposition: at line 3-6 in Algorithm 1, the algorithm provides a path for every edge (u, v) where v has degree 2. Then from Figure 8.4(a), we can see that only one path P = (a, b, c, d) is returned for the edge (a, b).

2. star decomposition: at line 7-9, only one star is generated if and only if the vertex u has at least one child node with degree = 2. Then from Figure 8.4(a), two stars are generated for the vertices a and d.

The following theorem shows the advantage of our decomposition approach compared to the root-to-leaf paths decomposition of classical holistic twig join algorithms.

Theorem 8.1 The total number of join operations required for star-path twig decomposition is less than or equal to the number of join operations of the root-to-leaf paths decomposition.

Proof. In TwigStack, a (k -1)-way merge is performed in the merging phase, where k is the number of leaf nodes in the twig query. From Algorithm 1, we can see that for every node u of degree at least 3, we have: for every child v of u with degree exactly 2 do 4:

Let P = u, v, x 1 , • • • , x m be an induced path of Q where the nodes from x 1 to x m-1 has degree 2 in Q and the degree of x m is different from 2. if u has at least one child of degree = 2 then 8:

SP = SP ∪ {star(Q, u, V (SP ))}.

9:

end if 10: end for 11: return SP .

1. star-path twig decomposition approach provides a path for every edge (u, v)

where v has degree 2.

2. only one star is generated if and only if the vertex v has at least one child node with degree = 2 (at line 7-9).

According to these two observations, we can see that the number of generated components passing through the node u is less or equal to the number of children of u which is less than or equal to the number of leaf nodes of subtree(Q, u). Therefore, the total number of join operations of star-path twig decomposition is less than or equal to the number of leaf nodes of any tree, giving the desired result.

From Algorithm 1, we can easily obtain the following theorem.

Theorem 8.2 For every two different components C 1 and C 2 of SP , we have

|V (C 1 ) ∩ V (C 2 )| ≤ 1
Merging individual query solutions to form twig matches is simple, at least, conceptually, but it may turn out to be a very expensive process in reality since the number of join operations can be very large, rendering the merge phase cumbersome and time consuming. By reducing the number of join operations, the performance of XML query processing can be greatly improved. Note that our structural decomposition will not only reduce the number of join operations but will also allow us to decrease a large number of join attributes in the merging phase. So from Theorem 8.2, we can see that the number of join attributes is restricted to one attribute.

Improvement of getNext function

Our second improvement consists essentially in rewriting of TwigStack to eliminate many unnecessary computations in the matching phase. As mentioned earlier, TwigStack works by recursively calling a method called getNext to efficiently filter useless elements in order to return the next node for processing. The existing holistic twig join algorithms may perform many redundant checks in the calls to getNext.

We propose here a new strategy guided by containment labeling scheme to avoid the redundant function calls. TwigStack++ changes the getNext to getNextSet function (Algorithm 2 given below). Implicitly, the getNextSet function does not return only one node (like getNext) but a set of nodes at once. The core of this procedure is more complex than the original algorithm but gives much better results.

In what follows, we first explain the getNextSet function and then present the main algorithm in details. getNextSet(q) is a procedure called in the main algorithm of TwigStack++. It updates the list Lq and returns a query node q ′ (possibly q = q ′ ) with the following properties: at every point during computation:

1. the elements in sequence Lq (from the beginning of L q to the end) are guaranteed to lie on a root-to-leaf path in the XML document.

2. for all ancestor-descendant pairs (q//q ′ ) in the twig query, we have ∀(eq, eq ′ ) ∈ Lq × Lq ′ , then eq ′ is descendant of eq in XML data tree.

3. the number of buffered elements in any list is bounded by the depth of the data tree. Note that the maximal depth of XML documents is usually very limited.

At line 6-18 in Algorithm 2, we recursively invoke getNextSet(q i ) for each q i ∈ children(q). In this computation step, we can avoid many unnecessary computations. Unlike TwigStack, it is unnecessary to recursively check whether q i and their corresponding descendants have solution extensions if one of the following conditions holds (this is because, the query node q i is processed already).

1. The existing top element of Sq i is decendant of the current element in the data stream of node q. Algorithm 2 Function getNextSet(q)

1: if isLeaf(q) then 2:

Lq.append(Cq.element);

3:

advance(T q); 4:

return q; 5: end if 6: for q i in children(q) do 7:

if not isLeaf (q i ) then if (Cq is not an ancestor of e)and(Lq i = ∅) then 13: q j =getNextSet(q i ); 14: if q j = q i then 15: return q j ; 16: end if 17: end if 18: end for 19: let h x be the head element of the list Lx; 20: n min =minarg q i {h q i .star : Lq i = ∅} ∪ {top(Sq i ).star : Lq i = ∅}; 21: n max =maxarg q i {h q i .star : Lq i = ∅} ∪ {top(Sq i ).star : Lq i = ∅}; 22: while Cq.end < maxStar do for all nodes q i in the subtreeN odes(q) do 4:

for all elements e of Lq i do 5:

e = Lq i .remove();

6:

updateStackList(e, q i );

7:
end for 8:

end for 9: end while 10: mergeAllSolutions(); 11: procedure updateStackList(e, q) 12: if not isRoot(q) then 13: cleanStack(Sparent(q), e); 14: end if 15: if isRoot(q) or not empty(Sparent(q)) then if not isLeaf (q) then 18: push(Sq, e, top(Sparent(q))); F q.append(e, top(Sparent(q)); for all leaves qi of q do 31: F q i .clearList();

32:

end for 33: end if 34: end procedure In the first phase (line 1-9), it repeatedly calls the getNextSet function (line 2). In this phase, the matching solutions are computed according to the star-path twig decomposition proposed previously. In the second phase, these solutions are mergejoined to compute the answers of the query twig pattern (line 10). The procedure call updateStackList(eq) (line 11-23) plays the role of updating the stack (or list if q is a leaf) structure. The update of stacks in this procedure is the same as the one used in the original TwigStack. The following property shows the conditions for a list F q (q is a leaf) to be cleared (line 29-33): a list F q is cleared if and only if Sparent(q) is empty. At line 27, showSolution(eq) is called to output all answers (star and path) matches passing through the XML element eq.

We present now an illustrative example of our approach. Consider the twig query and data tree in

Conclusion

In this chapter, we have proposed a new holistic twig join algorithm, called TwigStack++ to efficiently process XML twig patterns. Our approach is based on two main improvements in the matching and merging phase. Experimental results show that our approach achieves high efficiency and outperforms existing proposals.

Chapter 9

Conclusion and Future Work

In this thesis, we discussed three graph theory problems applied to different classes of labeled graphs. In this chapter, we present several open questions and directions for future research in these areas.

****** Over the years, several vertex-distinguishing edge coloring variants have been defined in the literature. We gave in Chapter three a survey of various methods, recent results and open conjectures from this area of research. In particular, we have detailed the vertex-distinguishing edge coloring problem by sets and multisets. Originally motivated by these two variants, we investigated in Chapter four a new variant of edge coloring that induces a vertex distinguishing labeling where the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. In view of our results, we observed that our parameter can be used to get a bound on the detection number. In addition, several results have been obtained for various classes of graphs.

As future works, we plan to focus on the following three issues.

1. We left as an open question to show that the gap chromatic number of a graph of order n is always in {n -1, n, n + 1}.

2. The computational complexity of the gap chromatic number is still an open problem (this is the case of most variants of vertex distinguishing problems derived from an improper edge coloring).

3. As for the other distinguishing parameters, it would be interesting to consider the variant of the gap coloring problem that distinguishes adjacent vertices only.

******

The purpose of the second part of this thesis was to study the graph packing problem for labeled graphs. Much work has been done on the unlabeled graph packing problem and we felt that investigating the labeled case might yield interesting results. The first section of Chapter five was dedicated to giving the reader an introduction to some relevant results on the packing of unlabeled graphs. Then, we studied

Coloring, Packing and Embedding of graphs Abstract: In this thesis, we investigate some problems in graph theory, namely the graph coloring problem, the graph packing problem and tree pattern matching for XML query processing. The common point between these problems is that they use labeled graphs.

In the first part, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G which induces a vertex distinguishing labeling of G such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of G is called the gap chromatic number of G and is denoted by gap(G). We will compute this parameter for a large set of graphs G of order n and we even prove that gap(G) ∈ {n -1, n, n + 1}.

In the second part, we focus on graph packing problems, which is an area of graph theory that has grown significantly over the past several years. However, the majority of existing works focuses on unlabeled graphs. In this thesis, we introduce for the first time the packing problem for a vertex labeled graph. Roughly speaking, it consists of graph packing which preserves the labels of the vertices. We study the corresponding optimization parameter on several classes of graphs, as well as finding general bounds and characterizations.

The last part deal with the query processing of a core subset of XML query languages: XML twig queries. An XML twig query, represented as a small query tree, is essentially a complex selection on the structure of an XML document. Matching a twig query means finding all the occurrences of the query tree embedded in the XML data tree. Many holistic twig join algorithms have been proposed to match XML twig pattern. Most of these algorithms find twig pattern matching in two steps. In the first one, a query tree is decomposed into smaller pieces, and solutions against these pieces are found. In the second step, all of these partial solutions are joined together to generate the final solutions. In this part, we propose a novel holistic twig join algorithm, called TwigStack++, which features two main improvements in the decomposition and matching phase. The proposed solutions are shown to be efficient and scalable, and should be helpful for the future research on efficient query processing in a large XML database.

Coloration, Placement and Plongement de graphes Résumé:

Cette thèse se situe dans le domaine de graphes et de leurs applications, Elle est constitué de trois grandes parties, la première est consacrée à l'étude d'un nouveau type de coloration sommets distinguantes, les arête-colorations sommetsdistinguantes par écarte. Il consiste de trouver une valuation des arêtes qui permette de distinguer les sommets de graphes telle que chaque sommet v du graphe est identifié de façon unique par la différence entre la plus grande et la plus petite des valeurs incidentes à v. Le plus entier pour lequel le graphe G admet une arête-coloration sommets-distinguantes par écarte est le nombre chromatique par écart de G, noté gap(G). Nous avons étudié ce paramètre pour diverses familles de graphes. Une conjecture intéressante, proposée dans cette partie, suggère que le nombre chromatique par écart de tout graphe connexe d'ordre n > 2 vaut n -1, n ou n + 1. La deuxième partie du manuscrit concerne le problème du placement de graphes. Nous proposons un état de l'art des problèmes de placement de graphes, puis nous introduisons la nouvelle notion de placement de graphes étiquetés. Il s'agit d'un placement de graphes qui préserve les étiquettes des sommets. Ensuite, nous proposons des encadrements de ce nouveau paramètre pour plusieurs classes de graphes. La troisième partie de la thèse s'intéresse au problème d'appariement d'arbres dans le cadre de la recherche d'information dans des documents structurés de type XML. Les algorithmes holistique de jointure structurelle est l'une des premières méthodes proposées pour résoudre l'appariement exact des documents XML. Ces algorithmes sont souvent divisés en deux grandes étapes. La première étape permet de décomposer l'arbre de la requête en un ensemble de petites composantes connexes. Ensuite, des solutions intermédiaires pour chaque composante de la requête sont trouvées, ces résultats intermédiaires sont joints pour obtenir la solution finale. Nous proposons dans cette partie un nouvel algorithme appelé TwigStack++ qui vise principalement à diminuer le coût de la jointure et le calcule inutile recherche. Notre algorithme obtient de meilleurs résultats en comparaison avec deux autres méthodes de l'état de l'art.

Keywords: théorie des graphes, graphes étiquetés, colorations sommets distinguantes, placement de graphes étiquetés, l'appariement exact des documents XML.

Figure 2 . 1 :

 21 Figure 2.1: Example of isomorphic graphs:f (u1) = v1, f (u 2 ) = v 3 , f (u 3 ) = v 5 , f (u 4 ) = v 2 and f (u 5 ) = v4.

Figure 2

 2 Figure 2.2: (a) G, (b) G.

Figure 2

 2 Figure 2.3: (a) Path graph, (b) Cycle graph.

Figure 2 . 4 :

 24 Figure 2.4: Complete graphs (a) K 1 , (b) K 2 , (c) K 3 , (d) K 4 , (e) K 5 .

FigureFigure 2 . 6 :

 26 Figure 2.5: Tree.

Figure 3

 3 Figure 3.1: A graph with a proper 3-coloring

Figure 3

 3 Figure 3.2: Coloring scheme of C 7 for each variant in Tabel 3.1.

Figure 4 .

 4 Figure 4.1: A gap vertex-distinguishing edge coloring of a graph.

Chapter 4 .

 4 Gap Vertex-Distinguishing Edge Colorings of Graphs

Figure 4 .

 4 Figure 4.2: A gap vertex-distinguishing edge coloring of C n : (a) n = 8, (b) n = 9, (c) n = 7, (d) n = 6.

Figure 4 . 3 :

 43 Figure 4.3: Illustration of Algorithm 1 (a=12): (a) A 2-edge-connected graph G. (b) Coloring of R 1 . (c),(d),(e),(f) illustrates the coloring of R 2 , R 3 , R 4 , R 5 , respectively. (g) A balanced gap-30-coloring of a spanning subgraph G ′ of G. (h) A gap-30-coloring of G which induces a gap vertex-distinguishing function l : V → {12, 13, . . . , 29}.

Theorem 4 .

 4 11 For every m-edge-connected graph G of order n (with m ≥ 2), different from a cycle of length n ≡ 2 or 3(mod 4), we havegap(G) = nProof. By Lemma 4.2, we have gap(G) ≥ n. It then suffices to prove that G admits a gap-n-coloring. We know by Theorem 4.8 that if G is a cycle of length n ≡ 0, 1(mod 4), then gap(G) = n. Otherwise, it is clear by Proposition 4.10 that if we set the integer parameter a at 0, we obtain a gap-n-coloring of G induced by a balanced edge coloring. Hence gap(G) = n.

Figure 4 . 4 :

 44 Figure 4.4: A gap-coloring of P n : (a) n = 8, (b) n = 9, (c) n = 7, (d) n = 6.

Figure 4 . 5 :

 45 Figure 4.5: (a) Notation of BT 3 , (b) A gap-14-coloring of BT 3

Figure 4 . 6 :

 46 Figure 4.6: Illustration of Algorithm 2: (a) A tree T . (b) Coloring of R 1 . (c),(d),(e),(f) illustrates the coloring of R 2 , R 3 , R 4 , R 5 , respectively. (g) A gap-14coloring of T .

Figure 5

 5 Figure 5.1: A packing of two copies of P 4 ∪ P 3 into K 7 .

Figure 5 .

 5 Figure 5.2: Example of a not 3-placeable tree Packing of k graphs

50 Chapter 5 .

 5 Labeled Packing of Graphs Conjecture 5.12 ([FRSS81]) If a graph G is a non-star graph without cycles of length m ≤ 4, then G is embeddable.

Theorem 5 .

 5 15 ([Woz99]) The following graphs are cyclically embeddable:1. non-star trees.2. (n, n -2) graphs.

Figure 5 . 3 :

 53 Figure 5.3: Five embeddable unicyclic graphs which are not cyclically embeddable.

Theorem 5 .

 5 18 ([Woz94]) Let G = (V, E) be a graph of order n, n ≥ 3. If |E(G)| ≤ n -2 then there exists an embedding σ of G such that each cycle of σ has length 3 except for one of length 1 if n ≡ 1(mod 3) or two of length 1 if n ≡ 2(mod 3).

Figure 5 . 4 :

 54 Figure 5.4: A 5-labeled packing of two copies of P 4 ∪ P 3 .

  The maximum positive integer p for which G admits a p-labeled packing of k copies of G is called the k-labeled packing number of G and is denoted by λ k (G).

Figure 5 . 5 :

 55 Figure 5.5: (a) A caterpillar T , (b) A 10-labeled embedding of T It is clear that any labeled embedding construction (the labeling function f and the permutation σ) that achieves the upper bound of Lemma 5.21 must consider the vertices of V S(f ) as fixed-points under the permutation σ, which then requires to define a ⌊ |V (G)\V S(f ) | 2 ⌋-labeled embedding without fixed points for the subgraph induced by the set of vertices V (G)\V S(f ) . For example, let us consider the caterpillar T of Figure 5.5(a). From Lemma 5.21, we have λ 2 (T ) ≤ 10. This upper bound can be reached by finding a 3-labeled embedding without fixed points for the central path of T (Figure 5.5(b)).

Figure 5 . 6 :

 56 Figure 5.6: Proof structure.

  1: x mod 2m = 0. Let B = {b 0 , b 1 , . . . , b p-1 } be a partition of V (C n ) into p sets,where all sets b i of B have the same cardinalty 2m. Then, we have p

Figure 5 . 7 :

 57 Figure 5.7: Partition of V (C 16 ) for k = 3.

Figure 5 .

 5 Figure 5.8 presents a 10-labeled-packing of three copies of C 16 .From the set of permutations, we can easily see that for every vertexv i in V (C n ), we have f (v i ) = f (σ 1 (v i )) = f (σ 2 (v i )) = • • • = f (σ k-1 (v i )). It then remains to show that the set of cycles σ 0 (C n ) = C n , σ 1 (C n ), σ 2 (C n ) . . . , σ k-1 (C n ) are edge-disjoint into K n .To prove this, it suffices to show that for every vertex v i of V (C n ), we have:

Figure 5 . 8 :

 58 Figure 5.8: A 10-labeled-packing of three copies of C 16 : (a) σ 1 (C 16 ), (b) σ 2 (C 16 ).

Figure 5 .Figure 5 . 9 :

 559 Figure 5.9 shows a 11-labeled-packing of three copies of C 17 .

Figure 5 .Figure 5 .

 55 Figure 5.11 shows a 9-labeled-packing of three copies of C 15 .

Figure 5 .

 5 Figure 5.11: A 8-labeled-packing of three copies of C 14 : (a) σ 1 (C 14 ), (b) σ 2 (C 14 ).

Figure 5 .

 5 Figure 5.12: A 7-labeled-embedding of C 10

Figure 5 .

 5 Figure 5.13: A 13-labeled-packing of three copies of C 20 : (a) σ 1 (C 20 ), (b) σ 2 (C 20 ).

and b k-1 = 64 Chapter 5 .

 645 Labeled Packing of Graphs

Figure 5 .

 5 Figure 5.14 presents a 7-labeled packing of three copies of C 11 .

Figure 5 .

 5 Figure 5.14: A 7-labeled packing of three copies of C 11 : (a) σ 1 (C 11 ), (b) σ 2 (C 11 ).

Figure 5 .

 5 Figure 5.15: A 3-labeled packing of three copies of C 7 : (a) σ 1 (C 7 ), (b) σ 2 (C 7 ).

Figure 5 .

 5 Figure 5.16: A 4-labeled packing of three copies of C 8 : (a) σ 1 (C 8 ), (b) σ 2 (C 8 ).

Figure 6 .

 6 Figure 6.1: A 3-labeled embedding of P 5 .

Figure 6 .

 6 Figure 6.2: A 1-labeled embedding of P 4 .

  one of the graphs of Figure6.5.

Case 1 :

 1 |V \ I| ≥ 5 or C is isomorphic to one of the graphs of Figure. 6.3. From Lemma 5.21, we have λ 2 (C) ≤ |I| + ⌊ n-|I| 2 ⌋, it then suffices to prove that C admits a (|I| + ⌊ n-|I| 2 ⌋)-labeled embedding. Three subcases are considered as follows:

Subcase 3 :

 3 C is isomorphic to one of the graphs of Figure. 6.3. We consider eight cases depending on the structure of C. Let L be the set of end vertices in C.1.

Figure 6 .

 6 3(a): let S = L ∪ {v 4 } = {u 1 , u 2 , . . . , u m },

Figure 6 . 6 :

 66 Figure 6.6: A tree of diameter 4.

Figure 6 . 8 :

 68 Figure 6.8: Forbidden graphs

Figure 7 .Figure 7 . 2 :

 772 Figure 7.1: An example of XML document

Figure 7 . 3 :

 73 Figure 7.3: Example of a data-oriented document

7. 2 .Figure 7 . 5 :

 275 Figure 7.5: An example of tree pattern matching

3 4 )

 4 . Kosaraju introduced three new techniques. Dubiner et al. [DGM94] improved Kosaraju's algorithm by discovering and exploiting periodical strings appearing in the pattern. They obtained a bound of (nm 1 2 ). Cole and Har-98 Chapter 7. Tree Matching and XML Retrieval iharan [CH97] introduced and gave an efficient algorithm for the subset Matching problem. The goal of this problem is to find all occurrences of a pattern string P of length m in a text string T of length n. Then the tree pattern matching has been reduced to a number of instances of the subset matching problem. Combining this reduction with the subset matching algorithm take an O(n log 3 m) time randomized algorithm for the tree pattern matching problem. Later the same authors improved the reduction time complexity [CH03]. They obtained an O(n log 2 m + m) time deterministic algorithm and an O(n log n + m) time Monte Carlo algorithm for the tree pattern matching problem.

  (ii) Tree-Merge and Stack-Tree algorithm: Al-Khalifa et al. [AJK + 02] took advantage of the containment labeling scheme of XML elements to decrease the time of join processing. They developed two algorithms for matching parent-child and ancestor-descendant structural relationships efficiently: Tree-Merge and Tree-Stack.

Figure 8 .

 8 Figure 8.1: A sample XML document with containment labels

Figure 8

 8 Figure 8.2: (a) D: An XML data tree and (b) Q: A twig query pattern

Figure 8 .

 8 2. The stacks encoding and the varying positions of cursors in data streams are shown in Figure 8.3(a)-(e). At the beginning (in Figure 8.3(a)), all cursors point to the first nodes a 1 , b 1 , c 1 , d 1 . Since a 1 is an ancestor of b 1 and d 1 , a 1 is inserted to stack S a in Figure 8.3(b).Then we advance T a to read a 2 which is also pushed to S a (Figure8.3(c)). Next, b 1 and c 1 are pushed into corresponding stacks. At this point, the algorithm outputs two intermediate paths (a 1 , b 1 , c 1 ), (a 2 , b 1 , c 1 ). Finally, d 1 is pushed to S d (in Figure8.3(e)) and output another two intermediate paths (a 1 , d 1 ), (a 2 , d 2 ). Hence, the final results is obtained by merging the obtained intermediate paths.

Figure 8 . 3 :

 83 Figure 8.3: Illustrate to stack operations

Figure 8 . 4 :

 84 Figure 8.4: (a) Tree pattern, (b) Structural star-path decomposition Algorithm 1 Decomposition Input: twig pattern query Q. Output: star-path twig decomposition of Q.1: Forest SP =null graph; 2: for every node u with degree more than 2 in Q do 3:

5 :

 5 SP = SP ∪ {P }.

8. 4 .

 4 A new algorithm: TwigStack++ 115 2. The list Lq i is not empty.

Chapter 8 .

 8 TwigStack++: A New Efficient Holistic Twig Join Algorithm Algorithm 3 TwigStack++ 1: while not (end(Q)) do

Figure 8 .

 8 5(a-b). There are five buffer lists L a , L b , L c , L d and L e . Initially, getN extSet(a) recursively calls getN extSet(b) and getN ext(c) (for b, c ∈ children(a) in Q). Since c is a leaf node in Q, the new element c 1 is inserted into the list L c . Next, getN extSet(b) recursively calls getN extSet(d) and getN extSet(e). Since both d and e are leaf nodes in Q, we obtain getN extSet(d) = d, getN ext(e) = e, L d = {d 1 } and L e = {e 1 }. Therefore, getN extSet(b) = b, getN extSet(a) = a, L b = {b 1 , b 2 } and L a = {a 1 }.

  Figure 8.6(a) shows the state of the algorithm after the previous computation has been completed.In the second call of getN extSet(a), the top element of S b is descendant of the current element in the data stream of node a. Therefore, it is unnecessary to recursively check whether b and their corresponding descendants (d and e) have solution extensions (see Figure8.6(b)).

Figure 8 .

 8 6(c) shows the state of the algorithm when evaluating the query Q, right after node e 2 has been processed. When e 2 is inserted to S 2 , b 2 is popped out (because b 2 is not an ancestor of e 2 ). At this point, the algorithm outputs all solutions (star or path) matches passing through b 2 (Figure8.6(d)).

Figure 8 . 5 :Figure 8 . 8 :

 8588 Figure 8.5: (a) D: An XML Data Tree and (b) Q: A Twig Query Pattern

  Basic notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Some graph operations . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Some families of graphs . . . . . . . . . . . . . . . . . . . . . . 7

	Chapter 2
	Preliminaries
	Contents
	2.1
	. TwigStack++. A New Efficient
	Holistic Twig Join Algorithm, In International Journal of Information-
	Interaction-Intelligence (I3) N:02, 2011.
	2. M. A. Tahraoui, E. Duchêne and H. Kheddouci. Gap vertex-distinguishing
	edge colorings of graphs, Discrete Mathematics Volume 312(20):3011-
	3025. 2012.
	International conferences
	3. E. Duchêne, H. Kheddouci, R. J. Nowakowski and M. A. Tahraoui. La-
	beled Embeddings of Graphs. In SIAM Conference on Discrete Mathe-
	matics, Canada, 2012.

  Let χ ′s (G) denote the minimum number of colors required to have a proper edge coloring of G that induces a vertex-distinguishing labeling by sets. This coloring number was introduced and studied by Burris and Schelp in[START_REF] Burris | Vertex-distinguishing edge-colorings[END_REF][START_REF] Burris | Vertex-distinguishing proper edge colorings[END_REF], and

		Edge	Labeling	vertex	Reference Example
		coloring operation distingushing
	Strong edge coloring	proper	set	global	[BS97]	Fig 3.2(a)
	Point-distinguishing edge coloring	improper	set	global	[HP85]	Fig 3.2(b)
	Adjacent strong edge coloring	proper	set	local	[ZLW02]	Fig 3.2(c)
	Neighbour-distinguishing coloring	improper	set	local	[GHPW08] Fig 3.2(d)
	Detectable coloring	improper	multiset	global	[ATT92]	Fig 3.2(e)
	Vertex colouring edge partitions	improper	multiset	local	[AADR05] Fig 3.2(f)
	Irregular weighting	improper	sum	global	[CJL + 88]	Fig 3.2(g)
	Vertex-colouring edge-weighting	improper	sum	local	[KLT04]	Fig 3.2(h)
	Neighbor sum distinguishing edge colorings	proper	sum	local	[FMP + 12] Fig 3.2(j)
	Multiplicative vertex-colouring weightings	improper	product	local	[Kaz12]	Fig 3.2(i)

Table 3

 3

.1: Summary of vertex distinguishing edge coloring of graphs was independently called observability of a graph by Cerny et al

  Proposition 4.1 A graph G admits a gap vertex-distinguishing edge coloring if and only if it has no connected component isomorphic to K 1 or K 2 .Proof. Since no isolated vertex of a graph G is assigned a label in an edge coloring of G, we may assume that G has no isolated vertex. Furthermore, if G contains a connected component K 2 , then the two vertices of K 2 are assigned the same label in any edge coloring of G. Hence, when considering the gap vertex-distinguishing edge coloring of G, we may assume that the order of every connected component of G is at least 3. Let G be such a graph and let E(G) = {e 1 , e 2 , ..., e m }. The following edge coloring function: f (e i ) = 2 i-1 for 1 i m clearly induces a gap vertex-distinguishing edge coloring of G.

	The following lemma gives a lower bound on the gap chromatic number.
	Lemma 4.2 A graph G of order n and without connected component isomorphic to
	K 1 or K 2 satisfies gap(G) ≥ n -1. Moreover, if δ(G) ≥ 2 or if any vertex of degree
	greater than 1 has at least two neighbors of degree one, then gap(G) ≥ n.

  Contents 5.1 Packing and embedding of unlabeled graphs . . . . . . . . . 45 5.1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . .

45 5.1.2 Packing of graphs of small size in a complete graph . . . . . . 47 5.1.3 Packing graphs with bounded maximum degree and bounded girth in a complete graph . . . . . . . . . . . . . . . . . . . . 49 5.1.4 Graph packing and permutation structure . . . . . . . . . . 50 5.1.5 Our observations . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.2 Labeled Packing Problem . . . . . . . . . . . . . . . . . . . . 52 5.2.1 Definitions and general results . . . . . . . . . . . . . . . . . 52 5.2.2 Labeled-packing of k copies of cycles with order at least 4k . 56 5.2.3 Labeled packing of k copies of cycles of order at most 4k -1 62 5.2.4 Summary and concluding remarks . . . . . . . . . . . . . . . 65 5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

  Contents 7.1 Querying XML Data: Key points . . . . . . . . . . . . . . . . 92 7.1.1 Tree representation of XML documents . . . . . . . . . . . . 92 7.1.2 Query languages . . . . . . . . . . . . . . . . . . . . . . . . . 94 7.2 Algorithms for exact tree pattern matching . . . . . . . . . 96 7.2.1 Notation and terminology . . . . . . . . . . . . . . . . . . . . 96 7.2.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96 7.3 Exact tree pattern matching for XML retrieval . . . . . . . 98 7.3.1 Structural join approaches . . . . . . . . . . . . . . . . . . . . 98 7.3.2 Holistic twig join approaches . . . . . . . . . . . . . . . . . . 99 7.3.3 Sequence matching approaches . . . . . . . . . . . . . . . . . 102 7.3.4 Other important exact XML tree algorithms . . . . . . . . . 103 7.3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Table 7 .

 7 1: Summary of XML retrieval approaches using XML exact tree matching As mentioned in the previous chapter, a typical approach of twig pattern matching is to first decompose the twig query into a set of binary (parent-child or ancestordescendant) relationships. Thus, each binary relationship is separately executed and its intermediate results are stored for further processing, and the final solution is formed by merging these intermediate results. The main disadvantage of such a decomposition is that intermediate result sizes can become very large, even if the input and the final result sizes are much more manageable. In order to overcome this problem, Bruno et al.[START_REF] Bruno | Holistic twig joins: optimal XML pattern matching[END_REF] introduced the first holistic twig join algorithm, called TwigStack. It answers the twig query holistically and avoids huge intermediate results. The holistic twig join algorithm forms an important branch in XML retrieval. However, it may perform a lot of unnecessary computation when processing the queries and disk I/O in the merging phase.

	Chapter 8

Contents 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.2 Containment labeling scheme of an XML document . . . . 108 8.3 Sub-optimality of TwigStack . . . . . . . . . . . . . . . . . . 109 8.4 A new algorithm: TwigStack++ . . . . . . . . . . . . . . . . 111 8.4.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.4.2 TwigStack++ description . . . . . . . . . . . . . . . . . . . . 112 8.5 Experimental result . . . . . . . . . . . . . . . . . . . . . . . . 118 8.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 8.1 Introduction

Table 8 .

 8 1: Number of calls to getNext durning TwigStack

  : procedure cleanStack (S, e) 25: while not empty(S) and (top(S).end < e.start) do

	21:	end if
	22: end if
	23: end procedure
	26:	pop(S);
	27:	showSolution(top(S));
	28: end while
	29: if emty(Sq) then
	30:

24

Acknowledgments

First of all I indebted to my supervisor Hamamache Kheddouci for his helpful guidance and advice for the entirety of my graduate studies. I would also like to thank him for introducing me to the topic of graph theory and for many useful discussions (mathematical and otherwise).

I also would like to express my deepest acknowledgement to the other supervisor Prof. Eric Duchêne for his inspiring guidance, helpful suggestions, and persistent encouragement as well as close and constant supervision throughout the period of

Chapter 6. Labeled Embedding of Trees and (n, n -2)-graphs 2. Figure 6.5(b): let S = L \ {v 1 } = {u 1 , u 2 , . . . , u m }, For every vertex u i of S, f (u i ) = i and σ(u i ) = u i .

f

Labeled embedding of trees

In this section, we intend to prove a lower bound on the labeled embedding number of general trees. Theorem 6.8 Let T be a non-star tree of order n and let X be the set of end-vertices of T , then

The lower bound of the previous theorem relies on two main theorems (Theorem 6.10 and Theorem 6.11). We first introduce the following notation to simplify our proofs. Let T = (V, E) be a graph of order n. For a vertex v ∈ V , let d(v) denote its degree and let diam(T ) denote the diameter of T . A permutation σ of V (T ) will be called good for T if and only if:

1. σ is an embedding of T .

2. σ has at least ⌊ 3n 4 ⌋ -2 cycles.

3. for every pair of end-vertices (u, v) in T , we have σ(u) = v and σ(v) = u.

Thus, to prove that λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2, it suffices to show that T admits a good permutation. Finally, for a vertex v of T , let T v be the subtree rooted at v and let V (T v) denote the set of vertices of T v. At the beginning, we prove the following theorem which will be useful for the proof of Theorem 6.10. Theorem 6.9 Let T be a tree of order n and diameter 4, then there exists an embedding σ of T such that σ is good.

Proof. If T is a caterpillar, then we have by Theorem 6.6 that λ 2 (T ) ≥ ⌊ 3n 4 ⌋ -2. In the other case, the level 2 of T contains at least three vertices of degree greater than 1 (see Figure 6.6). Let U = {u 1 , u 2 , . . . , u m } be the set of vertices of T with degree at least 2 except x and y. Let σ(T ) be an embedding of T into K n under the permutation σ where Chapter 6. Labeled Embedding of Trees and (n, n -2)-graphs proposition: * : σ(u 3 ) = u m-2 or σ(u m-2 ) = u 3 . The permutation σ ′ can be extended to a good permutation σ of T as follows: From this permutation scheme, we obtain the following equation:

By hypothesis, we have that λ 2 (T ′ ) ≥ ⌊ 3n ′ 4 ⌋ -2, and thus

Hence σ is a good permutation of T . Subcase 3.2: d(u 2 ) ≥ 3 and d(u m-1 ) ≥ 3. Three cases are considered as follows: (a) diam(T u 3 ) = 4 or diam(T u m-2 ) = 4. Wlog, assume that diam(T u 3 ) = 4. We consider the tree

a star, then T is isomorphic to one of the graphs of Figure 6.8. In this case, we choose a set of vertices X ⊂ V such that T \ X = (u 1 , u 2 , u 3 , u 4 ). The induction hypothesis guarantees the existence of a good permutation σ ′ on (u 1 , u 2 , u 3 , u 4 ). We can easily see that σ ′ is fixed-point-free permutation. Then, σ ′ can be extended to a good permutation σ of T as follows: σ(x) = u 5 , σ(u 5 ) = x and for every vertex v ∈ X \ {x, u 5 }, σ(v) = v. Hence σ is a good permutation of T . We suppose now that T ′ = K 1,m-1 , then the induction hypothesis guarantees the existence of a good permutation σ ′ on V (T ′ ). The permutation σ ′ can be extended to a good permutation σ of T as follows:

Chapter 6. Labeled Embedding of Trees and (n, n -2)-graphs is a good permutation of G. (c) diam(x 3 ) = 2 and diam(y 3 ) = 2. consider the graph G ′ = G\(V (T x 3 )∪V (Hy 3 )). So the induction hypothesis guarantees the existence of a good permutation σ ′ on V (G ′ ). The permutation σ ′ can be extended to a good permutation σ of G as follows:

From this permutation scheme, we obtain the following equation:

By hypothesis, we have that

Case 2: (p = 3 and q ≥ 3) or (p ≥ 3 and q = 3). Wlog, assume that p = 3. Two subcases are considered as follows:

Subcase 2.1: d(x 2 ) = 2 or d(y 2 ) = 2. This case follows easily using the same induction scheme as in Subcase 1.1. Subcase 2.2: d(x 2 ) ≥ 3 and d(y 2 ) ≥ 3. Consider the graph G ′ = G \ (T ∪ {y 1 , y 2 }). So the induction hypothesis guarantees the existence of a good permutation σ ′ on V (G ′ ). The permutation σ ′ can be extended to a good permutation σ of G as follows:

From this permutation scheme, we obtain the following equation:

By hypothesis, we have that

Case 3: G has a star S m . Let v be the root vertex of S m and let u = v be a vertex of degree 2 of G. Consider the graph G ′ = G \ (V (S m ) ∪ {u}). Then there exists a good permutation for G ′ , say σ ′ . Putting σ(u) = v, σ(v) = u, for every leaf vertex x ∈ V (S m ), σ(x) = x and for x ∈ V (G ′ ), σ(x) = σ ′ (x) we get a good permutaion for G.

the query twig into a set of root-to-leaf paths so that the ordered tree inclusion can be safely applied. It has to be evaluated against the data signature in the second phase. Finally, the set of answers is determined by joining compatible intermediate solutions. The experiments in [START_REF] Zezula | Tree signatures for XML querying and navigation[END_REF] demonstrate the efficiency of the decomposition approach, which is especially advantages for the large query trees, and for trees with highly selective predicates.

Two other sequence matching algorithms, ViST [START_REF] Wang | Vist: A dynamic index method for querying XML data by tree structures[END_REF] and PRIX [START_REF] Rao | Prix: Indexing and querying XML using prüfer sequences[END_REF] were proposed to avoid expensive join operations. ViST method represents a major departure from previous XML indexing approaches. In fact, unlike classical index methods that decompose a query into multiple sub-queries, and then join the solutions of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. This method introduced a new sequential representation that transforms XML data trees and twig queries into structure-encoded sequences. ViST performs efficient subsequence matching algorithms on the structure-encoded sequences to find twig patterns in XML documents. However, the query processing in ViST may result in false alarms and false dismissals (these two problems are explained in more detail in [START_REF] Wang | On the sequencing of tree structures for XML indexing[END_REF]). In [START_REF] Rao | Prix: Indexing and querying XML using prüfer sequences[END_REF], Rao and Moon proposed a new indexing XML documents and processing twig patterns in an XML database. This indexing approach transforms XML documents and twig query into sequences by prüfer method that constructs an oneto-one correspondence between trees and sequences. Based on this transformation, a query execution system, called PRIX (Prüfer sequences for indexing XML) is developed for indexing XML documents and processing twig queries. The matching phase is achieved by applying subsequence matching on the set of sequences in XML database.

Other important exact XML tree algorithms

In this section, we take a quick look over some other well-known query tree pattern processing algorithms which have been developed in recent years. Among them, some approaches have benefited from fundamental progress in node labeling schemes of XML documents (for a survey, see [START_REF] Haw | Node labeling schemes in XML query optimization: A survey and trends[END_REF]).

In [START_REF] Wu | XML twig pattern matching using version tree[END_REF], a twig pattern matching algorithm, called TwigVersion is proposed. the key idea of this approach is to compress both structural index and numbering schemes technique. TwigVersion is based on new version-labeling scheme that encodes all repetitive structures in XML documents. The identification of these repetitive structures matching allows to avoid a large amount of unnecessary computations. The experimental results reported in [START_REF] Wu | XML twig pattern matching using version tree[END_REF] show that TwigVersion significantly outperforms TwigStack, TJFast and Twig2Stack algorithms.

Recently, Izadi et al. [START_REF] Izadi | S 3 : Evaluation of tree-pattern XML queries supported by structural summaries[END_REF] proposed a novel method, called S 3 , which can selectively process the document nodes. In S 3 , unlike all previous methods, path ex- (a 2 , d 1 ). In this example, we have used only four calls to getNextSet to returns the final solutions: getNextSet(a), getNextSet(b), getNextSet(c), getNextSet(d). However, From Table 8.1 of Section 4, TwigStack requires 20 calls to getNext in order to return the final solution.

Finally, it is clear that our algorithm follows the same line of reasoning of TwigStack. Hence, it is easy to show the correctness and the completeness of TwigStack++ by directly deriving the proofs of TwigStack [START_REF] Bruno | Holistic twig joins: optimal XML pattern matching[END_REF]. Thus, we obtain the following theorem. Theorem 8.3 Given a twig query Q and an XML database D, the TwigStack++ algorithm correctly returns all the answers for Q on D.

Experimental result

In this section, we present the experiments conducted to evaluate the efficiency of our algorithm and report some of the results obtained. We compared TwigStack++ with two other twig join algorithms: TwigStack [BKS02] and TJEssential [START_REF] Li | Efficient holistic twig joins in leaf-to-root combining with root-to-leaf way[END_REF] when the twig query pattern only involves ancestor-descendant relationships. The reason for which we choose these two existing algorithms for comparisons is that TwigStack and TJEssential are very efficient when the query contains only ancestordescendant relationships. Since our improvements do not depend on the structure of the twig pattern, our algorithm can be easily adapted to other holistic twig join algorithms like TwigStackList [START_REF] Lu | Efficient processing of XML twig patterns with parent child edges: a look-ahead approach[END_REF] for efficiently processing twig queries with parent-child edges.

All the algorithms were coded using Java 1.4.2, and performed experiments on a PC with a Intel(R) Core(TM) 2 Duo T7250-2GHz processor and 2GB of main memory. We used real-world (TreeBank) and synthetic data sets (XMark) for the experimental evaluation. The comparison between the three algorithms is based the labeled graph packing problems for k copies of cycles in which we have proved the exact value of λ k (G) for all n ≥ 4k -3. In Chapter six, we computed upper bounds for the labeled embedding number of trees and (n, n-2)-graphs. From these results, we can consider several directions for future work:

1. We would like to prove Conjecture 5.28 (in Chapter 5) that deals with the labeled packing of k copies of cycles of order n, where 2k + 1 ≤ n ≤ 4k -3.

2. we hope that the work in Chapter 6 provides a helpful beginning to the study of the labeled packing of three copies of trees and (n, n -2)-graphs.

3. Characterize all trees T for which the labeled embedding number of T reaches the upper bound of Lemma 5.21.

4. We would also like to improve the lower bound of the labeled embedding number of (n, n -2)-graphs from ⌊ 2n 3 ⌋ to ⌊ 3n 4 ⌋ -2 (as shown in Conjecture 6.15).

******

The last part of this thesis addresses the problem of query processing in XML databases, namely XML twig queries. An XML twig query, represented as a labeled tree, is essentially a complex selection on the structure of an XML document. Thus, XML tree patten matching is widely regarded as a new challenge for efficient XML query processing. Until now, the holistic twig join approach was regarded as the most efficient family in the literature. In Chapter seven, we provided a comprehensive survey of the basic ideas and results of the main holistic twig join algorithms available in the literature. In Chapter eight, we proposed a novel holistic twig join algorithm, called TwigStack++. This algorithm is based on two main improvements in the decomposition and matching phases. We analytically and experimentally shown that TwigStack++ can efficiently avoid many unnecessary computation and I/O cost. While this part has proposed an efficient algorithm for XML tree pattern matching, a number of issues need to be further investigated.