Search

The main goal of this thesis is to develop lossless compression schemes for analog and binary sources. All the considered compression schemes have as common feature that the encoder can be represented by a graph, so they can be studied employing tools from modern coding theory. In particular, this thesis is focused on two compression problems: the group testing and the noiseless compressed sensing problems. Although both problems may seem unrelated, in the thesis they are shown to be very close. Furthermore, group testing has the same mathematical formulation as non-linear binary source compression schemes that use the OR operator. In this thesis, the similarities between these problems are exploited. The group testing problem is aimed at identifying the defective subjects of a population with as few tests as possible. Group testing schemes can be divided into two groups: adaptive and non-adaptive group testing schemes. The former schemes generate tests sequentially and exploit the partial decoding results to attempt to reduce the overall number of tests required to label all members of the population, whereas non-adaptive schemes perform all the test in parallel and attempt to label as many subjects as possible. Our contributions to the group testing problem are both theoretical and practical. We propose a novel adaptive scheme aimed to efficiently perform the testing process. Furthermore, we develop tools to predict the performance of both adaptive and non-adaptive schemes when the number of subjects to be tested is large. These tools allow to characterize the performance of adaptive and non-adaptive group testing schemes without simulating them. The goal of the noiseless compressed sensing problem is to retrieve a signal from its lineal projection version in a lower-dimensional space. This can be done only whenever the amount of null components of the original signal is large enough. Compressed sensing deals with the design of sampling schemes and reconstruction algorithms that manage to reconstruct the original signal vector with as few samples as possible. In this thesis we pose the compressed sensing problem within a probabilistic framework, as opposed to the classical compression sensing formulation. Recent results in the state of the art show that this approach is more efficient than the classical one. Our contributions to noiseless compressed sensing are both theoretical and practical. We deduce a necessary and sufficient matrix design condition to guarantee that the reconstruction is lossless. Regarding the design of practical schemes, we propose two novel reconstruction algorithms based on message passing over the sparse representation of the matrix, one of them with very low computational complexity., El objetivo principal de la tesis es el desarrollo de esquemas de compresión sin pérdidas para fuentes analógicas y binarias. Los esquemas analizados tienen en común la representación del compresor mediante un grafo; esto ha permitido emplear en su estudio las herramientas de codificación modernas. Más concretamente la tesis estudia dos problemas de compresión en particular: el diseño de experimentos de testeo comprimido de poblaciones (de sangre, de presencia de elementos contaminantes, secuenciado de ADN, etcétera) y el muestreo comprimido de señales reales en ausencia de ruido. A pesar de que a primera vista parezcan problemas totalmente diferentes, en la tesis mostramos que están muy relacionados. Adicionalmente, el problema de testeo comprimido de poblaciones tiene una formulación matemática idéntica a los códigos de compresión binarios no lineales basados en puertas OR. En la tesis se explotan las similitudes entre todos estos problemas. Existen dos aproximaciones al testeo de poblaciones: el testeo adaptativo y el no adaptativo. El primero realiza los test de forma secuencial y explota los resultados parciales de estos para intentar reducir el número total de test necesarios, mientras que el segundo hace todos los test en bloque e intenta extraer el máximo de datos posibles de los test. Nuestras contribuciones al problema de testeo comprimido han sido tanto teóricas como prácticas. Hemos propuesto un nuevo esquema adaptativo para realizar eficientemente el proceso de testeo. Además hemos desarrollado herramientas que permiten predecir el comportamiento tanto de los esquemas adaptativos como de los esquemas no adaptativos cuando el número de sujetos a testear es elevado. Estas herramientas permiten anticipar las prestaciones de los esquemas de testeo sin necesidad de simularlos. El objetivo del muestreo comprimido es recuperar una señal a partir de su proyección lineal en un espacio de menor dimensión. Esto sólo es posible si se asume que la señal original tiene muchas componentes que son cero. El problema versa sobre el diseño de matrices y algoritmos de reconstrucción que permitan implementar esquemas de muestreo y reconstrucción con un número mínimo de muestras. A diferencia de la formulación clásica de muestreo comprimido, en esta tesis se ha empleado un modelado probabilístico de la señal. Referencias recientes en la literatura demuestran que este enfoque permite conseguir esquemas de compresión y descompresión más eficientes. Nuestras contribuciones en el campo de muestreo comprimido de fuentes analógicas dispersas han sido también teóricas y prácticas. Por un lado, la deducción de la condición necesaria y suficiente que debe garantizar la matriz de muestreo para garantizar que se puede reconstruir unívocamente la secuencia de fuente. Por otro lado, hemos propuesto dos algoritmos, uno de ellos de baja complejidad computacional, que permiten reconstruir la señal original basados en paso de mensajes entre los nodos de la representación gráfica de la matriz de proyección.

