Catalònica: Aggregator of digital content of Catalunya > Log data

It's in  › Log data

Linked Open Data

(1, ≤ ℓ)-identifying codes in digraphs and graphs

Resource identifiers

Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 .

http://hdl.handle.net/2117/330141

10.5821/dissertation-2117-330141

http://hdl.handle.net/10803/669726

Origin

(Universitat Politècnica de Catalunya. UPCommons - Recerca)

File

Title:: (1, ≤ ℓ)-identifying codes in digraphs and graphs
Subject:: Àrees temàtiques de la UPC::Matemàtiques i estadística; Adjacency matrix; Graph; Digraph; Dominating set; Edge-identifying code; Eigenvalues; Eeigenvectors; Linedigraph; Separating set; Spectra
Description:: The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs.; El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos; Postprint (published version)
Origin:: TDX (Tesis Doctorals en Xarxa)
Idioma:: English
Author/Producer:: Martínez Barona, Berenice
Editor:: Universitat Politècnica de Catalunya
Other collaborators/producers:: Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística; Balbuena Martínez, Maria Camino Teófila; Dalfó Simó, Cristina
Rights:: L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/; http://creativecommons.org/licenses/by-nc-nd/4.0/; Open Access
Date:: 2020-09-14
Resource type:: Doctoral thesis
Format:: 102 p.; application/pdf

oai_dc

<?xml version="1.0" encoding="UTF-8" ?>

< oai_dc:dc schemaLocation =" http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd " >
1. < dc:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ dc:title >
2. < dc:creator > Martínez Barona, Berenice </ dc:creator >
3. < dc:contributor > Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística </ dc:contributor >
4. < dc:contributor > Balbuena Martínez, Maria Camino Teófila </ dc:contributor >
5. < dc:contributor > Dalfó Simó, Cristina </ dc:contributor >
6. < dc:subject > Àrees temàtiques de la UPC::Matemàtiques i estadística </ dc:subject >
7. < dc:subject > Adjacency matrix </ dc:subject >
8. < dc:subject > Graph </ dc:subject >
9. < dc:subject > Digraph </ dc:subject >
10. < dc:subject > Dominating set </ dc:subject >
11. < dc:subject > Edge-identifying code </ dc:subject >
12. < dc:subject > Eigenvalues </ dc:subject >
13. < dc:subject > Eeigenvectors </ dc:subject >
14. < dc:subject > Linedigraph </ dc:subject >
15. < dc:subject > Separating set </ dc:subject >
16. < dc:subject > Spectra </ dc:subject >
17. < dc:description > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ dc:description >
18. < dc:description > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ dc:description >
19. < dc:description > Postprint (published version) </ dc:description >
20. < dc:date > 2020-09-14 </ dc:date >
21. < dc:type > Doctoral thesis </ dc:type >
22. < dc:identifier > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ dc:identifier >
23. < dc:identifier > http://hdl.handle.net/2117/330141 </ dc:identifier >
24. < dc:identifier > 10.5821/dissertation-2117-330141 </ dc:identifier >
25. < dc:identifier > http://hdl.handle.net/10803/669726 </ dc:identifier >
26. < dc:language > eng </ dc:language >
27. < dc:rights > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
28. < dc:rights > http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
29. < dc:rights > Open Access </ dc:rights >
30. < dc:format > 102 p. </ dc:format >
31. < dc:format > application/pdf </ dc:format >
32. < dc:publisher > Universitat Politècnica de Catalunya </ dc:publisher >
33. < dc:source > TDX (Tesis Doctorals en Xarxa) </ dc:source >
</ oai_dc:dc >

didl

<?xml version="1.0" encoding="UTF-8" ?>

< d:DIDL schemaLocation =" urn:mpeg:mpeg21:2002:02-DIDL-NS http://standards.iso.org/ittf/PubliclyAvailableStandards/MPEG-21_schema_files/did/didl.xsd " >
1. < d:DIDLInfo >
  1. < dcterms:created schemaLocation =" http://purl.org/dc/terms/ http://dublincore.org/schemas/xmls/qdc/dcterms.xsd " > 2020-10-11T00:03:09Z </ dcterms:created >
  </ d:DIDLInfo >
