Ben Helmi

Frank Hmida

Boochs

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Christophe Nicolle
email: cnicolle@u-bourgogne.fr

Semantic-based Technique for the Automation the 3D Reconstruction Process

Keywords: Semantic web, knowledge modeling, ontology, 3D processing, mixed strategy, 3D scene reconstruction, object identification I

The reconstruction of 3D objects based on point clouds data presents a major task in many application field since it consumes time and require human interactions to yield a promising result. Robust and quick methods for complete object extraction or identification are still an ongoing research topic and suffer from the complex structure of the data, which cannot be sufficiently modeled by purely numerical strategies. Our work aims at defining a new way of automatically and intelligently processing of 3D point clouds from a 3D laser scanner. This processing is based on the combination of 3D processing technologies and Semantic Web technologies. Therefore, the intention of our approach is to take the human cognitive strategy as an example, and to simulate this process based on available knowledge for the objects of interest. First, this process introduces a semantic structure for the object description. Second, the semantics guides the algorithms to detect and recognize objects, which will yield a higher effectiveness. Hence, our research proposes an approach which uses knowledge to select and guide the 3D processing algorithms on the 3D point clouds.

INTRODUCTION

The laser scanning technology is a powerful tool for many applications; it has partially replaced traditional surveying methods since it can speed up field work significantly. This results in rich datasets with lots of useful and useless information. On one hand, the "manual" processing of such data set is efficient and robust since a human uses his own knowledge for detecting and identifying objects in point clouds, but this process is tedious, timeconsuming and expensive. On the other hand, the "automatic" processing of 3D point clouds can be very fast and efficient, but often it relies on significant interactions with the user for controlling algorithms and verifying the quality of the results. The WiDop project [START_REF] Marbs | Wissensbasierte Objekterkennung in 3D-Punktwolken und Bildern[END_REF] aims at the automatic processing of 3D point clouds using the specialist knowledge in order to guide the reconstruction process. By this way, the point clouds quantification and qualification will not be processed via an intermediary step allowing the human intervention (Figure 1). The principle of the WiDop project is a knowledge-based detection of objects in point clouds for AEC (Architecture, Engineering and Construction) engineering applications. Funded by the German government, the partners of the WiDop project are the German railway company (Deutsche Bahn), the Fraport company (Frankfurt Airport manager), and the Metronome company specializing in 3D point cloud processing. The Fraport company main concerns are building and furniture management of the airport. The furniture's position relative to the security gates and the trashes are constantly moving. In addition, updates are done on buildings such as new walls, destruction of walls, new holes in a wall, new windows, etc. This could be undertaken by the director of a new shop or by the technical employers in order to reorganize storerooms for instance. As a matter of fact, it is very difficult to keep up to date the plans of the airport. The motivation of the Deutsche Bahn Company is the management of railway furniture. The issue is closed to the Fraport Company because they have to face the management of the furniture which changed constantly. The cost of keeping these plans up to date is increasing. The solution consists to fix on a locomotive a 3D terrestrial laser scanner and to survey the surrounding landscape. After the first survey, the resulting data will be considered as a reference for comparisons with future surveys in order to detect changes. As a consequence, both companies will benefit from an automatic processing, because too much data has to be processed, and the amount of data leads to a tremendous management cost.

Ten years ago, a new format, which seems to be very suitable for our purpose was developed by the IAI (The International Alliance for Interoperability) it is named the IFC format (IFC -Industry Foundation Classes). The specification is a neutral data format to describe exchange and share information typically used within the building and facility management industry. This norm considers the building elements as independent objects where each object is characterized by a 3D representation and defined by a semantic normalized label. Consequently, the architects and the experts are not the only ones who are able to recognize the elements, but everyone will be able to do it, even the system itself. For instance, an IFC door is not just a simple collection of lines and geometric primitives recognized as a door; it is an "intelligent" object door which has a door attributes linked to a geometrical definition. The building mock-up for instance is designed by engineers and it describes all concrete and abstract elements of a building. Thus, it allows each participant in a building project to share and exchange information with the standardized description. IFC files are made of objects and connections between these objects. Object attributes describe the "business semantic" of the object. Connections between objects are represented by "relation elements" [START_REF] Vanlande | IFC and building lifecycle management[END_REF]. This format and its semantics are the keystone of our solution.

The following section covers background information on works and projects that aim at the reconstruction of 3D scenes from 3D point clouds. Section 3 presents a summary of the designed solution. Section 4 describes in detail the WiDop project. Section 5 focuses on the general model conception and the interaction management between the different created layers. It gives an overview of the different components of the reconstruction process and the basic theory of the "WiDop mixed strategy" presented by the combination of semantic web technology and 3D processing algorithms. Finally, conclusions and suggestions for future work are presented.

II. RELATED WORK

The reconstruction of 3D scene covers a wide area of computer vision; such reconstruction is based on the 3D processing algorithm extracted from the signal processing domain. Recent works aims to reconstruct a scene based on semantic networks describing the relationship between the scene objects. Based on these observations, this section will be articulated in two parts: the first one presents reconstruction methods based on signal processing algorithms while the second one describe methods based on semantic networks technology. Within a photogrammetric domain, there are three classes of methods for 3D scene reconstruction: Manual, semi-automatic and automatic methods.

A. 3D Processing Methods

Within the Terrestrial Scanning Laser (TSL) processing, three different main method classes are identified. These methods are classified based on their automatic rate. This section is articulated in three parts. The first part presents reconstruction methods based on manual processing of 3D point of clouds. The second presents the semantic based method to assist in the 3D scene reconstruction process and finally, the third one shows the automatic processing methods.

1) Manual methods: are completely based on user interactions. Such methods allow the user to extract the scene elements, which are then converted into 3D models with the help of software's packages.

2) Semi-automatic methods: in these methods, the user initializes the process by some manual measurements based on which an algorithm tries to extract other elements. Such methods are based on user interactions and automatic algorithm processing. They support elements projection, affine, and Euclidean geometries [START_REF] Zitova | Image registration methods: a survey[END_REF] for the definition of constraints. When modeling buildings by constructive solid geometry, buildings can be regarded as compositions of a few components with simple roof shapes (such as flat roofs, gable roofs and hip roofs). In [START_REF] Vosselman | 3D building model reconstruction from point clouds and ground plans[END_REF], Vosselman et al. tried to reconstruct a scene based on the detection of planar roof faces in the generated point clouds based on the 3D Hough transform. The used strategy relies on the detection of intersection lines and height jump edges between planar faces. Once done, the component composition is made manually.

3) Automatic methods: these methods are processed without the need of any kind of user intervention. Manual methods have been established with the appearance of the need to reconstruct 3D scene long time ago and are available under a high end commercial feature c.f. Leica® [18] or low cost software Dista [START_REF]Dista[END_REF]. Automatic methods use various approaches but all are based on segmentation techniques to extract features. The methods of Pollefeys et al. [START_REF] Pollefeys | Automated reconstruction of 3D scenes from sequences of images[END_REF] and Zisserman et al. [START_REF] Hartley | Multiple view geometry in computer vision[END_REF] use the projective geometry technique. Pollefeys method divides the task of 3D modeling into several steps. The system combines various algorithms from computer vision, like projective reconstruction, auto-calibration and depth map estimation. The disparity calculation between point pairs makes it possible to get a depth map. The depth map is then transformed into a volume model composed of voxels. The surface estimation between the outer surface voxels and the interior surface voxels makes it possible to combine inner and outer object parts. The method developed is effective and obtains good results. The approach of Zisserman et al. [START_REF] Hartley | Multiple view geometry in computer vision[END_REF] proceeds in two steps. First, a coarse surface model of the building is carried out. Then the coarse model guides the search of details (windows and doors) and refines the surface model. The reconstruction uses the detection of "vanishing points", line correspondence, and the estimation of points and homologous lines. Vanishing points are necessary for the detection of planar primitives with the help of the plane-sweeping method. This method has strong constraints as it contains three perpendicular dominant directions.

B. Knowledge-based Methods

All the strategies outlined below are based on signal processing algorithms, in the other side, new strategies appeared recently. They are based on semantic networks to guide the reconstruction like the work of Cantzler et al. [START_REF] Cantzler | Quality enhancement of reconstructed 3D models using coplanarity and constraints[END_REF], it aim to improve the structural quality of a 3D model. Architectural features like orientation of wall are used. Then, the feature's relationships are automatically extracted using a semantic network of the building mock 'up. The whole strategy consists of three steps: the architectural feature extraction from triangulated 3D model. Then the automatic extraction of constraint out of the scene is carried out by matching the planes against a semantic network of the building mock 'up by backtracking research tree. In this step, the semantic network concentrates the definition of the 3D objects and the relationships between them. The constraints such as parallel or perpendicular wall are exploited. The last step consists in applying the constraint to the model. Consequentially, the original model will be fitted to the new constraint model. Ansgar et al. [START_REF] Brunn | A step towards semantic-based building reconstruction using markov-random-fields[END_REF] presents a new concept for the building reconstruction. Building model is reconstructed based on it is topology using Markov model technique.

Stephane et al. [START_REF] Scholze | A probabilistic approach to building roof reconstruction using semantic labelling[END_REF], investigates this work into a model based reconstruction of complex polyhedral building roofs. The roof in question is modeled as a structured collection of planar polygonal faces. The modeling is done into two different regimes, one focus on geometry, whereas the other is rules by semantics. Concerning the geometry regime, the 3D line segments are grouped into planes and furthers into faces using a Bayesian analysis. In the second regime, the preliminary geometric model is subject to a semantic interpretation. The knowledge gained in this step is used to infer missing parts of the roof model (by invoking the geometric regime once more) and to adjust the overall roof topology.

C. Discussion

The problem of automatic object reconstruction remains a difficult task to realize in spite of many years of research [START_REF] Grimson | From images to surfaces: A computational study of the human early visual system[END_REF]. The major problems are the impact of the viewpoint onto the appearance of the object, resulting in changes with respect to geometry, radiometry, and existence of occlusions and the lack of texture. Strong variations in the viewpoint may destroy the adjacency relations of points, especially when the object surface shows considerable geometrical variations. This dissimilarity causes confusions within correspondence determination and is even worse, when partial occlusions result in a disappearance of object parts. In cases of weak texture, algorithms do not have sufficient information to correctly solve the correspondence problem. Consequently, the reconstruction fails to give a solution. Cantzler et al. [START_REF] Cantzler | Quality enhancement of reconstructed 3D models using coplanarity and constraints[END_REF] and Nüchte et al. [START_REF] Nuchter | Automatic model refinement for 3D reconstruction with mobile robots[END_REF] tried to solve these problems by using semantic information coupled to a scene.

Planes found in the reconstruction phase are introduced into a semantic interpretation, which has to fit to a network model [START_REF] Grau | A scene analysis system for the generation of 3-D models[END_REF]. A tree of "backtracking" allows the finding of the best mapping between the interpretation of the scene and the semantic network model. A coherent labeling exists, if all surfaces are labeled. Relations between the nodes of the semantic network are used to define geometrical constraints between labeled surfaces. The model used and the relations between the elements of the model define the knowledge of a typical architectural scene. The interpretation of the scene then forms a semantic network, which is an instance of the architectural model. Actually, we argue that the pervious cited works and others do not take in account the context of the geometries, and the use of 3D processing algorithms. Based on these observations, the idea behind this work is to benefit from the knowledge related to the scene structure and the different characteristics of geometries mainly to select the most suitable 3D processing algorithm from a 3D processing algorithm collection. In addition, in order to resolve the ambiguities issue of the scene caused by the sited constraints, more than one interaction between the semantic network and the 3D point clouds data is required.