A graph where every vertex has three neighboring vertices is a cubic graph. An edge-coloring is an assignment of colors to the edges of a graph in such a way that the edges incident to a vertex have no repeated colors. An edge-coloring is optimal if it uses the minimum possible number of colors. Vizing's Theorem implies that an optimal edge-coloring of a cubic graph requires three or four colors. If three colors are enough, we call the edge-coloring a Tait-coloring. If four colors are needed, we call the graph a snark. Holyer proved that deciding wether a cubic graph is Tait-colorable is an NP-complete problem, therefore it is widely believed that it is a very difficult or intractable problem in the general case. Nevertheless, theory does not forbid efficient solutions in specific cases: this is called "breaking intractability". We describe an heuristic algorithm called CVD, for "Conflicting Vertex Displacement", which has a good empirical performance in random regular graphs. Also it allows us to check a conjecture by Biggs on "odd graphs" in instances with milions of vertices and edges, using moderately powerful computers. Snarks are relevant in graph theory: they appear often as minimal counterexamples of important conjectures, such as the Cycle Double Cover Conjecture (every bridgeless graph has a family of cycles such that every edge belongs to exactly two cycles of the family). In the analysis and synthesis of snarks, multipoles, "pieces" of cubic graphs with free ends that can be joined to each other, are often used. In a Tait-colored multipole, the number of equally colored free ends for each color and the total number of free ends have the same parity (the number of vertices of the multipole has this same parity, too). This result, known as the Parity Lemma, allows the interpretation of multipoles as logic gates and cubic graphs as logic circuits. This gives a very general way to construct snarks, based on logic circuits with no valid Boolean assignment, and allows us to relate the Tait-coloring of cubic graphs to integer factorization. In particular, we can construct snarks from prime numbers. A state of a multipole is the restriction of a Tait-coloring of the multipole to its free ends. If the set of states of a multipole is a non-empty subset of the set of states of another multipole with a larger number of vertices, we call the smaller multipole a reduction of the larger one. An irreducible multipole is a multipole with no reduction (an obvious example is a minimal multipole, that is, with no vertices or with a single vertex). The maximum number of vertices of an irreducible multipole as a function of its number (m) of free ends is denoted by v(m). Its behavior is well-known only for m, Un graf on cada vèrtex té tres vèrtexs adjacents és un graf cúbic. Un aresta-acoloriment és una assignació de colors a les arestes d'un graf de tal manera que no es repeteixin colors en les arestes incidents a un mateix vèrtex. Un aresta-acoloriment és òptim si utilitza el mínim nombre possible de colors. El Teorema de Vizing implica que un aresta-acolorament òptim d'un graf cúbic requereix tres o quatre colors. Si tres colors són suficients, de l'aresta-acoloriment en diem Tait-acoloriment. Si fan falta quatre colors, diem que el graf és un snark. Holyer va demostrar que determinar si un graf cúbic és Tait-acolorible és un problema NP-complet, i per tant se suposa àmpliament que és un problema molt difícil o intractable en el cas general. Tanmateix, la teoria no prohibeix que es puguin resoldre eficientment casos concrets: és el que s'anomena "ruptura de la intractabilitat". Descrivim un algorisme heurístic anomenat DVC, per "Desplaçament de Vèrtexs Conflictius", que té un bon rendiment empíric en grafs regulars aleatoris. També ens permet comprovar una conjectura de Biggs sobre els "odd graphs" en instàncies de milions de vèrtexs i arestes, utilitzant ordinadors de potència moderada. Els snarks són rellevants en la teoria de grafs: sovint apareixen com a contraexemples minimals de conjectures importants, com per exemple la Conjectura del Recobriment Doble per Cicles (tot graf sense ponts té una família de cicles tal que cada aresta pertany exactament a dos dels cicles). En l'anàlisi i síntesi d'snarks se solen utilitzar multipols, que són "peces" de grafs cúbics amb extrems lliures que es poden unir entre ells. En un multipol Tait-acolorit, el nombre d'extrems lliures de cada color té la mateixa paritat que el nombre total d'extrems lliures (i que el nombre de vèrtexs del multipol). Aquest resultat, conegut com el Lema de Paritat, permet interpretar els multipols com a portes lògiques i els grafs cúbics com a circuits lògics. Això proporciona una manera molt general de construir snarks, en base a circuits lògics sense cap assignació booleana vàlida, i també permet relacionar l'aresta-acoloriment de grafs amb la factorització de nombres enters. En particular, permet construir snarks a partir de nombres primers. Un estat d'un multipol és la restricció d'un Tait-acoloriment del multipol als seus extrems lliures. Si el conjunt d'estats d'un multipol és un subconjunt no buit del conjunt d'estats d'un altre multipol amb un nombre de vèrtexs més gran, diem que n'és una reducció. Un multipol irreductible és un multipol sense cap reducció (un exemple obvi és un multipol minimal, és a dir sense vèrtexs o amb un sol vèrtex). El màxim nombre de vèrtexs d'un multipol irreductible en termes del seu nombre d'extrems lliures és una funció, representada per v(m), el comportament de la qual només es coneix exactament per m