2. < d:Item id =" hdl_2117_330141 " >
  1. < d:Descriptor >
    1. < d:Statement mimeType =" application/xml; charset=utf-8 " >
      1. < dii:Identifier schemaLocation =" urn:mpeg:mpeg21:2002:01-DII-NS http://standards.iso.org/ittf/PubliclyAvailableStandards/MPEG-21_schema_files/dii/dii.xsd " > urn:hdl:2117/330141 </ dii:Identifier >
      </ d:Statement >
    </ d:Descriptor >
  2. < d:Descriptor >
    1. < d:Statement mimeType =" application/xml; charset=utf-8 " >
      1. < oai_dc:dc schemaLocation =" http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd " >
        
        < dc:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ dc:title >
        
        < dc:creator > Martínez Barona, Berenice </ dc:creator >
        
        < dc:contributor > Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística </ dc:contributor >
        
        < dc:subject > Àrees temàtiques de la UPC::Matemàtiques i estadística </ dc:subject >
        
        < dc:description > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ dc:description >
        
        < dc:description > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ dc:description >
        
        < dc:date > 2020-10-11T00:03:09Z </ dc:date >
        
        < dc:date > 2020-10-11T00:03:09Z </ dc:date >
        
        < dc:date > 2020-09-14 </ dc:date >
        
        < dc:type > Doctoral thesis </ dc:type >
        
        < dc:identifier > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ dc:identifier >
        
        < dc:identifier > http://hdl.handle.net/2117/330141 </ dc:identifier >
        
        < dc:identifier > 10.5821/dissertation-2117-330141 </ dc:identifier >
        
        < dc:identifier > http://hdl.handle.net/10803/669726 </ dc:identifier >
        
        < dc:language > eng </ dc:language >
        
        < dc:rights > http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
        
        < dc:rights > Open Access </ dc:rights >
        
        < dc:rights > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
        
        < dc:publisher > Universitat Politècnica de Catalunya </ dc:publisher >
        
        < dc:source > TDX (Tesis Doctorals en Xarxa) </ dc:source >
        
        </ oai_dc:dc >
      </ d:Statement >
    </ d:Descriptor >
  3. < d:Component id =" 2117_330141_1 " >
    1. < d:Resource mimeType =" application/pdf " ref =" https://upcommons.upc.edu/bitstream/2117/330141/1/TBMB1de1.pdf " />
    </ d:Component >
  </ d:Item >
</ d:DIDL >

edm

<?xml version="1.0" encoding="UTF-8" ?>

< rdf:RDF schemaLocation =" http://www.w3.org/1999/02/22-rdf-syntax-ns# http://www.europeana.eu/schemas/edm/EDM.xsd " >
1. < edm:ProvidedCHO about =" https://catalonica.bnc.cat/catalonicahub/lod/oai:upcommons.upc.edu:2117_--_330141#ent0 " >
  1. < dc:contributor > Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística </ dc:contributor >
  2. < dc:contributor > Balbuena Martínez, Maria Camino Teófila </ dc:contributor >
  3. < dc:contributor > Dalfó Simó, Cristina </ dc:contributor >
  4. < dc:creator > Martínez Barona, Berenice </ dc:creator >
  5. < dc:date > 2020-09-14 </ dc:date >
  6. < dc:description > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ dc:description >
  7. < dc:description > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ dc:description >
  8. < dc:description > Postprint (published version) </ dc:description >
  9. < dc:identifier > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ dc:identifier >
  10. < dc:identifier > http://hdl.handle.net/2117/330141 </ dc:identifier >
  11. < dc:identifier > 10.5821/dissertation-2117-330141 </ dc:identifier >
  12. < dc:identifier > http://hdl.handle.net/10803/669726 </ dc:identifier >
  13. < dc:language > eng </ dc:language >
  14. < dc:publisher > Universitat Politècnica de Catalunya </ dc:publisher >
  15. < dc:rights > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
  16. < dc:rights > http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
  17. < dc:rights > Open Access </ dc:rights >
  18. < dc:source > TDX (Tesis Doctorals en Xarxa) </ dc:source >
  19. < dc:subject > Àrees temàtiques de la UPC::Matemàtiques i estadística </ dc:subject >
  20. < dc:subject > Adjacency matrix </ dc:subject >
  21. < dc:subject > Graph </ dc:subject >
  22. < dc:subject > Digraph </ dc:subject >
  23. < dc:subject > Dominating set </ dc:subject >
  24. < dc:subject > Edge-identifying code </ dc:subject >
  25. < dc:subject > Eigenvalues </ dc:subject >
  26. < dc:subject > Eeigenvectors </ dc:subject >
  27. < dc:subject > Linedigraph </ dc:subject >
  28. < dc:subject > Separating set </ dc:subject >
  29. < dc:subject > Spectra </ dc:subject >
  30. < dc:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ dc:title >
  31. < dc:type > Doctoral thesis </ dc:type >
  32. < edm:type > TEXT </ edm:type >
  </ edm:ProvidedCHO >