In this paper, we claim that the domain of the semantic Web, and semantics technologies that it relies on, is of benefit for the definition of an automatic processing. One of the technologies is a language that helps to define ontologies; an evolved version of the semantic networks. Ontologies presents one of the most famous technology for knowledge modeling, where the basic ideas was to present information using graphs and logical structure to make computers able to understand and process it easily and automatically [START_REF] Borst | Engineering ontologies[END_REF]. Our approach aims to structure knowledge, link geometrical objects to semantic information, create rules and finally guide the algorithms selection in 3D point clouds processing. The created knowledge will be structured in ontology. The produced ontology to orient the 3D object identification contain variety of data like the GIS data, images capture synchronized with the point clouds, information about the objects characteristics, the hierarchy of the sub elements, the geometrical topology, different processing algorithms etc. In the automatic process, the modeled knowledge will provide to the system relevant information aiming to orient the localization and the identification process. This purpose is reached by selecting the most suitable algorithm for the object detection and recognition. To achieve it, the ontology must contain information about objects characteristics like positions, geometrics information, images textures, etc. and also about the most suitable detection algorithms for each of existent objects.

III. SYSTEM OVERVIEW

As mentioned above, the automatic processing of 3D point clouds can be very fast and efficient, but often relies on significant interaction of the user for controlling algorithms and verifying the results. Alternatively, the manual processing is intelligent and very precise since a human person uses its own knowledge for detecting and identifying objects in point clouds, but it is very time-consuming and consequently inefficient and expensive. If human knowledge could be inserted into automatic detection and reconstruction algorithms, point cloud processing would be more efficient and reliable. However, such a solution involves a lot of questions and challenges such as: (1) How can knowledge be structured based on heterogeneous sources? (2) How to create a coarse model suitable for different applications? (3) How to allow a dynamic interaction between the knowledge model and the 3D processing part?

In general, mathematical algorithms contain different data processing steps which are combined with internal decisions based on numerical results. This makes processing inflexible and error prone, especially when the data does not behave as the model behind the algorithm expects. We want to put these implicit decisions outside, make a semantic layer out of it and combine it with the object model. This approach is more flexible and can be easily extended, because knowledge and data processing are separated.

The created knowledge will serve to guide the numerical algorithms for 3D point cloud processing, based on rules that have been created and formalized before. The knowledge will be organized in an ontology structure. Knowledge not only describes the information of the objects, but also gives a framework for the control of the strategies selected. For instance, it provides rules for the localization and identification process. These rules guide the selection of individual algorithms or sequences allowing the detection and recognition of the object to be searched for. Once the knowledge provides initial information about the structure of the scene and the objects, candidate regions can be determined. Then, the algorithms integrated in the knowledge will be guided to identify objects. In other cases, when the existence of objects in the scene is ambiguous, we will search them in the point cloud based on updated information in the knowledge model. Consequently, knowledge-based methods will enable the algorithms to be executed reasonably and adaptively on particular situations. This is where WiDOP project will try to make a step forward.

IV. WIDOP PROCESSING CAPACITY

The WiDop project aims at the development of efficient and intelligent methods for an automated processing of terrestrial laser scanner data. Figure 2 presents the general coarse architecture for the WiDop project, composed of 3 parts: the knowledge part, the 3D processing part and the interaction management and control part labeled (WiDop Processing) ensuring the interaction between the above sited parts. In contrast to existing approaches, we aim at the utilization of previous knowledge on objects. This knowledge can be contained in databases, construction plans, as-built plans or Geographic Information Systems (GIS). Therefore, this knowledge is the basis for a selective, objectoriented detection, identification and, if necessary, modeling of the objects and elements of interest in the point cloud.

A. The knowledge processing

Our approach aims at structuring and modeling the existing knowledge in order to represent objects from the geometrical and the semantic point of view and to integrate important feature characteristics, if necessary. In the second step, this knowledge base will guide the numerical algorithms for 3D point cloud processing, based on rules that have been created and formalized before. This approach also follows the concept of Semantic Web, while the knowledge will be organized in an ontology structure, where the basic idea is to present information in a logical structure to make computers able to understand and process it easily and automatically. Our approach is intended to use semantic knowledge based on OWL technology for knowledge modeling and processing. Knowledge has to be structured and formalized based on IFC schema, XML files, etc., using classes, instances, relations and rules. An object in the ontology can be modeled as presented; a room has elements composed of 4 walls, a ceiling and a floor. The sited elements are basic objects. They are defined by their geometry (plane, boundary, .), features (roughness, appearance, etc.), and also the qualified relations between them (adjacent wall, perpendicular, etc.). The object "room" gets its geometry from its elements and further characteristics may be added such as functions in order to estimate the existent sub elements. For instance a "classroom" will contain "tables", "chairs", "a blackboard", etc. The research of the object "room" will be based on an algorithmic strategy which will look for the different objects contained in the point cloud. This means, using different detection algorithms for each element, based on the above mentioned characteristics, will allow us to classify most of the point region in the different element categories. This prior knowledge is modeled in a Coarse Model (CM). It corresponds to the spatial structure of a building and it is an instance of semantic knowledge defined in the ontology. This instance defines the rough geometry and the semantics of the building elements without any real measurement. For example, a CM may define the number of stages, the type of roof, the configuration of the walls, the number of rooms per floor, the number of windows and doors per wall. In a CM, images and point clouds may be used as entry parameters for the process of data collection trying to correct the CM.

B. The 3D processing:

Numerical processing includes a number of algorithms or their combination to process the spatial data. Strategies include geometric elements detection (straight line, plane, surface, etc.), projection -based region estimation, histogram matrices, etc. All of these strategies are either under the guidance of knowledge, or use the previous knowledge to estimate the object intelligently and optimally. Alongside with 3D point clouds various types of input, data sets can be used such as images, range images, point clouds with intensity or color values, point clouds with individual images oriented to them or even stereo images without point cloud. All sources are exploited for application to particular strategies. Knowledge not only describes the information of the objects, but also gives a framework for the control of the selected strategies. The success rate of detection algorithms using RANSAC [START_REF] Lacey | Faithful least-squares fitting of spheres, cylinders, cones and tori for reliable segmentation[END_REF], Iterative Closest Point [START_REF] Besl | A Method for Registration of 3-D Shapes[END_REF] and Least Squares Fitting [START_REF] Arun | Least-squares fitting of two 3-D point sets[END_REF] should significantly increase by making use of the knowledge background. However, we are planning not only to process point data sets but also based on a surface and volume representation like mesh and voxels, respectively. These methods will be selected in a flexible way, depending on the semantic context.

C. The WiDop processing:

In order to manage the interaction between the knowledge part and the 3D processing part, a new layer labeled the WiDop processing is created. This layer ensures the control and the management of the information transaction and the decision taken, based on several steps, as outlined in Figure 3. The steps are:

• The algorithmic strategy selection.

• The update of the Coarse Model.

• The topological search of new objects.

• The semantic characterization of new objects.

In the next section, the mixed strategy based on the WiDop processing layer is presented in detail in order to show the different interactions that takes place during the WiDop reconstruction process between the knowledge base and the 3D processing algorithms.

V. THE INTERACTION MANAGMENT

We propose a mixed strategy based on WiDop processing layer insuring the interaction between the knowledge base and the 3D processing algorithms (Figure 2). It presents an intermediary between the semantic based strategy and the 3D processing one. In this section, the global view of our mixed strategy will be presented and the ultimate interaction between both of parts is described.

As seen in Figure 3, the mixed strategy is based on two principles axes which are the geometric resolution based on the 3D processing domain and the semantic one based on the semantic web technology. Such strategy can be divided in two main steps: The first step is the geometric quantification, detection and recognition of the different existent objects in the coarse model. In this phase, the purpose of the processing is the detection of the defined objects in the coarse model. This is ensured by linking the high level semantic object definition in the coarse model and the correspondent portion of the point clouds. The second one aims at the semantic characterization of new objects in point clouds is based on the topologic relations. The inference will be based on the "Coarse model" CM and on the detected and localized objects. In this step, based on the relation´s interpretation and the interference rules management, new objects in the point cloud will be inferred and detected automatically (Figure 3).

In order to focus on our method for the combination of the semantic web technology and the 3D processing algorithms, Figure 4 illustrates an UML sequence diagram that represents the general design of the proposed solution. Hence, the purpose is to create a more flexible, easily extended approach where algorithms will be executed reasonably and adaptively on particular situations. The system architecture is divided into four actors: the data base, the 3D processing, the WiDop processing and the knowledge base.

To simplify the illustration, we will use a single data set type. In fact, we are limited in working on point clouds generated by a laser scanner. This does not mean that we will not profit from others resources like images, panoramic images, videos, etc. For this reason, the mentioned source presenting the fourth actor in the diagram is a laser scanner providing millions of point clouds. For the rest of the section, the real mechanism related to our solution will be disambiguated in details beginning by how our ontology is created, how knowledge are linked to the 3D processing algorithms arriving to how objects are detected and semantic model is updated.

A. The Ontology Creation

The WiDop project deals with the creation of an ontology corresponding to the project requirements. In this field, two different strategies for the ontology creation can be used. In the first one, the ontology is created manually depending on our vision and on the business knowledge provided by the specialists of the domain. Such ontology will look like a bottom up ontology [START_REF] Van Der Vet | Bottom-up construction of ontologies[END_REF], [START_REF] Hare | Bridging the Semantic Gap in Multimedia Information Retrieval: Top-down and Bottom-up approaches[END_REF], very precise and designed for a specific domain. In the second one, it can be automatically generated based on different sources like ontologies from different domains such as the transport, the railway and the geometric ones [START_REF] Stumme | Ontology merging for federated ontologies on the semantic web[END_REF]. The generation of the ontology can be also done based on software's packages thanks to many tools like the XML2OWL [START_REF] Bohring | Mapping XML to OWL ontologies[END_REF], [START_REF] Cruz | Ontology Enrichment and Automatic Population From XML Data[END_REF]. It serves to map XML files provided from Metronome Db Clear Suite software used for the management of the Deutsche Bahn point cloud´s, allowing a manual tagging of the different selected elements and describing the general structure for the railway domain to an OWL file. It can also be ensured by the IFC/XML tools mapping IFC files for the building management structure to OWL one. From our point of view, the WiDop ontology must respect the applied areas specification (railway or Fraport). Based on this observation, our ontology is created automatically in order to have a general model then adapted manually to respect the real scene characteristics. The schema extracted from the XML data base provided from the DB Clear suite software, will be exploited to facilitate the automatic population of our ontology. Once our knowledge base is created and populated, it will be used as an entry for the WiDop project (Figure 5).

B. Integrating Knowledge in 3D object detection

The proposed approach couples the semantic web technology represented by the knowledge to the 3D processing one represented by the 3D processing algorithms. Let's remember that the idea behind this project is to direct, adapt and select the most suitable algorithms based on the objects characteristics. In fact, one algorithm could not detect and recognize different existent objects in the 3D point clouds, since they are distinguished by different shapes, size and capture condition. The role of knowledge is to provide not only the object's characteristics (shape, size, color, etc.) but also object's status (visibility, correlation) to algorithmic part, in order to adjust its parameters to adapt with current situation, Table 1. Based on theses observation, we draw links from algorithms to objects based on the similar characteristics, as Figure 6 shows. The knowledge part controls one or more algorithms for the detection of objects. In order to carry out this detection, we benefit from the experience of experts in 3D processing. This experience helps to find a match between the object's characteristics and the algorithm's characteristics. Actually, a certain algorithm can be used for the detection of a certain object in a certain context. The set of characteristics are determined by the object's properties such as geometrical features and appearance. Then, the role of the knowledge is also to provide the algorithms that can detect and recognize these characteristics. These characteristics are considered as values and it can change the parameters of the algorithms. After the detection of an object, there is a module that gives a feedback about the status of the detected object according to the knowledge part and in order to adjust the algorithms to improve the robustness. Due to these frequent updates, the combination of knowledge and the 3D processing becomes relevant and flexible, c.f. Table1.

