ED Mathématiques et Informatique
Distinction and Detection Problems in Graphs
by Clara MARCILLE (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
The defense will take place at 14h00 - Amphithéatre du LaBRI LaBRI (A33) 351 Cours de la Libération 33400 Talence
in front of the jury composed of
- Hervé HOCQUARD - Professeur des universités - Université de Bordeaux - Directeur de these
- Julien BENSMAIL - Maître de conférences - Université Côte d'Azur - CoDirecteur de these
- Florent FOUCAUD - Maître de conférences - Université Clermont Auvergne - Examinateur
- Éric DUCHENE - Professeur des universités - Université Lyon 1 - Rapporteur
- Nicolas NISSE - Directeur de recherche - Université Côte d'Azur - Rapporteur
- Éric SOPENA - Professeur des universités - Université de Bordeaux - Examinateur
- Aline PARREAU - Chargée de recherche - Université Lyon 1 - Examinateur
- Cléophée ROBIN - Maîtresse de conférences - Université Paris Cité - Examinateur
This thesis deals with two independent areas of graph theory. In the first part, we study irregularity of graphs, as an antonym to regularity. We focus on several established ways to distinguish adjacent vertices by their degrees. While some graphs naturally have the property of having any pair of adjacent vertices distinct degree-wise, it is not always the case. We introduce ways to label the edges of a graph so that, instead of considering the degree of a vertex, we consider a function of the labels of its incident edges. We call it resulting sum, which we ask to be different for any pair of adjacent vertices. In the area of the 1-2-3 Conjecture, introduced by Karoński et al., labels are either 1, 2, or 3, and the resulting sum of a vertex is the sum of the labels of its incident edges. The 1-2-3 Conjecture asks whether, for any connected graph other than K_2, it is possible to find a labelling of its edges so that the resulting sums of any two adjacent vertices are different. Another way to make a graph "irregular" is to decompose it into locally irregular graphs, where we partition the edges of the graph so that each part induces a locally irregular graph. By adjusting the resulting sum definition, labels, and the distinction condition, we are able to define several other distinction problems. We also introduce new ones, and prove connections between them using a unified formalism. In Chapter 2, we decompose graphs into strongly locally irregular graphs, where each part induces a graph where the degrees of any two adjacent vertices differ by at least 2. In Chapter 3, we study a generalisation of decompositions into locally irregular graphs and edge-labellings, which was introduced by Baudon et al. Finally, in Chapter 4, we extend the definition of edge-labellings to signed graphs, and give a formalism for the distinction problems of this thesis, which we use to give unified statements and results. In the second part, we monitor networks for faults, where networks are represented as graphs. Introduced by Foucaud et al., a monitoring edge-geodetic set (MEG-set for short) of a graph is a set of probes on nodes (vertices) that "ping" each other (measure their distance to each another). We also ask that probes be placed in such a way that, if there is a connection failure in the network (an edge is deleted), then pings between some two probes will change (the distance will increase). This notion belongs to the family of metric parameters, which is a set of ways to detect events in a graph using distances between vertices. We investigate several questions around MEG-sets. Since probes are expensive, we want to minimise their number. This problem is NP-hard, so we first look at graphs with a certain structure. In Chapter 6, we focus on graphs with a unique minimum MEG-set. We prove properties of the intersection of all MEG-sets of a graph, which leads us to polynomial-time algorithms for computing minimum MEG-sets of several classes of graphs. In Chapter 7, we prove that although finding a minimum MEG-set is NP-hard, it is also fixed-parameter tractable when parameterised by clique-width plus diameter of the input graph. We also provide an algorithm that yields a MEG-set that is larger than the optimal size by a factor logarithmic of the order of the input graph, but runs in polynomial time. We also prove that no such algorithm exists for a constant approximation factor. Finally, in Chapter 8, we introduce MAG-sets as an analogue to MEG-sets on oriented graphs, and begin the study of this parameter for several classes of graphs. We also introduce two decision problems. One is to find the size of a minimum MAG-set; the other is to find an orientation of a graph such that the minimum MAG-set is the whole vertex set. We prove that both problems are NP-hard.
ED Entreprise Economie Société
FAMILY SITUATIONS AND TOURIST MOBILITIES: THE EFFECT OF DEPENDENT CHILDREN ON OVERNIGHT STAYS AWAY FROM HOME AMONG HOUSEHOLDS IN METROPOLITAIN FRANCE
by Yuejia SUN (COMPTRASEC - Centre de Droit Comparé de Travail et de la Sécurité Sociale)
The defense will take place at 14h30 - 250 Salle des thèses de la faculté de droit COMPTRASEC - UMR CNRS 5114 Université de Bordeaux 16 avenue Léon Duguit 33608 Pessac Cedex
in front of the jury composed of
- Christophe BERGOUIGNAN - Professeur des universités - Université de Bordeaux - Directeur de these
- Frédéric SANDRON - Directeur de recherche - Université Paris Descartes - Rapporteur
- Claire SCODELLARO - Maîtresse de conférences - Université Paris 1-Panthéon-Sorbonne - Rapporteur
- Didier BRETON - Professeur des universités - Université de Strasbourg - CoDirecteur de these
- Jacques VERON - Directeur de recherche émérite - Institut national d'études démographiques - Examinateur
This thesis explores the influence of household structure on participation, frequency and duration of trips, as well as expenditure on the last trip, and distance, motives, and destinations by introducing a new measure of relative child load, which takes into account the age of individuals with childcare responsibilities. By establishing a link between life-course perspective, leisure constraints and cultural practices, a revised framework provides a more nuanced grasp of child-related responsibilities and their influence on family tourism practices. Using data from the 2017 French Household Budget Survey, the results show that, far from being a structural constraint, relative child burden affects staycation practices, implying that research should go beyond the usual approach of considering only the presence and number of children, to better reflect temporal divergences in the timing of parenthood.