2. < ore:Aggregation about =" https://catalonica.bnc.cat/catalonicahub/lod/oai:upcommons.upc.edu:2117_--_330141#ent1 " >
  1. < edm:aggregatedCHO resource =" https://catalonica.bnc.cat/catalonicahub/lod/oai:upcommons.upc.edu:2117_--_330141#ent0 " />
  2. < edm:dataProvider > Universitat Politècnica de Catalunya. UPCommons - Recerca </ edm:dataProvider >
  3. < edm:isShownAt resource =" http://hdl.handle.net/2117/330141 " />
  4. < edm:isShownBy resource =" https://upcommons.upc.edu/bitstream/2117/330141/1/TBMB1de1.pdf " />
  5. < edm:provider > Catalònica </ edm:provider >
  6. < edm:rights resource =" http://creativecommons.org/licenses/by-nc-nd/4.0/ " />
  </ ore:Aggregation >
</ rdf:RDF >

marc

<?xml version="1.0" encoding="UTF-8" ?>

< record schemaLocation =" http://www.loc.gov/MARC21/slim http://www.loc.gov/standards/marcxml/schema/MARC21slim.xsd " >
1. < leader > 00925njm 22002777a 4500 </ leader >
2. < datafield ind1 =" " ind2 =" " tag =" 042 " >
  1. < subfield code =" a " > dc </ subfield >
  </ datafield >
3. < datafield ind1 =" " ind2 =" " tag =" 720 " >
  1. < subfield code =" a " > Martínez Barona, Berenice </ subfield >
  2. < subfield code =" e " > author </ subfield >
  </ datafield >
4. < datafield ind1 =" " ind2 =" " tag =" 260 " >
  1. < subfield code =" c " > 2020-09-14 </ subfield >
  </ datafield >
5. < datafield ind1 =" " ind2 =" " tag =" 520 " >
  1. < subfield code =" a " > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ subfield >
  </ datafield >
6. < datafield ind1 =" " ind2 =" " tag =" 520 " >
  1. < subfield code =" a " > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ subfield >
  </ datafield >
7. < datafield ind1 =" 8 " ind2 =" " tag =" 024 " >
  1. < subfield code =" a " > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ subfield >
  </ datafield >
8. < datafield ind1 =" 8 " ind2 =" " tag =" 024 " >
  1. < subfield code =" a " > http://hdl.handle.net/2117/330141 </ subfield >
  </ datafield >
9. < datafield ind1 =" 8 " ind2 =" " tag =" 024 " >
  1. < subfield code =" a " > 10.5821/dissertation-2117-330141 </ subfield >
  </ datafield >
10. < datafield ind1 =" 8 " ind2 =" " tag =" 024 " >
  1. < subfield code =" a " > http://hdl.handle.net/10803/669726 </ subfield >
  </ datafield >