C. The Geometry Processing

The third part in this model is the digital treatments. This part will focus on the object detection based on the prior knowledge and the selected algorithm. As seen in Figure 4, once the algorithms are affected, the 3D processing layer will provide the generated point clouds from the laser scanners, it will also be provided with the different pieces of information relative to each object in the ontology. The 3D layer must have as information:

• The object label Depending on the object complexity, there are two possible scenarios. In the case of a low complexity rate, the objects can be detected automatically based on a template matching algorithm [START_REF] Kenue | LANELOK: Detection of lane boundaries and vehicle tracking using image-processing techniques-part II: Template matching algorithms[END_REF]. Else, the objects will be decomposed into elementary sub-objects as shown in the area B of Figure 4. Once detected, an evaluation process will estimate the detection quality rate (Figure 4, area C), and a topological reconstruction of the root element will be executed (Figure 4, area D). Once the coarse model elements are detected and recognized, (Figure 4, area E), the semantic research of new objects step is stimulated.

D. The Semantic Qualification

The described technique for the geometric qualification of the coarse model above aims at the detection of the maximum existing elements in the CM. Normally, a real scene should always contain extra object or unexpected one. To ensure a high detection quality rate, we suggest a second main module for our strategy aiming to identify new object in the coarse model. In fact, knowledge contains a reasoning capacity able to infer logical consequences from a set of asserted facts. Our model will be able to infer new objects and relations based on the coarse model topological relation and on the detected and identified elements (Figure 4, area F).

VI. CONCLUSION AND FUTURE WORK

The proposed approach for 3D object recognition in point clouds labeled "Mixed Strategy" present our initial work and vision on the project. It aims to improve the object localization and the scene reconstruction leading to a more robust and efficient processing of 3D point clouds and image data since it is based on interaction between two complementary domains, the semantic web and the 3D processing one via an intermediary layer labeled WiDop processing.

The integration of knowledge into 3D processing is a promising solution. It could make the object detection algorithms more robust, flexible and adaptive in the different circumstances through the knowledge guidance via a new mechanism under construction named "3D processing rules". Such mechanism aims to connect ontology to 3d processing algorithm via new Built-Ins. Once executed, these rules will query the ontology and the point clouds via the activation and the instantiation of the most suitable 3D processing algorithm.

Figure 1 .

 1 Figure 1. Automatic processing compared to the manual one.

Figure 2 .

 2 Figure 2. Overview system

Figure 3 .

 3 Figure 3. The mixed strategy, a system overview.

Figure 4 .

 4 Figure 4. The sequence diagram of interactions between the laser scanner, the 3D processing,the knwoldege processing and the knowledge base.

Figure 5 .

 5 Figure 5. Portion of the developped ontology describing the "Algorithm" class

Figure 6 .

 6 Figure 6. Linking algorithms and objects.

TABLE 1 .

 1 THE CHARACTERISTICS LIST OF ALGORITHM'S AND OBJECT'S

		INPUT
	No	Characteristics
	1	Geometry (plane, sphere, arc)
	2	Corner
	3	2D boundary
	4	Size
	5	Orientation
	6	Appearance (colour, surface material)
	7	Visibility
	8	Correlative position

  • The object location coordinate • The object spatial coordinate • The eventual 3D shape of the object • The sub-elements composing the object • The object complexity rate • The most suitable detection algorithm to use • …….

SEMAPRO 2010 : The Fourth International Conference on Advances in Semantic Processing Copyright (c) IARIA, 2010 ISBN: 978-1-61208-104-5

Copyright (c) IARIA, 2010 ISBN: 978-1-61208-104-5

ACKNOWLEDGMENT

The work presented in this paper is part of the research project WiDOP -Wissensbasierte Detektion von Objekten in Punktwolken für Anwendungen im Ingenieurbereich, funded by the German Federal Ministry for Research and Education (grant no. 1758X09). Partners in the project are Metronom Automation GmbH and DB Netz AG (for the railway domain) and Fraport AG (for the facility management domain).


Thierry Paul

Recent results in semiclassical approximation with rough potentials

Recent results in semiclassical approximation with rough potentials

T. Paul

Quantum Mechanics was invented for stability reasons. In fact it is striking to notice the difference of regularity that needs the potential of a Schrödinger operator to insure unitary of the quantum flow (e.g. V ∈ L 1 loc , limǫ→0 sup x |x-y|≤ǫ |x-y| 2-N |V (y)|dy = 0) compared to the classical Cauchy-Lipshitz condition for vector fields.

On the other hand, tremendous progress have been done in the last 25 years concerning the theory of ODEs using PDE's methods: extension of the Cauchy-Lipshitz condition to Sobolev ones (DiPerna-Lions 1989) and BV vector fields (Bouchut for the Hamiltonian case 2001 and Ambrosio for the general case 2004) have been proved to provide well-posedness of the classical flow almost everywhere, through uniqueness result for the corresponding Liouville equation in the space

L ∞ + ([0, T ]; L 1 (R 2n )∩L ∞ (R 2n
)). Under these regularity conditions on the potential (in addition to some growing at infinity) the Schrödinger equation is well posed for all positive values of the Planck constant and it is therefore natural to ask what is happening at the classical limit. As we will see, different answers will be given, according to the choices we make first on the topology of the convergence, and secondly on the asymptotic properties of the initial datum. The general idea of the results we are going to present here can be summarized as follows:

For some V / ∈ C 1,1 both the quantum and the classical exist and the diPerna-Lions-Ambrosio flow is the classical limit of the quantum flow for non concentrating initial data.

For concentrating initial data the multivalued bicharacteristics are the classical limit of the quantum flow.

All the results presented here will use a quantum formalism on phase space, thanks to the notion of Wigner function. More precisely we will be concerned with the so-called Schrödinger and von Neumann equation

iǫ∂tψ = (-ǫ 2 ∆ + V )ψ and ∂tD = 1 iǫ [-ǫ 2 ∆ + V, D] with ψ t=0 ∈ L 2 (R n ) and D t=0 ≥ 0, T rD t=0 = 1 (density matrix, e.g. D 0 = |ψ 0 ψ 0 |).
And we will consider the Wigner function associated to D t (e.g. = |ψ t ψ t |), defined by

W ǫ D(x, p) := 1 (2π) n R n D t (x + ǫ 2 yx - ǫ 2
y)e -ipy dy 1 where D t (x, y) is the integral kernel of D t (e.g. = ψ t (x)ψ t (y) in which case we write W ǫ ψ t ǫ ). The well-known lack of positivity of W ǫ suggests, in order to study evolution in spaces like L ∞ + , to use the so-called Husimi function of D t , a mollification of W ǫ defined as W ǫ D := e ǫ∆ R 2n W ǫ D which happens to be positive. But the only bound we have for

W ǫ D is W ǫ D L ∞ ≤ ǫ -n
TrD, unuseful for the L ∞ condition needed for the existence of the classical solution. We formulate the Conjecture: For an ǫ-dependant family Dǫ of density matrices we have

TrDǫ = 1 =⇒ sup ǫ>0 W ǫ Dǫ L ∞ = +∞.
In the general case of a potential whose gradient is BV, the first idea will be to smeared out the initial conditions and consider a family of vectors ψ 0 ǫ,w , w belonging to a probability space (W, F, P). Under the general assumptions

Assumptions on V

Assumptions on initial datum globally bounded, locally Lipschitz

ψ ǫ 0,w ∈ H 2 (R n ; C) ∇U b ∈ BV loc (R n ; R n ) sup ǫ>0 W R n |Hǫψ 0 ǫ,w | 2 dx dP(w) < ∞ ess sup x∈R n |∇U b (x)| 1+|x| < +∞ W |ψ 0 ǫ,w >< ψ 0 ǫ,w | dP(w) ≤ ǫ n Id +f inite repulsive Coulomb singularities lim ǫ↓0 W ǫ ψ 0 ǫ,w = i(w) ∈ P(R d ) for P -a.e. w ∈ W.
we have, for any bounded distance dP inducing the weak topology in P(R 2n ), the

Theorem 0.1 ([1]). lim ǫ→0 W sup t∈[-T,T ] dP W ǫ ψ t ǫ,w ), µ(t, i(w)) dP(w) = 0,
where µ(t, ν) is a (regular Lagrangian) flow on P(P(R 2n )) "solving" the Liouville equation.

In the case of the von Neumann equation, a more direct result can be obtained.

Assumptions on V Assumptions on initial datum globally bounded, locally Lipschitz sup ǫ∈(0,1)

Tr(H 2 ǫ D o ǫ ) < +∞ ∇U b ∈ BV loc (R n ; R n ) D o ǫ ≤ ǫ n Id ess sup x∈R n |∇U b (x)| 1+|x| < +∞ w -limǫ→0 W ǫ D 0 ǫ = W 0 0 ∈ PR 2n
Theorem 0.2 ([3]). Let dP be any bounded distance inducing the weak topology in P(R 2n ). Then

lim ǫ→0 sup [0,T ] dP ( W ǫ D t ǫ , W 0 t ) = 0, W 0 t is the unique solution in L ∞ + ([0, T ]; L 1 (R 2n ) ∩ L ∞ (R 2n
)) of the Liouville equation. The next result concerns the semiclassical approximation in strong topology. Let us denote V := e ǫ∆ R n V and suppose:

(new) Assumptions on V (new) Assumptions on initial datum | V (S)| |S| 2 1+|S| 2 dS < ∞ W ǫ 0 ∈ H 2 (R n ) |S|∈(a,b) | V (S)| |S| m dS ≤ C b m-1-θ -a m-1-θ if ∂tρ + k∂xρ -∂x V • ∂xρ = 0, ρt=0 := W ǫ 0 m = 0, 1, 2, 0 < θ < 1 ∃T > 0, δ ∈ (0, θ 2+θ ) such that ||ρ(t)|| H 2 = O(ε -δ ||W ε 0 || L 2 ) for t ∈ [0, T ] Theorem 0.3 ([2]). Let ρ ǫ 1 be the solution of ∂tρ ǫ 1 + k∂xρ ǫ 1 -∂x V • ∂xρ ǫ 1 = 0. W ǫ t := W ǫ D t ǫ satisfies, uniformly on [0, T ], ||W ǫ t -ρ ε 1 (t)|| L 2 = O(ε κ ||W ε 0 || L 2 ), κ = min{ 1 + θ 2 -1, θ 2 + θ -δ }.
Let us finally give a 1D example where the lack of unicity will be crucial.

Let V be a confining potential such that V = -|x| 1+θ near 0. Near (0, 0) we obtain two solutions of the Hamiltonian flow:

(X ± (t), P ± (t)) = (±c0t ν , ±c0νt ν-1 ), ν = 2 1 -θ and c0 = (1 -θ) 2 2 1-θ
, plus a continuum family of solutions obtained by not moving up to any value t0 of the time and then starting to move according to (X ± (t -t0), P ± (t -t0)).