The topic of this thesis is the development of SAT-based techniques and tools for solving industrial combinatorial problems. First, it describes the architecture of state-of-the-art SAT and SMT Solvers based on the classical DPLL procedure. These systems can be used as black boxes for solving combinatorial problems. However, sometimes we can increase their efficiency with slight modifications of the basic algorithm. Therefore, the study and development of techniques for adjusting SAT Solvers to specific combinatorial problems is the first goal of this thesis. Namely, SAT Solvers can only deal with propositional logic. For solving general combinatorial problems, two different approaches are possible: - Reducing the complex constraints into propositional clauses. - Enriching the SAT Solver language. The first approach corresponds to encoding the constraint into SAT. The second one corresponds to using propagators, the basis for SMT Solvers. Regarding the first approach, in this document we improve the encoding of two of the most important combinatorial constraints: cardinality constraints and pseudo-Boolean constraints. After that, we present a new mixed approach, called lazy decomposition, which combines the advantages of encodings and propagators. The other part of the thesis uses these theoretical improvements in industrial combinatorial problems. We give a method for efficiently scheduling some professional sport leagues with SAT. The results are promising and show that a SAT approach is valid for these problems. However, the chaotical behavior of CDCL-based SAT Solvers due to VSIDS heuristics makes it difficult to obtain a similar solution for two similar problems. This may be inconvenient in real-world problems, since a user expects similar solutions when it makes slight modifications to the problem specification. In order to overcome this limitation, we have studied and solved the close solution problem, i.e., the problem of quickly finding a close solution when a similar problem is considered.