11. < datafield ind1 =" " ind2 =" " tag =" 653 " >
  1. < subfield code =" a " > Àrees temàtiques de la UPC::Matemàtiques i estadística </ subfield >
  </ datafield >
12. < datafield ind1 =" 0 " ind2 =" 0 " tag =" 245 " >
  1. < subfield code =" a " > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ subfield >
  </ datafield >
</ record >

mets

<?xml version="1.0" encoding="UTF-8" ?>

< mets ID =" DSpace_ITEM_2117-330141 " OBJID =" hdl:2117/330141 " PROFILE =" DSpace METS SIP Profile 1.0 " TYPE =" DSpace ITEM " schemaLocation =" http://www.loc.gov/METS/ http://www.loc.gov/standards/mets/mets.xsd " >
1. < metsHdr CREATEDATE =" 2024-09-05T15:11:44Z " >
  1. < agent ROLE =" CUSTODIAN " TYPE =" ORGANIZATION " >
    1. < name > UPCommons. Portal del coneixement obert de la UPC </ name >
    </ agent >
  </ metsHdr >
2. < dmdSec ID =" DMD_2117_330141 " >
  1. < mdWrap MDTYPE =" MODS " >
    1. < xmlData schemaLocation =" http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd " >
      1. < mods:mods schemaLocation =" http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd " >
        
        < mods:name >
        
        < mods:role >
        
        < mods:roleTerm type =" text " > author </ mods:roleTerm >
        
        </ mods:role >
        
        < mods:namePart > Martínez Barona, Berenice </ mods:namePart >
        
        </ mods:name >
        
        < mods:name >
        
        < mods:role >
        
        < mods:roleTerm type =" text " > other </ mods:roleTerm >
        
        </ mods:role >
        
        < mods:namePart > Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística </ mods:namePart >
        
        </ mods:name >
        
        < mods:extension >
        
        < mods:dateAccessioned encoding =" iso8601 " > 2020-10-11T00:03:09Z </ mods:dateAccessioned >
        
        </ mods:extension >
        
        < mods:extension >
        
        < mods:dateAvailable encoding =" iso8601 " > 2020-10-11T00:03:09Z </ mods:dateAvailable >
        
        </ mods:extension >
        
        < mods:originInfo >
        
        < mods:dateIssued encoding =" iso8601 " > 2020-09-14 </ mods:dateIssued >
        
        </ mods:originInfo >
        
        < mods:identifier type =" citation " > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ mods:identifier >
        
        < mods:identifier type =" uri " > http://hdl.handle.net/2117/330141 </ mods:identifier >
        
        < mods:identifier type =" doi " > 10.5821/dissertation-2117-330141 </ mods:identifier >
        
        < mods:identifier type =" tdx " > http://hdl.handle.net/10803/669726 </ mods:identifier >
        
        < mods:abstract > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs.El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ mods:abstract >
        
        < mods:language >
        
        < mods:languageTerm authority =" rfc3066 " > eng </ mods:languageTerm >
        
        </ mods:language >
        
        < mods:accessCondition type =" useAndReproduction " > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ mods:accessCondition >
        
        < mods:subject >
        
        < mods:topic > Àrees temàtiques de la UPC::Matemàtiques i estadística </ mods:topic >
        
        </ mods:subject >
        
        < mods:titleInfo >
        
        < mods:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ mods:title >
        
        </ mods:titleInfo >
        
        < mods:genre > Doctoral thesis </ mods:genre >
        
        </ mods:mods >
      </ xmlData >
    </ mdWrap >
  </ dmdSec >