The question now is to know which one, out of this continuous family, is going to be selected by the classical limit. The answer is given by the following result.

Theorem 0.4 ([2]). Let W ε D 0 ǫ (x, k) = λ 7+3θ 30 w(λ 1+θ 6 x, λ 1-θ 15 k), λ = log 1 ǫ , supp w ⊆ {|x| 2 + |k| 2 < 1}. Then ∃T > 0 s.t. ∀t ∈ [0, T ], W ǫ D t ǫ converges in weak- * sense to W 0 t = c+δ (X + (t),P + (t)) + c-δ (X -(t),P -(t)) , with c± = ±x>0 w(x, k)dxdk.
What these results show is the fact that, at the contrary to the case where the underlying classical dynamics is well-posed, the classical limit of the quantum evolution with non regular (i.e. not providing uniqueness of the classical flow) potentials is not unique, and depends on the family of initial conditions itself, and not anymore only on their limit.

For non concentrating data the classical limit, in the general case of a potential whose gradient is BV, is driven (in the two senses expressed by Theorems 0.1 and 0.2) by the DiPerna-Lions-Bouchut-Ambrosio flow.

Slowly concentrating data (Theorem 0.4) provide situations where the classical limit is ubiquitous, and follows several of the non unique bicharateritics, a typical quantum feature surviving, in this situation, the classical limit. It is important to remark that the speed of concentration governs the selections of the remaining trajectories. The case of fast concentration, in particular the pure states situations, is still open.


Irène Charon
email: charon@telecom-paristech.fr

Olivier Hudry
email: hudry@telecom-paristech.fr

Antoine Lobstein
email: lobstein@telecom-paristech.fr

Taille minimum des codes identifiants dans les graphes différant par un sommet ou une arête Minimum Sizes of Identifying Codes in Graphs Differing by One Edge or One Vertex

Keywords: Théorie des graphes, Graphes sans jumeaux, Graphes identifiables, Codes identifiants Graph Theory, Twin-Free Graphs, Identifiable Graphs, Identifying Codes

Soit G un graphe simple, non orienté, d'ensemble de sommets

sont tous non vides et distincts. Un graphe G admettant un code r-identifiant est dit sans r-jumeaux, et dans ce cas la taille d'un plus petit code r-identifiant dans G est dénotée par γ r (G).

Nous étudions le problème structurel suivant : soit G un graphe sans r-jumeaux, et G * un graphe obtenu à partir de G en ajoutant ou en retirant un sommet, ou en ajoutant ou en retirant une arête. Si G * est encore sans r-jumeaux, nous comparons le comportement de γ r (G) et γ r (G * ), et établissons des résultats sur leurs possibles différence et rapport.

Introduction

We introduce basic definitions and notation for graphs, for which we refer to, e.g., [START_REF] Berge | English translation: Graphs[END_REF] and [START_REF] Diestel | Graph Theory[END_REF], and for identifying codes (see [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] and the bibliography at [START_REF] Lobstein | A bibliography on watching systems, identifying, locating-dominating and discriminating codes in graphs[END_REF]).

We shall denote by G = (V, E) a simple, undirected graph with vertex set V and edge set E, where an edge between x ∈ V and y ∈ V is indifferently denoted by {x, y}, {y, x}, xy or yx. The order of a graph is its number of vertices |V |.

A path P n = x 1 x 2 . . . x n is a sequence of n distinct vertices x i , 1 ≤ i ≤ n, such that x i x i+1 is an edge for i ∈ {1, 2, . . . , n -1}. The length of P n is its number of edges, n -1. A cycle C n = x 1 x 2 . . . x n is a sequence of n distinct vertices x i , 1 ≤ i ≤ n, where x i x i+1 is an edge for i ∈ {1, 2, . . . , n -1}, and x n x 1 is also an edge; its length is n.

A graph G is called connected if for any two vertices x and y, there is a path between them. It is called disconnected otherwise. In a connected graph G, we can define the distance between any two vertices x and y, denoted by d G (x, y), as the length of any shortest path between x and y, since such a path exists. This definition can be extended to disconnected graphs, using the convention that d G (x, y) = +∞ if there is no path between x and y.

For any vertex v ∈ V and integer r ≥ 1, the ball of radius r and centre v, denoted by B G,r (v), is the set of vertices within distance r from v:

B G,r (v) = {x ∈ V : d G (v, x) ≤ r}.
Two vertices x and y such that B G,r (x) = B G,r (y) are called (G, r)-twins; if G has no (G, r)-twins, that is, if ∀x, y ∈ V with x = y, B G,r (x) = B G,r (y), then we say that G is r-twin-free.

Whenever two vertices x and y are within distance r from each other in G, i.e., x ∈ B G,r (y) and y ∈ B G,r (x), we say that x and y r-cover each other. When three vertices x, y, z are such that x ∈ B G,r (z) and y / ∈ B G,r (z), we say that z r-separates x and y in G. A set is said to r-separate x and y in G if it contains at least one vertex which does.

A code C is simply a subset of V , and its elements are called codewords. For each vertex v ∈ V , the r-identifying set of v, with respect to C, is the set of codewords r-covering v, and is denoted by I G,C,r (v):

I G,C,r (v) = B G,r (v) ∩ C.
We say that C is an r-identifying code [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] if all the sets I G,C,r (v), v ∈ V , are nonempty and distinct: in other words, every vertex is r-covered by at least one codeword, and every pair of vertices is r-separated by at least one codeword.

It is quite easy to observe that a graph G admits an r-identifying code if and only if G is r-twin-free; this is why r-twin-free graphs are also sometimes called r-identifiable.

When G is r-twin-free, we denote by γ r (G) the cardinality of a smallest r-identifying code in G. The search for the smallest r-identifying code in given graphs or families of graphs is an important part of the studies devoted to identifying codes.

In this preprint and the forthcoming [START_REF] Charon | Minimum sizes of identifying codes in graphs differing by one edge[END_REF] and [START_REF] Charon | Minimum sizes of identifying codes in graphs differing by one vertex[END_REF], we are interested in the following issue: let G be an r-twin-free graph, and G * be a graph obtained from G by adding or deleting one vertex, or by adding or deleting one edge. Now, if G * is still r-twin-free, what can be said about γ r (G) compared to γ r (G * )? More specifically, we shall study their difference and, when appropriate, their ratio, γ r (G)γ r (G * ) and γ r (G) γ r (G * ) , as functions of the order of the graph G, and r.

Note that a partial answer to the issue of knowing the conditions for which an r-twin-free graph remains so when one vertex is removed was given in [START_REF] Charon | Structural properties of twin-free graphs[END_REF] and [START_REF] Charon | On the structure of identifiable graphs[END_REF]: any 1-twin-free graph with at least four vertices always possesses at least one vertex whose deletion leaves the graph 1-twin-free; for any r ≥ 1, any r-twin-free tree with at least 2r + 2 vertices always possesses at least one vertex whose deletion leaves the graph r-twin-free; on ther other hand, for any r ≥ 3, there exist r-twin-free graphs such that the deletion of any vertex makes the graph not r-twin-free. The case r = 2 remains open.

Of what interest this study is, can be illustrated by the watching of a museum: we place ourselves in the case r = 1 and assume that we have to protect a museum, or any other type of premises, using smoke detectors. The museum can be viewed as a graph, where the vertices represent the rooms, and the edges, the doors or corridors between rooms. The detectors are located in some of the rooms and give the alarm whenever there is smoke in their room or in one of the adjacent rooms. If there is smoke in one room and if the detectors are located in rooms corresponding to a 1-identifying code, then, only by knowing which detectors gave the alarm, we can identify the room where someone is smoking.

Of course we want to use as few detectors as possible. Now, what are the consequences, beneficial or not, of closing or opening one room or one door? This is exactly what we investigate here, in the more general case when r can take values other than 1.

In the conclusion of [START_REF] Roberts | Locating sensors in paths and cycles: the case of 2-identifying codes[END_REF], it is already observed, somewhat paradoxically, that a cycle with one vertex less can require more codewords/detectors. In the sequel, we shall exhibit examples of large variations for the minimum size of an identifying code.

A related issue is that of t-edge-robust identifying codes, which remain identifying when at most t edges are added or deleted, in any possible way; see, e.g., [START_REF] Honkala | An optimal edge-robust identifying code in the triangular lattice[END_REF]- [START_REF] Honkala | On identifying codes that are robust against edge changes[END_REF], [START_REF] Laihonen | Optimal t-edge-robust r-identifying codes in the king lattice[END_REF] or [START_REF] Laihonen | On edge-robust (1, ≤ )-identifying codes in binary Hamming spaces[END_REF].

Let us mention that in the sequel, we shall consider two cases, (i) both graphs G ands G * are connected, (ii) the graph with one edge less or one vertex less may be disconnected, and observe some significant differences. For r = 1, this distinction is meaningless, since a vertex v which is linked to all the other vertices guarantees that the graph is connected and does not change anything as far as 1-identification is concerned, in the sense given by the following two easy lemmata.

Lemma 1 If G = (V, E) is not connected and 1-twin-free, and if G * is the graph obtained by adding to G a vertex v which is linked to all the vertices in V , then G * is (connected and) 1-twin-free.

Proof. First, v is the only vertex in G * which is connected to every vertex in V . Second, for all vertices x ∈ V , we have B G * ,1 (x) = B G,1 (x) ∪ {v}, so, by hypothesis on G, these balls are distinct.

Lemma 2 If a graph G = (V, E) is 1-twin-free and contains a vertex v which is linked to all the other vertices, then there is an optimal 1-identifying code C not containing v.

Proof. Assume that an optimal 1-identifying code C contains v. Since v cannot 1-separate any pair of vertices in G, its only purpose as a codeword is to 1-cover some vertices not 1-covered by any other codeword; because these vertices are 1-separated by C, only one of them, which we denote by x, can be such that I G,C,1 (x) = {v}. Then C \ {v} ∪ {x} is also optimal and 1-identifying.

Before we proceed, we still need some additional definitions and notation, we state one theorem on cycles, and we also give two lemmata which, although trivial, will prove useful in the sequel, even implicitly.

For a graph G = (V, E) and a vertex v ∈ V , we denote by G v the graph with vertex set V and edge set E , where

V = V \ {v}, E = {xy ∈ E : x ∈ V , y ∈ V }.
When we delete the edge e ∈ E in a graph G = (V, E), we denote the resulting subgraph by G e = (V, E e ).

In both parts, I and II, we shall use the following result on cycles of even length.

Theorem 3 [START_REF] Bertrand | LOBSTEIN: Identifying and locating-dominating codes on chains and cycles[END_REF] For all r ≥ 1 and for all even n, n ≥ 2r + 4, we have:

γ r (C n ) = n 2 .
If G = (V, E) is a graph and S is a subset of V , we say that two vertices x ∈ V and y ∈ V are (G, S, r)-twins if

I G,S,r (x) = I G,S,r (y).
In other words, x and y are not r-separated by S in G. By definition, if C is r-identifying in G, then no (G, C, r)-twins exist.

Lemma 4 [(G, S, r)-twin transitivity] In a graph G = (V, E), if x, y, z are three distinct vertices, if S is a subset of V , if x and y are (G, S, r)-twins and if y and z are (G, S, r)-twins, then x and z are (G, S, r)-twins.

Lemma 5 If C is an r-identifying code in a graph G = (V, E), then so is any set S such that C ⊆ S ⊆ V.

Part I: Addition and deletion of one vertex