En aquesta tesi s'estudien diferents problemes en el camp de la combinatòria i la teoria de grafs, utilitzant el mètode probabilístic. Aquesta tècnica, introduïda per Erdős , ha esdevingut una eina molt potent per tal de donar proves existencials per certs problemes en diferents camps de les matemàtiques on altres mètodes no ho han aconseguit. Un dels seus principals objectius és l'estudi del comportament de les variables aleatòries. El cas en que aquestes variables compten el nombre d'esdeveniments dolents que tenen lloc en una estructura combinatòria és de particular interès. La idea del Paradigma de Poisson és estimar la probabilitat que tots aquests esdeveniments dolents no succeeixin a la vegada, quan les dependències entre ells són febles o escasses. En tal cas, aquesta probabilitat s'hauria de comportar de forma similar al cas on tots els esdeveniments són independents. El Lema Local de Lovász o la Desigualtat de Suen són exemples d'aquesta idea. L'objectiu de la tesi és estudiar aquestes tècniques ja sigui proveint-ne noves versions, refinant-ne les existents per casos particulars o donant-ne noves aplicacions. A continuació s'enumeren les principals contribucions de la tesi. La primera part d'aquesta tesi estén un resultat d' Erdős i Spencer sobre transversals llatins. Els autors proven que qualsevol matriu d'enters on cap nombre apareix massa vegades, admet un transversal on tots els nombres són diferents. Això equival a estudiar els aparellaments multicolors en aresta-coloracions de grafs complets bipartits. Sota les mateixes hipòtesis que, es donen resultats sobre el nombre d'aquests aparellaments. Les tècniques que s'utilitzen estan basades en l'estratègia desenvolupada per Lu i Székely. En la segona part d'aquesta tesi s'estudien els codis identificadors. Un codi identificador és un conjunt de vèrtexs tal que tots els vèrtexs del graf tenen un veïnatge diferent en el codi. Aquí s'estableixen cotes en la mida d'un codi identificador mínim en funció dels graus i es resol parcialment una conjectura de Foucaud et al.. En un altre capítol, es mostra que qualsevol graf suficientment dens conté un subgraf que admet un codi identificador òptim. En alguns casos, provar l'existència d'un cert objecte és trivial. Tot i així, es poden utilitzar les mateixes tècniques per obtenir resultats d'enumeració. L'estudi de patrons en permutacions n'és un bon exemple. A la tercera part de la tesi es desenvolupa una nova tècnica per tal d'estimar el nombre de permutacions d'una certa llargada que eviten còpies consecutives d'un patró donat. En particular, es donen cotes inferiors i superiors per a aquest nombre. Una de les conseqüències és la prova de la conjectura CMP enunciada per Elizalde i Noy així com nous resultats en el comportament de la majoria dels patrons. En l'última part de la tesi s'estudia la Conjectura Lonely Runner, enunciada independentment per Wills i Cusick i que té múltiples aplicacions en diferents camps de les matemàtiques. Aquesta coneguda conjectura diu que per qualsevol conjunt de corredors que corren al llarg d'un cercle unitari, hi ha un moment on tots els corredors estan suficientment lluny de l'origen. Aquí, es millora un resultat de Chen ampliant la distància de tots els corredors a l'origen. També s'estén el teorema del corredor invisible de Czerwiński i Grytczuk ., In this thesis we study different problems in combinatorics and in graph theory by means of the probabilistic method. This method, introduced by Erdös, has become an extremely powerful tool to provide existential proofs for certain problems in different mathematical branches where other methods had failed utterly. One of its main concerns is to study the behavior of random variables. In particular, one common situation arises when these random variables count the number of bad events that occur in a combinatorial structure. The idea of the Poisson Paradigm is to estimate the probability of these bad events not happening at the same time when the dependencies among them are weak or rare. If this is the case, this probability should behave similarly as in the case where all the events are mutually independent. This idea gets reflected in several well-known tools, such as the Lovász Local Lemma or Suen inequality. The goal of this thesis is to study these techniques by setting new versions or refining the existing ones for particular cases, as well as providing new applications of them for different problems in combinatorics and graph theory. Next, we enumerate the main contributions of this thesis. The first part of this thesis extends a result of Erdös and Spencer on latin transversals [1]. They showed that an integer matrix such that no number appears many times, admits a latin transversal. This is equivalent to study rainbow matchings of edge-colored complete bipartite graphs. Under the same hypothesis of, we provide enumerating results on such rainbow matchings. The second part of the thesis deals with identifying codes, a set of vertices such that all vertices in the graph have distinct neighborhood within the code. We provide bounds on the size of a minimal identifying code in terms of the degree parameters and partially answer a question of Foucaud et al. On a different chapter of the thesis, we show that any dense enough graph has a very large spanning subgraph that admits a small identifying code. In some cases, proving the existence of a certain object is trivial. However, the same techniques allow us to obtain enumerative results. The study of permutation patterns is a good example of that. In the third part of the thesis we devise a new approach in order to estimate how many permutations of given length avoid a consecutive copy of a given pattern. In particular, we provide upper and lower bounds for them. One of the consequences derived from our approach is a proof of the CMP conjecture, stated by Elizalde and Noy as well as some new results on the behavior of most of the patterns. In the last part of this thesis, we focus on the Lonely Runner Conjecture, posed independently by Wills and Cusick and that has multiple applications in different mathematical fields. This well-known conjecture states that for any set of runners running along the unit circle with constant different speeds and starting at the same point, there is a moment where all of them are far enough from the origin. We improve the result of Chen on the gap of loneliness by studying the time when two runners are close to the origin. We also show an invisible runner type result, extending a result of Czerwinski and Grytczuk.