3. < amdSec ID =" FO_2117_330141_1 " >
  1. < techMD ID =" TECH_O_2117_330141_1 " >
    1. < mdWrap MDTYPE =" PREMIS " >
      1. < xmlData schemaLocation =" http://www.loc.gov/standards/premis http://www.loc.gov/standards/premis/PREMIS-v1-0.xsd " >
        
        < premis:premis >
        
        < premis:object >
        
        < premis:objectIdentifier >
        
        < premis:objectIdentifierType > URL </ premis:objectIdentifierType >
        
        < premis:objectIdentifierValue > https://upcommons.upc.edu/bitstream/2117/330141/1/TBMB1de1.pdf </ premis:objectIdentifierValue >
        
        </ premis:objectIdentifier >
        
        < premis:objectCategory > File </ premis:objectCategory >
        
        < premis:objectCharacteristics >
        
        < premis:fixity >
        
        < premis:messageDigestAlgorithm > MD5 </ premis:messageDigestAlgorithm >
        
        < premis:messageDigest > 445c93aa81c14fbf30ee33ab673bb936 </ premis:messageDigest >
        
        </ premis:fixity >
        
        < premis:size > 3395689 </ premis:size >
        
        < premis:format >
        
        < premis:formatDesignation >
        
        < premis:formatName > application/pdf </ premis:formatName >
        
        </ premis:formatDesignation >
        
        </ premis:format >
        
        </ premis:objectCharacteristics >
        
        < premis:originalName > TBMB1de1.pdf </ premis:originalName >
        
        </ premis:object >
        
        </ premis:premis >
        
        </ xmlData >
      </ mdWrap >
    </ techMD >
  </ amdSec >
4. < amdSec ID =" FT_2117_330141_4 " >
  1. < techMD ID =" TECH_T_2117_330141_4 " >
    1. < mdWrap MDTYPE =" PREMIS " >
      1. < xmlData schemaLocation =" http://www.loc.gov/standards/premis http://www.loc.gov/standards/premis/PREMIS-v1-0.xsd " >
        
        < premis:premis >
        
        < premis:object >
        
        < premis:objectIdentifier >
        
        < premis:objectIdentifierType > URL </ premis:objectIdentifierType >
        
        < premis:objectIdentifierValue > https://upcommons.upc.edu/bitstream/2117/330141/4/TBMB1de1.pdf.txt </ premis:objectIdentifierValue >
        
        </ premis:objectIdentifier >
        
        < premis:objectCategory > File </ premis:objectCategory >
        
        < premis:objectCharacteristics >
        
        < premis:fixity >
        
        < premis:messageDigestAlgorithm > MD5 </ premis:messageDigestAlgorithm >
        
        < premis:messageDigest > e797b30f5ffe5c907ee9c7de7fe85db4 </ premis:messageDigest >
        
        </ premis:fixity >
        
        < premis:size > 161182 </ premis:size >
        
        < premis:format >
        
        < premis:formatDesignation >
        
        < premis:formatName > text/plain </ premis:formatName >
        
        </ premis:formatDesignation >
        
        </ premis:format >
        
        </ premis:objectCharacteristics >
        
        < premis:originalName > TBMB1de1.pdf.txt </ premis:originalName >
        
        </ premis:object >
        
        </ premis:premis >
        
        </ xmlData >
      </ mdWrap >
    </ techMD >
  </ amdSec >
5. < fileSec >
  1. < fileGrp USE =" ORIGINAL " >
    1. < file ADMID =" FO_2117_330141_1 " CHECKSUM =" 445c93aa81c14fbf30ee33ab673bb936 " CHECKSUMTYPE =" MD5 " GROUPID =" GROUP_BITSTREAM_2117_330141_1 " ID =" BITSTREAM_ORIGINAL_2117_330141_1 " MIMETYPE =" application/pdf " SEQ =" 1 " SIZE =" 3395689 " >
      1. < FLocat LOCTYPE =" URL " href =" https://upcommons.upc.edu/bitstream/2117/330141/1/TBMB1de1.pdf " type =" simple " />
      </ file >
    </ fileGrp >
  2. < fileGrp USE =" TEXT " >
    1. < file ADMID =" FT_2117_330141_4 " CHECKSUM =" e797b30f5ffe5c907ee9c7de7fe85db4 " CHECKSUMTYPE =" MD5 " GROUPID =" GROUP_BITSTREAM_2117_330141_4 " ID =" BITSTREAM_TEXT_2117_330141_4 " MIMETYPE =" text/plain " SEQ =" 4 " SIZE =" 161182 " >
      1. < FLocat LOCTYPE =" URL " href =" https://upcommons.upc.edu/bitstream/2117/330141/4/TBMB1de1.pdf.txt " type =" simple " />
      </ file >
    </ fileGrp >
  </ fileSec >