We present the main six results of this part in the following way. In Section 3 we consider the case r = 1: we study how large γ 1 (G x )γ 1 (G) can be (Proposition 6), then Theorem 7 states exactly how small this difference can be (namely, -1). In Section 4, we study how small γ r (G x )γ r (G) can be for any r ≥ 2 (Proposition 10) and it so happens that the graphs we use are connected; then we study how large this difference can be, in the following three cases: (i) r ≥ 2, r is even and the graphs are connected (Proposition 12 in Section 4.1); (ii) r ≥ 3, r is odd and the graphs are connected (Proposition 14 in Section 4.2); (iii) r ≥ 2 and the graph G x is disconnected (Proposition 16 in Section 4.3). In all these sections, the number n represents the order of either G or G x . A general conclusion recapitulates our results.

The case r = 1

Proposition 6 There exist two (connected) 1-twin-free graphs G and G x , with n = 4β + 6 and 4β + 5 vertices respectively, such that γ 1 (G) = 2β + 3 and γ 1 (G x ) = 3β + 3, where β is any integer greater than or equal to 1.

Remark preceding the proof. The difference γ 1 (G x )γ 1 (G) = β can be made arbitrarily large; in terms of n, the order of G, we can see that we have:

γ 1 (G x ) -γ 1 (G) = n -6 4 . (1)
We can also consider the ratio between γ 1 (G x ) and γ 1 (G):

γ 1 (G x ) γ 1 (G) = 3n -6 2n , (2)
which is equivalent to 3 2 when β, or n, goes to infinity. An open question is to know whether these difference or ratio can be made larger.

On the other hand, we shall see in Theorem 7 that any two 1-twin-free graphs H and

H x must satisfy γ 1 (H) -γ 1 (H x ) ≤ 1.
Proof of Proposition 6. Let β ≥ 1 be an integer.

For 1 ≤ i ≤ β + 1, we consider copies (V i , E i ) of the path P 4 , with the following notation:

V i = {v i,1 , v i,2 , v i,3 , v i,4 }, and E i = {{v i,j , v i,j+1 } : 1 ≤ j ≤ 3}. Let G = (V, E), where V = ∪ 1≤i≤β+1 V i ∪ {x} ∪ {y} and v 1,1 v 1,1 v 1,4 v 3,4 v 3,2 y (b) G v 1,4 v 3,4 v 3,2 x y G (a)
x Figure 1: The graphs G and G x , for β = 2, in Proposition 6.

E = ∪ 1≤i≤β+1 E i ∪ {{y, s} : s ∈ V \ {y}} ∪ {{x, v i,2 } : 1 ≤ i ≤ β + 1},
see Figure 1(a). Note that the vertex y is used only to make sure that G x is connected, which is not strictly necessary; the same construction could have been done without y, with G a tree and G x a forest.

Then G has n = 4β + 6 vertices, and we claim that: (a) γ 1 (G) = 2β + 3, and (b) γ 1 (G x ) = 3β + 3, from which (1) and (2) follow.

Proof of (a). The code

{x} ∪ {v i,2 , v i,3 : 1 ≤ i ≤ β + 1}
is clearly 1-identifying in G. To establish the lower bound, we use Lemma 2 and assume that C is an optimal 1-identifying code not containing y. Then we need at least two codewords on each copy of P 4 , because each end must be 1-covered by at least one codeword. Finally, since γ 1 (P 4 ) = 3, it is straightforward to see that the best we can do is to take advantage of x, take it as a codeword, and have 2β + 3 codewords.

Proof of (b). Thanks to Lemma 2, this is obvious, using that γ 1 (P 4 ) = 3.

Note that, here and also in Proposition 10, we could have contented ourselves with inequalities, here γ 1 (G) ≤ 2β + 3 and γ 1 (G x ) ≥ 3β + 3, so as to obtain

γ 1 (G x ) -γ 1 (G) ≥ β = n -6 4 and γ 1 (G x ) γ 1 (G) ≥ 3β + 3 2β + 3 = 3n -6 2n .
Theorem 7 Let G = (V, E) be any 1-twin-free graph with at least three vertices. For any vertex x ∈ V such that G x is 1-twin-free, we have:

γ 1 (G x ) ≥ γ 1 (G) -1. (3)
Proof. Cf. [START_REF] Foucaud | Extremal graphs for the identifying code problem[END_REF]Prop. 3]. For completeness, we still give a proof. Let x ∈ V be such that G x is 1-twin-free. Let C x be a minimum 1-identifying code in G x : |C x | = γ 1 (G x ). There are two cases: either (a)

x is not 1-covered (in G) by any codeword of C x , or (b) x is 1-covered (in G) by at least one codeword of C x . (a) In this case, let C = C x ∪ {x}. Then C is clearly 1-identifying in G (in particular, thanks to Lemma 5); therefore, γ 1 (G) ≤ γ 1 (G x ) + 1. (b) x is 1-covered by y ∈ C x . If C x is 1-identifying in G, then γ 1 (G) ≤ γ 1 (G x
), and we are done. So we assume that C x is not 1-identifying in G. This means that either (i) at least one vertex in G is not 1-covered by C x , or (ii) at least two vertices in G are not 1-separated by C x .

(i) Since C x 1-covers any vertex in G x and x is linked to y ∈ C x , this case is impossible.

(ii) Let u, v ∈ V be two distinct vertices which are not 1-separated by C x . One of them is necessarily x, and without loss of generality, we assume that x = u. Now, v is unique by Lemma 4: C x is not 1-identifying in G only because one pair of vertices, x and v, is not 1-separated by C x .

Since G is 1-twin-free, there is a vertex z which 1-covers exactly one of the vertices v and x. We set C = C x ∪ {z}, and we obtain a 1-identifying code in G, so

γ 1 (G) ≤ γ 1 (G x ) + 1. Corollary 8 If γ 1 (G x ) ≤ a and γ 1 (G) ≥ a + 1, then γ 1 (G x ) = a and γ 1 (G) = a + 1.

Note that we made no assumption on the connectivity of

G or G x . Examples where γ 1 (G x ) = γ 1 (G) -1, or γ 1 (G x ) = γ 1 (G)
, are numerous and easy to find.

Conclusion 9

Provided that the graphs considered are 1-twin-free, we can see, using Proposition 6 and Theorem 7, that γ 1 (G x )γ 1 (G) cannot be smaller than -1, but examples exist where it can be as large as, approximately, n 4 , and where the ratio γ 1 (G x ) γ 1 (G) can be as large as, approximately, 3 2 .

4 The case r ≥ 2

Things are different for r ≥ 2, since we can exhibit pairs of graphs (G, G x ) proving that γ r (G)γ r (G x ) can be arbitrarily large or small. We first give a result with γ r (G)γ r (G x ) arbitrarily large. Note that we obtain this result with connected graphs: we found no better with disconnected graphs.

Proposition 10 There exist two (connected) r-twin-free graphs G x and G, with n = pr + 1 and pr + 2 vertices respectively, such that where p is any integer greater than or equal to 3.

γ r (G x ) = p + 2r -3 = n + 2r 2 -3r -1 r and γ r (G) = r(p -1) + 1 = n -r, v 1,1 v p,r v p,2 v 1,r x v v p,r v p,2 v v 1,r v 1,1 (a)
Remark preceding the proof. The difference

γ r (G) -γ r (G x ) = p(r -1) -3r + 4
can be made arbitrarily large; in terms of n, the number of vertices of G x , we can see that we have:

γ r (G) -γ r (G x ) = (n -3r)(r -1) + 1 r , (4)
which is equivalent to n(r-1) r when r is fixed and n goes to infinity. Also:

γ r (G) γ r (G x ) = r(n -r) n + 2r 2 -3r -1 , (5)
which is equivalent to r when we increase n. Again, is it possible to improve on (4) or ( 5)?

Proof of Proposition 10. Let r ≥ 2 and p ≥ 3 be integers; we put the cart before the horse and, before defining G, we describe G x in the following informal way, partially illustrated in Figure 2(a): G x consists of p copies of the path P r , and in each copy the last vertex is linked to v. This graph has n = pr + 1 vertices. Next, we construct the graph G consisting of G x to which we add one vertex x, linked to each first vertex of all the copies of P r . See Figure 2(b). We claim that: (a) γ r (G x ) = p + 2r -3, and (b) γ r (G) = r(p -1) + 1, from which (4) and ( 5) follow.

Proof of (a). The code

C = {v 1,i : 2 ≤ i ≤ r} ∪ {v 2,i : 1 ≤ i ≤ r} ∪ {v j,1 : 3 ≤ j ≤ p}, (6)
i.e., the code consisting of all the vertices of the first two copies of P r , except v 1,1 , and the first vertex of each of the following copies, is r-identifying in G x ; this it is straightforward to check. So γ r (G x ) ≤ (r -1) + r + (p -2) = p + 2r -3. We now prove that γ r (G x ) ≥ p + 2r -3. The following two observations will be useful. For 1 ≤ i ≤ p and 2 ≤ k ≤ r, we have:

B G x ,r (v i,r-k+1 )∆B G x ,r (v i,r-k+2 ) = {v j,k : 1 ≤ j ≤ p, j = i}, (7)
where ∆ stands for the symmetric difference, and for 1 ≤ i < j ≤ p:

B G x ,r (v i,r )∆B G x ,r (v j,r ) = {v i,1 , v j,1 }. ( 8
)
The consequences are immediate. First, in order to have the vertices v i,r , 1 ≤ i ≤ p, pairwise r-separated in G x , we see by [START_REF] Charon | Extremal cardinalities for identifying and locating-dominating codes in graphs[END_REF] that we need at least p -1 codewords among the p vertices v i,1 ; second, for k fixed between 2 and r, we see, using [START_REF] Charon | Possible cardinalities for identifying codes in graphs[END_REF], that we need at least two codewords among the p vertices v i,k . So γ r (G x ) ≥ (p -1) + 2(r -1) = p + 2r -3, and Claim (a) is proved. Proof of (b). Note that in G, for i and j such that 1 ≤ i < j ≤ p, the set of vertices

{x} ∪ {v i,k : 1 ≤ k ≤ r} ∪ {v} ∪ {v j,k : 1 ≤ k ≤ r}
forms the cycle C 2r+2 , which is r-twin-free and is denoted by C(i, j). On such a cycle, we say that the vertex z is the opposite of the vertex y if z is the (only) vertex at distance r + 1 from y.

We claim that, for k fixed between 1 and r, among the p vertices v i,k , at least p -1 of them belong to any r-identifying code C in G. Indeed, assume on the contrary that two vertices, say v 1,k and v 2,k , are not in C; then their opposite vertices in C(1, 2), v 2,r-k+1 and v 1,r-k+1 respectively, cannot be r-separated by C.

Finally, the fact that B G,r (v)∆B G,r (x) = {v, x} shows that v or x belong to C, and finally γ r (G) ≥ (p -1)r + 1. On the other hand,

{v} ∪ {v i,k : 2 ≤ i ≤ p, 1 ≤ k ≤ r} is an r-identifying code in G, with size (p -1)r + 1, thus Claim (b) is proved.
Note that this code contains all the vertices in G, except the r + 1 vertices

x and v 1,k , 1 ≤ k ≤ r.

Conclusion 11

When r ≥ 2, Proposition 10 provides pairs of graphs proving that γ r (G x )γ r (G) can be, asymptotically, as small as approximately n(r-1) r , and γ r (G x ) γ r (G) can be, asymptotically, as small as approximately 1 r , and this can even be obtained with connected examples.

Then we turn to examples where γ r (G x )γ r (G) is arbitrarily large. We start with connected graphs, and have two subcases, r even and r odd.