The objective of this thesis is to study cages, constructions and properties of such families of graphs. For this, the study of graphs without short cycles plays a fundamental role in order to develop some knowledge on their structure, so we can later deal with the problems on cages. Cages were introduced by Tutte in 1947. In 1963, Erdös and Sachs proved that (k, g) -cages exist for any given values of k and g. Since then, large amount of research in cages has been devoted to their construction. In this work we study structural properties such as the connectivity, diameter, and degree regularity of graphs without short cycles. In some sense, connectivity is a measure of the reliability of a network. Two graphs with the same edge-connectivity, may be considered to have different reliabilities, as a more refined index than the edge-connectivity, edge-superconnectivity is proposed together with some other parameters called restricted connectivities. By relaxing the conditions that are imposed for the graphs to be cages, we can achieve more refined connectivity properties on these families and also we have an approach to structural properties of the family of graphs with more restrictions (i.e., the cages). Our aim, by studying such structural properties of cages is to get a deeper insight into their structure so we can attack the problem of their construction. By way of example, we studied a condition on the diameter in relation to the girth pair of a graph, and as a corollary we obtained a result guaranteeing restricted connectivity of a special family of graphs arising from geometry, such as polarity graphs. Also, we obtained a result proving the edge superconnectivity of semiregular cages. Based on these studies it was possible to develop the study of cages. Therefore obtaining a relevant result with respect to the connectivity of cages, that is, cages are k/2-connected. And also arising from the previous work on girth pairs we obtained constructions for girth pair cages that proves a bound conjectured by Harary and Kovács, relating the order of girth pair cages with the one for cages. Concerning the degree and the diameter, there is the concept of a Moore graph, it was introduced by Hoffman and Singleton after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage. The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth (bipartite Moore graphs) as well as odd girth, and again these graphs are cages. Thus, Moore graphs give a lower bound for the order of cages, but they are known to exist only for very specific values of k, therefore it is interesting to study how far a cage is from this bound, this value is called the excess of a cage. We studied the excess of graphs and give a contribution, in the sense of the work of Biggs and Ito, relating the bipartition of girth 6 cages with their orders. Entire families of cages can be obtained from finite geometries, for example, the graphs of incidence of projective planes of order q a prime power, are (q+1, 6)-cages. Also by using other incidence structures such as the generalized quadrangles or generalized hexagons, it can be obtained families of cages of girths 8 and 12. In this thesis, we present a construction of an entire family of girth 7 cages that arises from some combinatorial properties of the incidence graphs of generalized quadrangles of order (q,q).