6. < structMap LABEL =" DSpace Object " TYPE =" LOGICAL " >
  1. < div ADMID =" DMD_2117_330141 " TYPE =" DSpace Object Contents " >
    1. < div TYPE =" DSpace BITSTREAM " >
      1. < fptr FILEID =" BITSTREAM_ORIGINAL_2117_330141_1 " />
      </ div >
    </ div >
  </ structMap >
</ mets >

mods

<?xml version="1.0" encoding="UTF-8" ?>

< mods:mods schemaLocation =" http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-1.xsd " >
1. < mods:name >
  1. < mods:namePart > Martínez Barona, Berenice </ mods:namePart >
  </ mods:name >
2. < mods:extension >
  1. < mods:dateAvailable encoding =" iso8601 " > 2020-10-11T00:03:09Z </ mods:dateAvailable >
  </ mods:extension >
3. < mods:extension >
  1. < mods:dateAccessioned encoding =" iso8601 " > 2020-10-11T00:03:09Z </ mods:dateAccessioned >
  </ mods:extension >
4. < mods:originInfo >
  1. < mods:dateIssued encoding =" iso8601 " > 2020-09-14 </ mods:dateIssued >
  </ mods:originInfo >
5. < mods:identifier type =" citation " > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ mods:identifier >
6. < mods:identifier type =" uri " > http://hdl.handle.net/2117/330141 </ mods:identifier >
7. < mods:identifier type =" doi " > 10.5821/dissertation-2117-330141 </ mods:identifier >
8. < mods:identifier type =" tdx " > http://hdl.handle.net/10803/669726 </ mods:identifier >
9. < mods:abstract > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ mods:abstract >
10. < mods:abstract > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ mods:abstract >
11. < mods:language >
  1. < mods:languageTerm > eng </ mods:languageTerm >
  </ mods:language >
12. < mods:accessCondition type =" useAndReproduction " > http://creativecommons.org/licenses/by-nc-nd/4.0/ </ mods:accessCondition >
13. < mods:accessCondition type =" useAndReproduction " > Open Access </ mods:accessCondition >
14. < mods:accessCondition type =" useAndReproduction " > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ mods:accessCondition >
15. < mods:subject >
  1. < mods:topic > Àrees temàtiques de la UPC::Matemàtiques i estadística </ mods:topic >
  </ mods:subject >
16. < mods:titleInfo >
  1. < mods:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ mods:title >
  </ mods:titleInfo >
17. < mods:genre > Doctoral thesis </ mods:genre >
</ mods:mods >

qdc

<?xml version="1.0" encoding="UTF-8" ?>