Case of a connected graph G x and r ≥ 2, r even

Proposition 12 There exist two (connected) r-twin-free graphs G and G x , with n + 1 and n vertices respectively, such that

γ r (G x ) -γ r (G) ≥ n 4 -(r + 1), (9)
γ r (G x ) γ r (G) ≥ 2n n + 4r + 4 . ( 10
)
Remark preceding the proof. The two lower bounds ( 9) and ( 10) are equivalent to n/4 and 2 when n increases with respect to r. An open question is whether these two inequalities can be improved.

Proof of Proposition 12. Let r ≥ 2 be an even integer, and n be an (even) integer such that n = k • 2r, k ≥ 2; let G x = C n = x 1 x 2 . . . x n be the cycle of length n and G be the graph obtained from G x by adding the vertex x and linking it to the k vertices x j•2r , 1 ≤ j ≤ k. See Figure 3, which illustrates the case r = 6, k = 4, n = 48 and G has 49 vertices. We know by Theorem 3 that γ r (G x ) = n 2 , and we claim that

γ r (G) ≤ 1 + (k + 2) n 4k = n 4 + r + 1,
from which ( 9) and ( 10) follow. Proving this claim, by exhibiting an ridentifying code for G, is tedious and of no special interest; therefore, we content ourselves with showing how it works in the case r = 6, n = 48, hoping that this will help the reader to gain an insight into the general case. We consider a first set Let us consider the first three pairs, {x 48 , x 1 }, {x 2 , x 3 }, {x 4 , x 5 }. Using edges going through x, they can be 6-separated, for instance, by the vertices x 16 , x 14 and x 12 (see the large black circles), and these three vertices also 6separate the other pairs of (G, S, 6)-twins, except for {x 12 , x 13 }, {x 14 , x 15 }, {x 16 , x 17 }. These three pairs can however be 6-separated by three more codewords, for instance x 4 , x 2 and x 48 , see the black squares in Figure 3. Now the code C = S ∪ {x 12 , x 14 , x 16 , x 48 , x 2 , x 4 } is 6-identifying in G and has 1 + (4 × 3) + (2 × 3) = 19 codewords. In the general case,

S = {x, x 1 , x
S = {x} ∪ {x 1+j•2r , x 3+j•2r , . . . , x r-1+j•2r : 0 ≤ j ≤ k -1},
there are k × r 2 pairs of (G, S, r)-twins, and C can be chosen, for instance, as

C = S ∪ {x n , x 2 , . . . , x r-2 } ∪ {x 2r , x 2r+2 , . . . , x 2r+(r-2) }, which shows that the cardinality of C is 1 + (k × r 2 ) + (2 × r 2 ) = 1 + (k + 2) n 4k ,
and so γ r (G) ≤ 1 + (k + 2) n 4k .

Conclusion 13

When r is even, Proposition 12 gives pairs of connected graphs proving that γ r (G x )-γ r (G) can be, asymptotically, as large as approximately n 4 , and γ r (G x ) γ r (G) can be, asymptotically, as large as approximately 2.

4.2 Case of a connected graph G x and r ≥ 3, r odd Proposition 14 There exist two (connected) r-twin-free graphs G and G x , with n + 1 and n vertices respectively, such that

γ r (G x ) -γ r (G) ≥ n(3r -1) 12r -r, (11)
γ r (G x ) γ r (G) ≥ 6nr n(3r + 1) + 12r 2 . ( 12
)
Remark preceding the proof. An open question is to know whether these two inequalities can be improved. The two lower bounds are equivalent to n(3r-1) 12r

and 6r 3r+1 when r is fixed and n goes to infinity. Proof of Proposition 14. Let r ≥ 3 be an odd integer, and n be an (even) integer such that n = k • 2r, where k ≥ 3 is a multiple of 3; let G x = C n = x 1 x 2 . . . x n be the cycle of length n and G be the graph obtained from G x by adding the vertex x and linking it to the k vertices x j•2r , 1 ≤ j ≤ k. See Figure 4, which illustrates the case r = 5, k = 6, n = 60 and G has 61 vertices.

We know by Theorem 3 that γ r (G x ) = n 2 , and we claim that

γ r (G) ≤ n 4 + n 12r + r,
from which [START_REF] Chen | Identifying codes and locatingdominating sets on paths and cycles[END_REF] and ( 12) follow. Again, proving this claim is of no interest here, and we just show how it works in the case r = 5, n = 60. We consider a first set 4. Now in Case (i), all the vertices are 5-separated by the vertices in T \ S, and so are x 59 on the one hand and x 1 , x 2 on the other hand, as well as their symmetrical counterparts from Case (ii). The remaining pairs of (G, T , 5)-twins are {x 1 , x 2 }, {x 3 , x 4 } and the 10 pairs obtained by symmetry. As in the proof of Proposition 12, these handle very economically: the vertex x 60 5-separates the 5 pairs {x 13 , x 14 }, . . . , {x 53 , x 54 }, and so does x 2 for {x 11 , x 12 }, . . . , {x 51 , x 52 }; finally, {x 1 , x 2 } and {x 3 , x 4 } can be 5-separated, for instance, by x 10 and x 12 , see the black squares in Figure 4:

S = {x, x 1 , x
C = T ∪ {x 60 , x 2 , x 10 , x 12 }
is a 5-identifying code in G and has 1 + (6 × 2) + (4 × 1) + (2 × 2) = 21 codewords. In the general case,

S = {x} ∪ {x 1+j•2r , x 3+j•2r , . . . , x r-2+j•2r : 0 ≤ j ≤ k -1} contains 1 + (k × r-1
2 ) vertices; then

T = S ∪ {x r+j•2r : 0 ≤ j ≤ k -1, j not congruent to 2 modulo 3} contains |S| + 2k
3 elements, and finally we take

C = T ∪ {x n , x 2 , . . . , x r-3 } ∪ {x 2r , x 2r+2 , . . . , x 2r+(r-3) }, which shows that γ r (G) ≤ 1 + (k × r -1 2 ) + 2k 3 + (2 × r -1 2 ) = n 4 + n 12r + r.

Conclusion 15

When r ≥ 3 and r is odd, Proposition 14 gives pairs of connected graphs proving that γ r (G x )γ r (G) can be, asymptotically, as large as approximately n(3r-1) 12r , and γ r (G x ) γ r (G) can be, asymptotically, as large as approximately 6r 3r+1 . If we do not require to consider a connected graph G x , then we can obtain a much larger difference or ratio than in ( 9)-( 12), we need consider only one case, whatever the parity of r is, and moreover the construction is easy to understand; see next section.

Case of a disconnected graph G x and r ≥ 2, r even or odd

Proposition 16 There exist two graphs G and G x , with p(2r + 1) + 1 and n = p(2r + 1) vertices respectively, such that Remark preceding the proof. These two lower bounds are equivalent to n(2r-2) 2r+1 and r when n increases. Can they be improved? Proof of Proposition 16. Let r ≥ 2 and p ≥ 3 be integers; the graph G x consists of p copies of the path P 2r+1 , and G is obtained by adding the vertex x and linking it to all the middle vertices of the path copies, see Figure 5. We claim that: (a) γ r (G x ) = 2pr and (b) γ r (G) ≤ 2p + 2r, from which ( 13) and ( 14) follow.

γ r (G x ) -γ r (G) ≥ n(2r -2) 2r + 1 -2r, ( 13
) γ r (G x ) γ r (G) ≥ nr n + 4r 2 + 2r . ( 14
) v 1,1 v 1,2r+1 v 1,r+1 v p,2r+1
Proof of (a). The result comes from the obvious fact that γ r (P 2r+1 ) = 2r. Proof of (b). It is not difficult to check that

C = {x} ∪ {v i,1 , v i,2r+1 : 1 ≤ i ≤ p -1} ∪ {v p,j : 1 ≤ j ≤ 2r + 1}
is indeed r-identifying in G. Note however that, for simplicity, we chose to give the bound 2p + 2r, when actually, with a little more care, 2p + 2r -3 can be reached, which would improve only slightly on ( 13) and [START_REF] Gravier | On graphs having a V \ {x} set as an identifying code[END_REF].

Conclusion 17

Proposition 16 gives pairs of graphs (G, G x ), where G x is not connected, proving that γ r (G x )γ r (G) can be, asymptotically, as large as approximately n(2r-2) 2r+1 , and γ r (G x ) γ r (G) can be, asymptotically, as large as approximately r.

General conclusion

Table 1 recapitulates the results obtained in the previous sections, using in particular the partial conclusions 9, 11, 13, 15 and 17 at the end of each section; these are stated for n large with respect to r, so it doesn't matter to know if n is the order of G or of G x . We only consider the difference γ r (G x )γ r (G) and the ratio γ r (G x ) γ r (G) . r Concl. 17

r r comment γ r (G x ) -γ r (G) γ r (G x ) γ r (G) reference = 1 impossible to have < -
Table 1: The difference γ r (G x )γ r (G) and ratio γ r (G x ) γ r (G) , as functions of n and r.

Part II: Addition and deletion of one edge

This part is organized as follows. Section 6 is devoted to the case r = 1; here, the difference γ 1 (G e )γ 1 (G) must lie between -2 and +2. Then in the beginning of Section 7, we study how small γ r (G e )γ r (G) can be for any r ≥ 2, and it so happens that the graphs we use are connected; then we study how large this difference can be, when G e is connected (Section 7.1) and when G e is not connected (Section 7.2); in these three cases with r ≥ 2, we obtain bounds on γ r (G e )γ r (G) depending on r, namely -r, r -1 and 2r -3. A conclusion recapitulates our results. [START_REF] Charon | On the structure of identifiable graphs[END_REF] The case r = 1

The difference γ 1 (G e )γ 1 (G) can vary only inside the set {-2, -1, 0, 1, 2} (Theorem 22), and these five values can be reached (Examples 19, 21 and 23).

We first study how small γ 1 (G e )γ 1 (G) can be. Putting the cart before the horse, in the next theorem we first define G e , and only then, G.

Theorem 18

Let G e = (V, E e ) be a 1-twin-free graph with at least four vertices, let x and y be two distinct vertices in V such that e = xy / ∈ E e , and let G = (V, E) with E = E e ∪ {xy}. Assume that G is also 1-twin-free.

If C e is a 1-identifying code in G e , then there exists a

1-identifying code C in G with |C| ≤ |C e | + 2.
As a consequence, we have:

γ 1 (G e ) -γ 1 (G) ≥ -2. ( 15
)
Proof. Since we add an edge when going from G e to G, all vertices remain 1-covered, in G, by at least one codeword in C e . Since we only add the edge xy, only the balls of x and y are modified in G. As a consequence, only the following pairs are possible (G, C e , 1)-twins:

• x and y,

• x and u with u = x, u = y,

• y and v with v = x, v = y. Moreover, x and u , with u = u, u = x, u = y, cannot be (G, C e , 1)-twins since this would imply, by Lemma 4, that u and u are (G, C e , 1)-twins, hence (G e , C e , 1)-twins, which would contradict the fact that C e is 1-identifying in G e . The same is true for y and v , with v = v, v = x, v = y. So at most three pairs of (G, C e , 1)-twins can appear.

Similarly, if these three pairs of (G, C e , 1)-twins all do appear, then u and v are (G, C e , 1)-twins, which leads to the same contradiction, unless u = v. In this case, because G is 1-twin-free, we can pick an additional When at most two pairs of (G, C e , 1)-twins appear, then obviously with at most two more codewords added to C e we can 1-separate them.

Note that we made no assumption on the connectivity of G e . The following example shows that graphs G e and G with γ 1 (G) = γ 1 (G e ) + 2 do exist; we do not know if this is the smallest possible example.

Example 19

Let G e = (V, E e ) be the graph represented in Figure 6, and G the graph obtained by adding the edge e = xy. We claim that: (a) γ 1 (G e ) ≤ 10 and (b) γ 1 (G) ≥ 12, which by [START_REF] Honkala | An optimal edge-robust identifying code in the triangular lattice[END_REF]

implies that γ 1 (G) = 12 = γ 1 (G e ) + 2.
Proof of (a). It is quite straightforward to check that C e = {1, 3, x, 6, 8, 8 , 6 , y, 3 , 1 } is 1-identifying in G e . Hence γ 1 (G e ) ≤ 10.

Proof of (b). Let C be a 1-identifying code in G. Because 1 and 2 must be 1-separated by C, we have 3 ∈ C; and because 1 must be 1-covered by at least one codeword, we have 1 ∈ C or 2 ∈ C. Similarly, C contains 6, 6 , 3 and at least one element in each of the 2-sets {7, 8}, {8 , 7 } and {2 , 1 }, which amounts to eight codewords.

With simple arguments, we obtain the following fact:

• there are at least three codewords in {1, 2, 3, 4, x}.

The same is true for {x, 5, 6, 7, 8}, {y, 5 , 6 , 7 , 8 } and {y, 4 , 3 , 2 , 1 }. So, if neither x nor y belongs to C, there are at least 3 × 4 = 12 codewords, and we are done. If, on the other hand, both x and y belong to C, then we have already ten codewords, and still x, y and z are not 1-separated by any codeword; this will require two additional codewords, and again, |C| ≥ 12.

If we assume finally, without loss of generality, that x ∈ C and y / ∈ C, then we have already chosen (3 × 2) + 5 = 11 codewords: three in each of the sets {4 , 3 , 2 , 1 } and {5 , 6 , 7 , 8 }, one in each of the sets {1, 2} and {7, 8}, plus 3, 6 and x; still, x and z are not 1-separated by any codeword, so again we need at least twelve codewords, which proves Claim (b).

Next, we establish how large γ 1 (G e )γ 1 (G) can be.

Theorem 20 Let G = (V, E) be a 1-twin-free graph with at least four vertices, let x and y be two vertices in V such that e = xy ∈ E, and let G e = (V, E e ) with E e = E \ {xy}. Assume that G e is also 1-twin-free.

If C is a 1-identifying code in G, then there exists a 1-identifying code C e in G e with |C e | ≤ |C| + 2.

As a consequence, we have:

γ 1 (G e ) -γ 1 (G) ≤ 2. ( 16
)
Proof. We assume that C is not 1-identifying in G e anymore, otherwise we are done. There can be two reasons why C is not 1-identifying: 1) at least one of the two vertices x and y, say x, is not 1-covered by any codeword anymore:

B G e ,1 (x) ∩ C = ∅ = (B G,1 (x) \ {y}) ∩ C, which implies that B G,1 (x) ∩ C = {y}, y ∈ C and x /
∈ C; we see that in this case y is still 1-covered by a codeword, namely itself.

If meanwhile all vertices remain 1-separated by C in G e , then C ∪ {x} is 1-identifying in G e . But this first reason can go along with the second reason:

2) (G e , C, 1)-twins appear; because only the edge xy is deleted when going from G to G e , and similarly to the proof of Theorem 18, only the following pairs can be (G e , C, 1)-twins: • x and y, • x and u with u = x, u = y, • y and v with v = x, v = y.