Esta tesis se divide en dos partes. La primera parte contiene el estudio de tres pesos o profundidades, asociados a conjuntos finitos de puntos en el plano: el peso definido por las capas convexas, convex depth (introducido por Hubert (72) y Barnett (76)), la separabilidad lineal, también conocido por location, halfspace o Tukey depth (Tukey 75) y el peso Delaunay (Green 81). De la noción de peso, se obtiene una estratificación de los conjuntos de puntos en el plano en capas y una partición del plano en regiones o niveles, cuyas fronteras son conocidas por depth contours. Se definen los conceptos de capa y nivel en los tres pesos señalados y se estudian sus propiedades y complejidades. Chazelle obtuvo métodos para hallar en tiempo óptimo las capas convexas, que coinciden con las fronteras de los niveles convexos. En esta tesis, para los pesos de separabilidad lineal y Delaunay, se proporcionan algoritmos de obtención, tanto de capas como de niveles, y de cálculo del peso de un punto nuevo que se incorpore a la nube. De forma independiente, han sido obtenidos para el peso de la separabilidad lineal los algoritmos de construcción de los niveles, location depth contours, y el de cálculo del peso de un punto nuevo, por Miller et al. (01). Para los tres pesos mencionados, se analizan árboles generadores, poligonizaciones o triangulaciones, con peso mínimo, donde el peso se ha considerado como la suma de los pesos de las aristas de dichas estructuras. Se obtienen propiedades generales entorno a la caracterización de tales estructuras y algoritmos de obtención para alguna de ellas. Se definen dos pesos relacionados con la separabilidad mediante cuñas: el peso según dominación isotética y la separabilidad . En ambos, se dan algoritmos para el cálculo de los pesos de los puntos de un conjunto dado. La separabilidad  está estrechamente relacionada con la enumeración eficiente de (,k)-sets. Se realiza un estudio combinatorio del conjunto de (,k)-sets para nubes de puntos en el plano y se describen algoritmos de construcción de todos los (,k)-sets en cada uno de los cuatro casos posibles, según sean,  o k, fijos o variables. En la segunda parte, se tratan diversos problemas de transversalidad. Se obtienen resultados acerca de la caracterización de las permutaciones realizables, tanto como polígonos simples, como convexos, sobre arreglos de rectas. Para colecciones de segmentos en el plano, se definen cuña y círculo transversales separadores. Se realiza un análisis del orden de estos elementos transversales separadores y se obtienen diversos algoritmos de decisión de existencia de los mismos y construcción de todos ellos. Para colecciones de círculos, también se define el círculo transversal separador y se obtiene un algoritmo de existencia y construcción de dichos círculos para círculos con el mismo radio., This thesis can be divided into two parts. The first part contains the study of three weights or depths associated to finite point sets in the plane: the convex depth convex hull peeling depth (introduced by Hubert (72) and Barnett (76)), the location depth (also known by halfspace or Tukey depth (Tukey (75)), and the Delaunay depth (Green (81)).From any notion of depth, a stratification of the point sets of the plane into layers and a partition of the plane into regions or levels are obtained. The boundaries of the levels are known by depth contours. We define the concepts of layers and levels for all three depths and we study their properties and their complexities. Chazelle obtained methods to find the layers, which are the boundaries of the convex levels, with an optimal time algorithm. We present the algorithms for constructing the layers and levels, in location and Delaunay depths. Also, for both depths, we show algorithms to calculate the depth of a new point joining the cloud. In an independent way, the algorithms to obtain the levels (location depth contours) and to calculate the location depth of a new point, are obtained by Miller et al. (01).For each one of the three mentioned depths, we study the geometric structures (spanning trees, polygonizations and triangulations) with minimum weight, where this weight has been considered as t-weight (the addition of the weight of their edges). We obtain general properties about the characterization of such structures and some algorithms to obtain them. We define two depths related with the separability by wedges: the isothetic-domination and the -separability which generalizes the location depth. We develop the algorithms in order to obtain the depths of all points of a given set in both cases. The -separability (in particular the location depth) is closely related with the efficient enumeration of the (,k)-sets. We make a combinatorial study of the (,k)-sets for point sets in the plane. We give lower and upper bounds for the maximum number of the (,k)-sets and we give algorithms for constructing all them, in each one of the four cases according to the case where  or k are fixed or variable.In the second part, we consider some transversality problems. We obtain results about the characterization of the realizable permutations both as simple and as convex polygons, over arrangements of lines. We also study some transversality problems with wedges and circles. We have defined the separating transversal wedge and the separating transversal circle for sets of segments. We analyze the size of the set of the transversal elements. Furthermore, we obtain some decision algorithms on the existence and construction of all of them. Finally, we define also the separating transversal circle for sets of circles and we obtain an algorithm for sets of circles with the same radius.

DE LA TESISSi un graf G admet un etiquetament super edge magic, aleshores G es diu que és un graf super edge màgic. La tesis està principalment enfocada a l'estudi del conjunt de grafs que admeten etiquetaments super edge magic així com també a desenvolupar relacions entre aquest tipus d'etiquetaments i altres etiquetaments molt estudiats com ara els etiquetaments graciosos i armònics, entre d'altres. De fet, els etiquetaments super edge magic serveixen com nexe d'unió entre diferents tipus d'etiquetaments, i per tant moltes relacions entre etiquetaments poden ser obtingudes d'aquesta forma. A la tesis també es proposa una nova manera de pensar en la ja famosa conjectura que afirma que tots els arbres admeten un etiquetament super edge magic. Això és, per a cada arbre T trobam un arbre super edge magic T' que conté a T com a subgraf, i l'ordre de T'no és massa gran quan el comparam amb l'ordre de T . Un problema de naturalesa similar al problema anterior, en el sentit que intentam trobar un graf super edge magic lo més petit possible i que contengui a cert tipus de grafs, i que ha estat completament resolt a la tesis es pot enunciar com segueix.Problema: Quin és un graf conexe G super edge magic d'ordre més petit que conté al graf complet Kn com a subgraf?.La solució d'aquest problema és prou interessant ja que relaciona els etiquetaments super edge magic amb un concepte clàssic de la teoria aditiva de nombres com són els conjunts de Sidon dèbils, també coneguts com well spread sets.De fet, aquesta no és la única vegada que el concepte de conjunt de Sidon apareix a la tesis. També quan a la tesis es tracta el tema de la deficiència , els conjunts de Sidon són d'una gran utilitat. La deficiencia super edge magic d'un graf és una manera de mesurar quan d'aprop està un graf de ser super edge magic. Tècnicament parlant, la deficiència super edge magic d'un graf G es defineix com el mínim número de vèrtexs aillats amb els que hem d'unirG perque el graf resultant sigui super edge magic. Si d'aquesta manera no aconseguim mai que el graf resultant sigui super edge magic, aleshores deim que la deficiència del graf és infinita. A la tesis, calculam la deficiència super edge magic de moltes families importants de grafs, i a més donam alguns resultats generals, sobre aquest concepte.Per acabar aquest document, simplement diré que al llarg de la tesis molts d'exemples que completen la tesis, i que fan la seva lectura més agradable i entenible han estat introduits., OF THESISIf a graph G admits a super edge magic labeling, then G is called a super edge magic graph. The thesis is mainly devoted to study the set of graphs which admit super edge magic labelings as well as to stablish and study relations with other well known labelings.For instance, graceful and harmonic labelings, among others, since many relations among labelings can be obtained using super edge magic labelings as the link.In the thesis we also provide a new approach to the already famous conjecture that claims that every tree is super edge magic. We attack this problem by finding for any given tree T a super edge magic tree T' that contains T as a subgraph, and the order of T'is not too large if we compare it with the order of T .A similar problem to this one, in the sense of finding small host super edge magic graphs for certain type of graphs, which is completely solved in the thesis, is the following one.Problem: Find the smallest order of a connected super edge magic graph G that contains the complete graph Kn as a subgraph.The solution of this problem has particular interest since it relates super edge magic labelings with the additive number theoretical concept of weak Sidon set, also known as well spread set. In fact , this is not the only time that this concept appears in the thesis.Also when studying the super edge magic deficiency, additive number theory and in particular well spread sets have proven to be very useful. The super edge magic deficiency of graph is a way of measuring how close is graph to be super edge magic.Properly speaking, the super edge magic deficiency of a graph G is defined to be the minimum number of isolated vertices that we have to union G with, so that the resulting graph is super edge magic. If no matter how many isolated vertices we union G with, the resulting graph is never super edge magic, then the super edge magic deficiency is defined to be infinity. In the thesis, we compute the super edge magic deficiency of may important families of graphs and we also provide some general results, involving this concept.Finally, and in order to bring this document to its end, I will just mention that many examples that improve the clarity of the thesis and makes it easy to read, can be found along the hole work.

Los estudios desarrollados se enmarcan, dentro de la teoría de grafos, en el análisis de condiciones suficientes para obtener algunas medidas de conectividad optima.se han estudiado condiciones de tipo mixto para el caso de dígrafos bipartitos que mejoran los conocidos hasta el momento.se han estudiado la t-distancia conectividad, construyendo dígrafos que muestran la independencia de los parámetros que le definen y obteniendo cotas superiores sobre el diámetro que garantizan valores óptimos para las mismas.se ha introducido el concepto de diámetro condicional que ha permitido la ampliación de las cotas conocidas sobre el diámetro, así como la mejora de algunas de ellas. Por último se han obtenido nuevas condiciones de tipo chartrand para la conectividad y la superconectividad de dígrafos s-geodeticos.