< qdc:qualifieddc schemaLocation =" http://purl.org/dc/elements/1.1/ http://dublincore.org/schemas/xmls/qdc/2006/01/06/dc.xsd http://purl.org/dc/terms/ http://dublincore.org/schemas/xmls/qdc/2006/01/06/dcterms.xsd http://dspace.org/qualifieddc/ http://www.ukoln.ac.uk/metadata/dcmi/xmlschema/qualifieddc.xsd " >
1. < dc:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ dc:title >
2. < dc:creator > Martínez Barona, Berenice </ dc:creator >
3. < dc:contributor > Balbuena Martínez, Maria Camino Teófila </ dc:contributor >
4. < dc:contributor > Dalfó Simó, Cristina </ dc:contributor >
5. < dc:contributor > Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística </ dc:contributor >
6. < dc:subject > Àrea temàtica UPC: Matemàtiques i estadística </ dc:subject >
7. < dc:subject > Adjacency matrix </ dc:subject >
8. < dc:subject > Graph </ dc:subject >
9. < dc:subject > Digraph </ dc:subject >
10. < dc:subject > Dominating set </ dc:subject >
11. < dc:subject > Edge-identifying code </ dc:subject >
12. < dc:subject > Eigenvalues </ dc:subject >
13. < dc:subject > Eeigenvectors </ dc:subject >
14. < dc:subject > Linedigraph </ dc:subject >
15. < dc:subject > Separating set </ dc:subject >
16. < dc:subject > Spectra </ dc:subject >
17. < dcterms:abstract > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ dcterms:abstract >
18. < dcterms:abstract > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ dcterms:abstract >
19. < dcterms:dateAccepted > 2020-10-11T00:03:09Z </ dcterms:dateAccepted >
20. < dcterms:available > 2020-10-11T00:03:09Z </ dcterms:available >
21. < dcterms:issued > 2020-09-14 </ dcterms:issued >
22. < dc:type > Doctoral thesis </ dc:type >
23. < dc:identifier > 10.5821/dissertation-2117-330141 </ dc:identifier >
24. < dc:identifier > http://hdl.handle.net/10803/669726 </ dc:identifier >
25. < dc:identifier type =" dcterms:URI " > http://hdl.handle.net/2117/330141 </ dc:identifier >
26. < dcterms:bibliographicCitation > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ dcterms:bibliographicCitation >
27. < dc:language > eng </ dc:language >
28. < dc:rights > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
29. < dc:rights > http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
30. < dcterms:accessRights > Open Access </ dcterms:accessRights >
31. < dcterms:extent > 102 p. </ dcterms:extent >
32. < dc:publisher > Universitat Politècnica de Catalunya </ dc:publisher >
33. < dc:source > TDX (Tesis Doctorals en Xarxa) </ dc:source >
34. < dcterms:identifier > https://upcommons.upc.edu/bitstream/2117/330141/3/TBMB1de1.pdf.jpg </ dcterms:identifier >
</ qdc:qualifieddc >

rdf

<?xml version="1.0" encoding="UTF-8" ?>

< rdf:RDF schemaLocation =" http://www.openarchives.org/OAI/2.0/rdf/ http://www.openarchives.org/OAI/2.0/rdf.xsd " >
1. < ow:Publication about =" oai:upcommons.upc.edu:2117/330141 " >
  1. < dc:title > (1, ≤ ℓ)-identifying codes in digraphs and graphs </ dc:title >
  2. < dc:creator > Martínez Barona, Berenice </ dc:creator >
  3. < dc:contributor > Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística </ dc:contributor >
  4. < dc:subject > Àrees temàtiques de la UPC::Matemàtiques i estadística </ dc:subject >
  5. < dc:description > The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs. </ dc:description >
  6. < dc:description > El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos </ dc:description >
  7. < dc:date > 2020-10-11T00:03:09Z </ dc:date >
  8. < dc:date > 2020-10-11T00:03:09Z </ dc:date >
  9. < dc:date > 2020-09-14 </ dc:date >
  10. < dc:type > Doctoral thesis </ dc:type >
  11. < dc:identifier > Martínez Barona, B. (1, ≤ ℓ)-identifying codes in digraphs and graphs. Tesi doctoral, UPC, Facultat de Matemàtiques i Estadística, 2020. DOI 10.5821/dissertation-2117-330141 . </ dc:identifier >
  12. < dc:identifier > http://hdl.handle.net/2117/330141 </ dc:identifier >
  13. < dc:identifier > 10.5821/dissertation-2117-330141 </ dc:identifier >
  14. < dc:identifier > http://hdl.handle.net/10803/669726 </ dc:identifier >
  15. < dc:language > eng </ dc:language >
  16. < dc:rights > http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
  17. < dc:rights > Open Access </ dc:rights >
  18. < dc:rights > L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ </ dc:rights >
  19. < dc:publisher > Universitat Politècnica de Catalunya </ dc:publisher >
  20. < dc:source > TDX (Tesis Doctorals en Xarxa) </ dc:source >
  </ ow:Publication >
</ rdf:RDF >

Biblioteca de Catalunya Carrer de l'Hospital, 56. 08001 Barcelona Email: catalonica@bnc.cat Tlf.: +34 932 702 300

OAI Repository