If x and y are (G e , C, 1)-twins, this means that

B G e ,1 (x) ∩ C = B G e ,1 (y) ∩ C,
which implies that x / ∈ C, y / ∈ C, and so

B G,1 (x) ∩ C = B G,1 (y) ∩ C, contradicting the fact that C is 1-identifying in G.
Assume next that x and u are (G e , C, 1)-twins. Then and so

B G e ,1 (x) ∩ C = B G e ,1 (u) ∩ C = B G,1 (u) ∩ C = B G,1 (x) ∩ C, y 4' 3' 2 1 3 2' 1' 5 6 7 8 5' 6' 7' 8'
y ∈ C and B G e ,1 (x) ∩ C = (B G,1 (x) ∩ C) \ {y}.
If x and u are the only (G e , C, 1)-twins, then with two more codewords we can both 1-cover x if necessary and 1-separate x and u in G e . The same argument would work if y and v were the only (G e , C, 1)-twins. So we assume that x and u, and y and v are (G e , C, 1)-twins. This implies that both x and y are codewords, each 1-covered by itself. All there is left to do is to 1-separate two pairs of (G e , C, 1)-twins in G e , which can be done using two more codewords.

Note that we made no assumption on the connectivity of G and G e . The following example shows that graphs G and G e with γ 1 (G e ) = γ 1 (G) + 2 exist. Here the graph G e is disconnected, but by adding a vertex which is linked to all the other vertices, we could also have, thanks to Lemmata 1 and 2, an example where G e would be connected.

Example 21 Let G = (V, E) be the graph represented in Figure 7, and G e the graph obtained by deleting the edge xy. We claim that: (a) γ 1 (G) ≤ 12 and (b) γ 1 (G e ) ≥ 14, which by [START_REF] Honkala | On 2-edge-robust r-identifying codes in the king grid[END_REF] will imply that γ 1 (G e ) = 14 = γ 1 (G)+2.

Proof of (a). It is quite straightforward to check that C = {1, 3, x, 6, 8, 9, 9 , 8 , 6 , y, 3

, 1 } is 1-identifying in G. Hence γ 1 (G) ≤ 12.
Proof of (b). Let C e be a 1-identifying code in G e . We are going to show that the left part of the (now disconnected) graph G e requires at least seven codewords.

As in Example 19, we have 3 ∈ C e , 6 ∈ C e , and C e also contains at least one element in each of the 2-sets {1, 2} and {7, 8}, which amounts to four codewords.

As in Example 19, we also have that:

• there are at least three codewords in {1, 2, 3, 4, x}, and three codewords in {x, 5, 6, 7, 8}. So, if x / ∈ C e , there are, because of 9 and 10, at least 3 + 3 + 2 = 8 codewords, and we are done. We now assume that x ∈ C e , so that we have already taken five codewords. One more codeword is not sufficient to 1-separate both 9 and 10, 9 and x, and 10 and x. This proves Claim (b).

By Theorems 18 and 20, we have the following result.

Theorem 22 Let G 1 and G 2 be two 1-twin-free graphs, with same vertex set and differing by one edge. Then

γ 1 (G 1 ) -2 ≤ γ 1 (G 2 ) ≤ γ 1 (G 1 ) + 2.
As a consequence, if for instance γ 1 (G 1 ) ≤ a and γ 1 (G 2 ) ≥ a + 2, then γ 1 (G 1 ) = a and γ 1 (G 2 ) = a + 2.

We conclude the case r = 1 by mentioning that pairs of graphs G and G e such that γ 1 (G e )γ 1 (G) = 0 or γ 1 (G e )γ 1 (G) = ±1 exist.

Example 23 We give simple examples with (a) γ 1 (G e )γ 1 (G) = -1 and (b) γ 1 (G e )γ 1 (G) = 1, omitting the easy case when the difference is 0.

(a) Let G e = P 9 = x 1 x 2 . . . x 9 , and add the edge {x 3 , x 5 } in order to obtain G. It is known [START_REF] Bertrand | LOBSTEIN: Identifying and locating-dominating codes on chains and cycles[END_REF]Th. 3]) that γ 1 (P 9 ) = 5, and it is easy to see that γ 1 (G) = 6, so γ 1 (G e )γ 1 (G) = -1.

(b) Let G e be the graph consisting of P 1 and P 4 , and G be the graph obtained by adding an edge between one extremity of P 4 and the vertex of P 1 , so that G = P 5 . We have γ 1 (P 1 ) = 1, γ 1 (P 4 ) = 3, and γ 1 (P 5 ) = 3, which shows that γ 1 (G e )γ 1 (G) = 1.

The case r ≥ 2

We first give a result with γ r (G)γ r (G e ) equal to r; here, the graph G e is connected, but we have found no better result using a disconnected graph.

Proposition 24 There exist two (connected) r-twin-free graphs G and G e such that γ r (G)γ r (G e ) = r.

Proof. Let r ≥ 2 and p ≥ 3 be integers; for 1 ≤ i ≤ p, we consider copies (V i , E i ) of the path P r , with the following notation:

V i = {v i,1 , v i,2 , . . . , v i,r }, and E i = {{v i,j , v i,j+1 } : 1 ≤ j ≤ r -1}.
Let G = (V, E), where

V = ∪ 1≤i≤p V i ∪ {x} ∪ {v} and E = ∪ 1≤i≤p E i ∪ {{x, v i,1 } : 1 ≤ i ≤ p} ∪ {{v, v i,r } : 1 ≤ i ≤ p},
and build the graph G e from G by deleting the edge xv 1,1 , see Figure 8. Proof of (a). Note that in G, for i and j such that 1 ≤ i < j ≤ p, the set of vertices {x} ∪ {v i,k : 1 ≤ k ≤ r} ∪ {v} ∪ {v j,k : 1 ≤ k ≤ r} forms the cycle C 2r+2 , which is r-twin-free and is denoted by C(i, j). On such a cycle, we say that the vertex z is the opposite of the vertex y if z is the (only) vertex at distance r + 1 from y.

We claim that, for k fixed between 1 and r, among the p vertices v i,k , at least p -1 of them belong to any r-identifying code C in G. Indeed, assume on the contrary that two vertices, say v 1,k and v 2,k , are not in C; then their opposite vertices in C(1, 2), v 2,r-k+1 and v 1,r-k+1 respectively, cannot be r-separated by C.

Finally, the fact that B G,r (v)∆B G,r (x) = {v, x} (where ∆ stands for the symmetric difference) shows that v or x belong to C, and finally γ r (G) ≥ (p -1)r + 1. On the other hand,

{v} ∪ {v i,k : 2 ≤ i ≤ p, 1 ≤ k ≤ r}
is an r-identifying code in G, with size (p -1)r + 1, thus Claim (a) is proved. Note that this code contains all the vertices in G, except the r + 1 vertices x and v 1,k , 1 ≤ k ≤ r.

Proof of (b). The same argument about cycles of length 2r + 2 similarly shows that for k fixed between 1 and r, among the p -1 vertices v i,k , 2 ≤ i ≤ p, at least p -2 of them belong to any r-identifying code in G e . These r(p -2) codewords are not sufficient, but adding v 1,1 gives an r-identifying code C e in G e , for example

C e = {v 1,1 } ∪ {v i,k : 3 ≤ i ≤ p, 1 ≤ k ≤ r}.
Note that we could have contented ourselves with the inequalities γ r (G) ≥ r(p -1) + 1 and γ r (G e ) ≤ r(p -2) + 1, so as to obtain γ r (G)γ r (G e ) ≥ r.

We now investigate how large γ r (G e )γ r (G) can be. We start with connected graphs.

Case of a connected graph G e

Proposition 25 There exist two (connected) r-twin-free graphs G and G e such that γ r (G e )γ r (G) ≥ r -1.

Proof. Consider the path P 4r+2 represented in Figure 9, consisting of one codeword, then r noncodewords, then r codewords, then one noncodeword, then r codewords, then r noncodewords. This pattern was already described in [3, Fig. 2] and can be used to construct periodic r-identifying codes in chains or cycles, with density one half. Now for k ≥ 2, we let G e be the cycle with n = k(4r + 2) + 2r vertices and construct the graph G by adding the edge e = x n x 4r+1 , see Figure 10 for k = 2, r = 4 and n = 44. We claim that the code C consisting of k concatenated patterns given by Figure 9, starting at x r and ending at x r+k(4r+2)-1 , plus the codeword x r+k(4r+2) , is r-identifying in G. Once we have proved this, and since |C| = k(2r + 1) + 1 and γ r (G e ) = k(2r + 1) + r by Theorem 3, we have proved [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF].

Checking C can be done in two steps: first, it is easy to observe that the vertices x i for i ∈ {r, . . . , r + k(4r + 2) -1} are r-covered and pairwise r-separated by codewords, see also the proof of Th. 1 in [START_REF] Bertrand | LOBSTEIN: Identifying and locating-dominating codes on chains and cycles[END_REF]. Next, with the crucial help of the edge e, the 2r vertices x k(4r+2)+r to x r-1 are rcovered, pairwise r-separated, and r-separated fom the previous vertices by codewords.

Case of a disconnected graph G e

We first give a result with γ r (G e )γ r (G) ≥ 2r -3, then investigate how to possibly reach 2r, and finally give a conjecture.

Proposition 26 There exist two r-twin-free graphs G and G e such that γ r (G e )γ r (G) ≥ 2r -3.

(

) 19
Proof. Consider the graph G given by Figure 11, with the edge e = vw, where p and q are integers, p ≥ 3, q ≥ 3. We claim that: (a) γ r (G e ) ≥ p + q + 4r -6, and (b) γ r (G) ≤ p + q + 2r -3, from which (19) follows.

Proof of (a). If G(v) represents the "left part" of G, it is sufficient to prove that γ r (G(v)) ≥ p + 2r -3. The following two observations will be useful. For 1 ≤ i ≤ p and 2 ≤ k ≤ r, we have:

B G(v),r (v i,r-k+1 )∆B G(v),r (v i,r-k+2 ) = {v j,k : 1 ≤ j ≤ p, j = i}, (20)
and for 1 ≤ i < j ≤ p:

B G(v),r (v i,r )∆B G(v),r (v j,r ) = {v i,1 , v j,1 }. (21)
The consequences are immediate. First, in order to have the vertices v i,r , 1 ≤ i ≤ p, pairwise r-separated in G(v), we see by [START_REF] Lobstein | A bibliography on watching systems, identifying, locating-dominating and discriminating codes in graphs[END_REF] that we need at least p -1 codewords among the p vertices v i,1 ; second, for k fixed between 2 and r, we see, using [START_REF] Laihonen | On edge-robust (1, ≤ )-identifying codes in binary Hamming spaces[END_REF], that we need at least two codewords among the p vertices v i,k . So we obtain, after checking that G(v) indeed is r-twin-free, that γ r (G(v)) ≥ (p -1) + 2(r -1) = p + 2r -3, and Claim (a) is proved. Proof of (b). We set

C = C v ∪ C w , with C v = {v i,1 : 2 ≤ i ≤ p} ∪ {v i,3 , v i,5 , . . . , v i,r : 1 ≤ i ≤ 2}, C w = {w i,1 : 1 ≤ i ≤ q} ∪ {w i,3 , w i,5 , . . . , w i,r : 1 ≤ i ≤ 2},
when r is odd, and when r is even:

C v = {v i,1 : 2 ≤ i ≤ p} ∪ {v i,3 , v i,5 , . . . , v i,r-1 : 1 ≤ i ≤ 2} ∪ {v}, C w = {w i,1 : 1 ≤ i ≤ q} ∪ {w i,3 , w i,5 , . . . , w i,r-1 : 1 ≤ i ≤ 2} ∪ {w}.
We show that C, which has p + q + 2r -3 elements, is r-identifying in G.

First, one vertex in the left part and one vertex in the right part of G cannot be (G, C, r)-twins, thanks in particular to the q vertices w i,1 : more specifically, note that we take w 1,1 in C (among other candidates, such as v 1,1 ) in order to r-separate w 1,r and v 1,r , and the consequence is that C v and C w are not completely alike. Second, two vertices in the left part of G cannot be (G, C, r)-twins because -on each of the p copies of P r , consecutive vertices are r-separated alternatively by one codeword in C w then one codeword in C v ;

-two vertices on different copies j 1 and j 2 are r-separated by v j 1 ,1 or v j 2 ,1 ;

-and v is r-separated from the other vertices by v 2,1 or v 3,1 . The same argument works even better for the right part of G, by Lemma 5 and since w 1,1 ∈ C w . And obviously, all vertices are r-covered by at least one codeword.

We now give a lead on how (19) could be improved, in Example 30. To do this, we need some previously known results and one definition.

The r-transitive closure, or r-th power, of a graph G = (V, E) is the graph denoted by G r = (V r , E r ) and defined by V r = V and E r = {xy : x ∈ V, y ∈ V, 0 < d G (x, y) ≤ r}.

The following very easy lemma can be found in [START_REF] Charon | Extremal cardinalities for identifying and locating-dominating codes in graphs[END_REF] or [START_REF] Charon | Extremal cardinalities for identifying and locating-dominating codes in graphs[END_REF].

Lemma 27 In a graph G = (V, E), a code C ⊆ V is r-identifying if and only if it is 1-identifying in G r . The following result is from [START_REF] Bertrand | Codes identifiants et codes localisateurs-dominateurs sur certains graphes, Mémoire de stage de maîtrise[END_REF], but we prefer to refer to the shorter, more elegant and more general proof of [START_REF] Gravier | On graphs having a V \ {x} set as an identifying code[END_REF].

Theorem 28 Any minimum 1-identifying code in a graph with n vertices has at most n -1 codewords.

Corollary 29 For all r ≥ 1, any minimum r-identifying code in a graph with n vertices has at most n -1 codewords.

Graphs G of order n with γ r (G) = n -1 exist for all r and n ≥ 3r 2 + 1, see Theorems 4-6 in [START_REF] Charon | Extremal cardinalities for identifying and locating-dominating codes in graphs[END_REF] or [START_REF] Charon | Extremal cardinalities for identifying and locating-dominating codes in graphs[END_REF], or Theorems 4 and 5 in [START_REF] Charon | Possible cardinalities for identifying codes in graphs[END_REF]; on this topic, see also the more recent [START_REF] Foucaud | Extremal graphs for the identifying code problem[END_REF]. Our idea is to use two copies of such a "bad" graph, and to link them with an edge.

Example 30 See Figure 12, where two different representations of the very same graph G * with 10 vertices and γ 2 (G * ) = 9 are given, forming a (disconnected) graph G e with 20 vertices and γ 2 (G e ) = 18. If we link any two vertices of the two copies, say v 1,1 and z 1,1 , we obtain a graph G with 20 vertices and γ 2 (G) ≤ 14: a 2-identifying code in G is C = {v 1,1 , v 1,3 , v 1,4 , v 1,5 , v 2,2 , v 2,3 , v 2,5 , z 1,1 , z 1,3 , z 1,4 , z 1,5 , z 2,2 , z 2,3 , z 2,5 }, see the black vertices in Figure 12. We have therefore an example with γ 2 (G e )γ 2 (G) ≥ 4.

(

) 22
We feel however that it is difficult to improve more than that (a decrease by 4 when r = 2, and, in the general case, by 2r), and, together with the case r = 1, see [START_REF] Honkala | On 2-edge-robust r-identifying codes in the king grid[END_REF] and Example 21 in Section 6, this suggests the following conjecture:

Conjecture 31 For all r ≥ 1, there exist two r-twin-free graphs G e and G such that γ r (G e )γ r (G) = 2r. (23)

Moreover, any two r-twin-free graphs G e and G satisfy γ r (G e )γ r (G) ≤ 2r.

(24)

Conclusion

Table 2 recapitulates the results obtained in the previous sections, using (in)equalities ( 15)-( 19) and [START_REF] Roberts | Locating sensors in paths and cycles: the case of 2-identifying codes[END_REF], and also restates Conjecture 31. We only consider the difference γ r (G e )γ r (G). Table 2: The difference γ r (G e )γ r (G), as a function of r.

It would be interesting to try and see whether the results in Propositions 24, 25 and 26 could be improved, namely: for r ≥ 2, are there graphs G and G e with (i) γ r (G e )γ r (G) < -r, (ii) γ r (G e )γ r (G) > r -1, or (iii) γ r (G e )γ r (G) > 2r -3, where in Cases (i) and (iii), the graph G e may be disconnected.

Figure 2 :

 2 Figure 2: The graphs G x and G in Proposition 10.

Figure 3 :

 3 Figure 3: Graph G in Proposition 12, for r = 6 and k = 4. Squares and circles, white or black, small or large, are vertices. The 19 black vertices constitute a 6-identifying code in G.

Figure 4 :

 4 Figure 4: Graph G in Proposition 14, for r = 5 and k = 6. Squares and circles, white or black, small or large, are vertices. The 21 black vertices constitute a 5-identifying code in G.

Figure 5 :

 5 Figure 5: The graphs G x and G in Proposition 16.

4 Figure 6 :

 46 Figure 6: Graph G e in Example 19.

4 Figure 7 :

 47 Figure 7: Graph G in Example 21.

Figure 8 :

 8 Figure 8: The graphs G e and G in Proposition 24.

Figure 9 :

 9 Figure 9: A pattern with 4r + 2 vertices, half of which are codewords.

Figure 10 :

 10 Figure 10: Graph G in Proposition 25, for r = 4 and n = 44. The 19 black vertices constitute a 4-identifying code in G.

Figure 11 :

 11 Figure 11: Graph G in Proposition 26.

Figure 12 :

 12 Figure 12: Two copies of G * , a graph with 10 vertices and γ 2 (G * ) = 9.

r

  comment γ r (G e )γ r (G) reference = 1 must be inside {-2, -1, 0, 1, 2}(15), (16), Th. 22 = 1 graphs with = -2, = -1, = 0, = 1, = 2 Ex.

  see the small black circles in Figure3. It is now quite straightforward to observe that the pairs {x 48 , x 1 }, {x 2 , x 3 } and {x 4 , x 5 } are pairs of (G, S, 6)twins, as well as {x 12 , x 13 }, {x 14 , x 15 }, {x 16 , x 17 }, {x 24 , x 25 }, {x 26 , x 27 }, {x 28 , x 29 }, {x 36 , x 37 }, {x 38 , x 39 } and {x 40 , x 41 }, for reasons of symmetry, and that they are the only ones.

3 , x 5 , x 13 , x 15 , x 17 , x 25 , x 27 , x 29 , x 37 , x 39 , x 41 },

  3 , x 11 , x 13 , x 21 , x 23 , x 31 , x 33 , x 41 , x 43 , x 51 , x 53 }, see the small black circles in Figure4. It is straightforward to see that only the following sets of (G, S, 5)-twins exist:• (i) {x, x 10 , x 20 , x 30 , x 40 , x 50 , x 60 }, • (ii) {x 59 , x 1 , x 2 }together with the five symmetrical sets {x 9 , x 11 , x 12 }, . . ., • (iii) {x 3 , x 4 } together with the five symmetrical sets {x 13 , x 14 }, . . .The first two cases are annoying and will be "expensive" because they present symmetries with respect to x. Define the set T as follows: T = S ∪ {x 5 , x 15 , x 35 , x 45 }, see the large black circles in Figure