Hispana. Acceso en línea al Patrimonio Cultural Digital Español

Está en:  › Datos de registro

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

Identificadores del recurso

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

Procedencia

(Tesis de la Universitat Politècnica de Catalunya)

Ficha

Título:: (1, ≤ ℓ)-identifying codes in digraphs and graphs
Tema:: Adjacency matrix; Graph; Digraph; Dominating set; Edge-identifying code; Eigenvalues; Eeigenvectors; Linedigraph; Separating set; Spectra; Àrees temàtiques de la UPC::Matemàtiques i estadística; 512
Descripción:: 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
Fuente:: TDX (Tesis Doctorals en Xarxa)
Idioma:: English
Autor/Productor:: Martínez Barona, Berenice
Editor:: Universitat Politècnica de Catalunya
Otros colaboradores/productores:: Balbuena Martínez, Camino; Dalfó Simó, Cristina; Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística
Derechos:: 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/; info:eu-repo/semantics/openAccess
Fecha:: 2020-10-09T16:02:17Z; 2020-09-14
Tipo de recurso:: info:eu-repo/semantics/doctoralThesis; info:eu-repo/semantics/publishedVersion
Formato:: 102 p.; application/pdf

oai_dc

Descargar XML

<?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>Balbuena Martínez, Camino</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>Adjacency matrix</dc:subject>
7. <dc:subject>Graph</dc:subject>
8. <dc:subject>Digraph</dc:subject>
9. <dc:subject>Dominating set</dc:subject>
10. <dc:subject>Edge-identifying code</dc:subject>
11. <dc:subject>Eigenvalues</dc:subject>
12. <dc:subject>Eeigenvectors</dc:subject>
13. <dc:subject>Linedigraph</dc:subject>
14. <dc:subject>Separating set</dc:subject>
15. <dc:subject>Spectra</dc:subject>
16. <dc:subject>Àrees temàtiques de la UPC::Matemàtiques i estadística</dc:subject>
17. <dc:subject>512</dc:subject>
18. <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>
19. <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>
20. <dc:date>2020-10-09T16:02:17Z</dc:date>
21. <dc:date>2020-10-09T16:02:17Z</dc:date>
22. <dc:date>2020-09-14</dc:date>
23. <dc:type>info:eu-repo/semantics/doctoralThesis</dc:type>
24. <dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
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>info:eu-repo/semantics/openAccess</dc:rights>
30. <dc:format>102 p.</dc:format>
31. <dc:format>application/pdf</dc:format>
32. <dc:format>application/pdf</dc:format>
33. <dc:publisher>Universitat Politècnica de Catalunya</dc:publisher>
34. <dc:source>TDX (Tesis Doctorals en Xarxa)</dc:source>
</oai_dc:dc>

dim

Descargar XML

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

<dim:dim schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
1. <dim:field element="contributor" mdschema="dc">Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística</dim:field>
2. <dim:field authority="913c97aa-beaa-404d-b584-5e328cb19d80" confidence="-1" element="contributor" mdschema="dc" qualifier="author">Martínez Barona, Berenice</dim:field>
3. <dim:field element="contributor" lang="en_US" mdschema="dc" qualifier="authoremail">bere.mtz.barona@gmail.com</dim:field>
4. <dim:field element="contributor" lang="en_US" mdschema="dc" qualifier="authoremailshow">false</dim:field>
5. <dim:field authority="c09a47b6-263a-422a-a2ab-283aae6bcdf5" confidence="-1" element="contributor" mdschema="dc" qualifier="director">Balbuena Martínez, Camino</dim:field>
6. <dim:field authority="e55aa1e0-4aef-4109-b80f-3d22e135b28c" confidence="-1" element="contributor" mdschema="dc" qualifier="codirector">Dalfó Simó, Cristina</dim:field>
7. <dim:field element="date" mdschema="dc" qualifier="accessioned">2020-10-09T16:02:17Z</dim:field>
8. <dim:field element="date" mdschema="dc" qualifier="available">2020-10-09T16:02:17Z</dim:field>
9. <dim:field element="date" mdschema="dc" qualifier="issued">2020-09-14</dim:field>
10. <dim:field element="identifier" mdschema="dc" qualifier="uri">http://hdl.handle.net/10803/669726</dim:field>
11. <dim:field element="description" lang="en_US" mdschema="dc" qualifier="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.</dim:field>
12. <dim:field element="description" lang="en_US" mdschema="dc" qualifier="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</dim:field>
13. <dim:field element="format" lang="en_US" mdschema="dc" qualifier="extent">102 p.</dim:field>
14. <dim:field element="format" mdschema="dc" qualifier="mimetype">application/pdf</dim:field>
15. <dim:field element="language" lang="en_US" mdschema="dc" qualifier="iso">eng</dim:field>
16. <dim:field element="publisher" mdschema="dc">Universitat Politècnica de Catalunya</dim:field>
17. <dim:field element="rights" mdschema="dc" qualifier="license">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/</dim:field>
18. <dim:field element="rights" lang="*" mdschema="dc" qualifier="uri">http://creativecommons.org/licenses/by-nc-nd/4.0/</dim:field>
19. <dim:field element="rights" mdschema="dc" qualifier="accessLevel">info:eu-repo/semantics/openAccess</dim:field>
20. <dim:field element="source" mdschema="dc">TDX (Tesis Doctorals en Xarxa)</dim:field>
21. <dim:field element="subject" lang="en_US" mdschema="dc">Adjacency matrix</dim:field>
22. <dim:field element="subject" lang="en_US" mdschema="dc">Graph</dim:field>
23. <dim:field element="subject" lang="en_US" mdschema="dc">Digraph</dim:field>
24. <dim:field element="subject" lang="en_US" mdschema="dc">Dominating set</dim:field>
25. <dim:field element="subject" lang="en_US" mdschema="dc">Edge-identifying code</dim:field>
26. <dim:field element="subject" lang="en_US" mdschema="dc">Eigenvalues</dim:field>
27. <dim:field element="subject" lang="en_US" mdschema="dc">Eeigenvectors</dim:field>
28. <dim:field element="subject" lang="en_US" mdschema="dc">Linedigraph</dim:field>
29. <dim:field element="subject" lang="en_US" mdschema="dc">Separating set</dim:field>
30. <dim:field element="subject" lang="en_US" mdschema="dc">Spectra</dim:field>
31. <dim:field element="subject" lang="en_US" mdschema="dc" qualifier="other">Àrees temàtiques de la UPC::Matemàtiques i estadística</dim:field>
32. <dim:field element="subject" lang="en_US" mdschema="dc" qualifier="udc">512</dim:field>
33. <dim:field element="title" lang="en_US" mdschema="dc">(1, ≤ ℓ)-identifying codes in digraphs and graphs</dim:field>
34. <dim:field element="type" mdschema="dc">info:eu-repo/semantics/doctoralThesis</dim:field>
35. <dim:field element="type" mdschema="dc">info:eu-repo/semantics/publishedVersion</dim:field>
36. <dim:field element="embargo" lang="en_US" mdschema="dc" qualifier="terms">cap</dim:field>
</dim:dim>

etdms

Descargar XML

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

<thesis schemaLocation="http://www.ndltd.org/standards/metadata/etdms/1.0/ http://www.ndltd.org/standards/metadata/etdms/1.0/etdms.xsd">
1. <title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</title>
2. <creator>Martínez Barona, Berenice</creator>
3. <contributor>bere.mtz.barona@gmail.com</contributor>
4. <contributor>false</contributor>
5. <contributor>Balbuena Martínez, Camino</contributor>
6. <contributor>Dalfó Simó, Cristina</contributor>
7. <subject>Adjacency matrix</subject>
8. <subject>Graph</subject>
9. <subject>Digraph</subject>
10. <subject>Dominating set</subject>
11. <subject>Edge-identifying code</subject>
12. <subject>Eigenvalues</subject>
13. <subject>Eeigenvectors</subject>
14. <subject>Linedigraph</subject>
15. <subject>Separating set</subject>
16. <subject>Spectra</subject>
17. <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.</description>
18. <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</description>
19. <date>2020-10-09</date>
20. <date>2020-10-09</date>
21. <date>2020-09-14</date>
22. <type>info:eu-repo/semantics/doctoralThesis</type>
23. <type>info:eu-repo/semantics/publishedVersion</type>
24. <identifier>http://hdl.handle.net/10803/669726</identifier>
25. <language>eng</language>
26. <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/</rights>
27. <rights>http://creativecommons.org/licenses/by-nc-nd/4.0/</rights>
28. <rights>info:eu-repo/semantics/openAccess</rights>
29. <publisher>Universitat Politècnica de Catalunya</publisher>
30. <source>TDX (Tesis Doctorals en Xarxa)</source>
</thesis>

marc

Descargar XML

<?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">http://hdl.handle.net/10803/669726</subfield>
  </datafield>
8. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Adjacency matrix</subfield>
  </datafield>
9. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Graph</subfield>
  </datafield>
10. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Digraph</subfield>
  </datafield>
11. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Dominating set</subfield>
  </datafield>
12. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Edge-identifying code</subfield>
  </datafield>
13. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Eigenvalues</subfield>
  </datafield>
14. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Eeigenvectors</subfield>
  </datafield>
15. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Linedigraph</subfield>
  </datafield>
16. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Separating set</subfield>
  </datafield>
17. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Spectra</subfield>
  </datafield>
18. <datafield ind1="0" ind2="0" tag="245">
  1. <subfield code="a">(1, ≤ ℓ)-identifying codes in digraphs and graphs</subfield>
  </datafield>
</record>

marc_ccuc

Descargar XML

<?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>nam a 5i 4500</leader>
2. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Adjacency matrix</subfield>
  </datafield>
3. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Graph</subfield>
  </datafield>
4. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Digraph</subfield>
  </datafield>
5. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Dominating set</subfield>
  </datafield>
6. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Edge-identifying code</subfield>
  </datafield>
7. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Eigenvalues</subfield>
  </datafield>
8. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Eeigenvectors</subfield>
  </datafield>
9. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Linedigraph</subfield>
  </datafield>
10. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Separating set</subfield>
  </datafield>
11. <datafield ind1=" " ind2=" " tag="653">
  1. <subfield code="a">Spectra</subfield>
  </datafield>
12. <datafield ind1="1" ind2="0" tag="245">
  1. <subfield code="a">(1, ≤ ℓ)-identifying codes in digraphs and graphs</subfield>
  </datafield>
13. <datafield ind1=" " ind2="1" tag="264">
  1. <subfield code="a">[Barcelona] :</subfield>
  2. <subfield code="b">Universitat Politècnica de Catalunya,</subfield>
  3. <subfield code="c">2020</subfield>
  </datafield>
14. <datafield ind1="4" ind2="0" tag="856">
  1. <subfield code="z">Accés lliure</subfield>
  2. <subfield code="u">http://hdl.handle.net/10803/669726</subfield>
  </datafield>
15. <controlfield tag="007">cr |||||||||||</controlfield>
16. <controlfield tag="008">AAMMDDs2020 sp ||||fsm||||0|| 0 eng|c</controlfield>
17. <datafield ind1="1" ind2=" " tag="100">
  1. <subfield code="a">Martínez Barona, Berenice,</subfield>
  2. <subfield code="e">autor</subfield>
  </datafield>
18. <datafield ind1=" " ind2=" " tag="300">
  1. <subfield code="a">1 recurs en línia (102 pàgines)</subfield>
  </datafield>
19. <datafield ind1=" " ind2=" " tag="502">
  1. <subfield code="g">Tesi</subfield>
  2. <subfield code="b">Doctorat</subfield>
  3. <subfield code="c">Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística</subfield>
  4. <subfield code="d">2020</subfield>
  </datafield>
20. <datafield ind1="2" ind2=" " tag="710">
  1. <subfield code="a">Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística</subfield>
  </datafield>
21. <datafield ind1=" " ind2="4" tag="655">
  1. <subfield code="a">Tesis i dissertacions electròniques</subfield>
  </datafield>
22. <datafield ind1="1" ind2=" " tag="700">
  1. <subfield code="a">Balbuena Martínez, Camino,</subfield>
  2. <subfield code="e">supervisor acadèmic</subfield>
  </datafield>
23. <datafield ind1="1" ind2=" " tag="700">
  1. <subfield code="a">Dalfó Simó, Cristina,</subfield>
  2. <subfield code="e">supervisor acadèmic</subfield>
  </datafield>
24. <datafield ind1="0" ind2=" " tag="730">
  1. <subfield code="a">TDX</subfield>
  </datafield>
25. <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>
26. <datafield ind1=" " ind2=" " tag="998">
  1. <subfield code="a">p</subfield>
  </datafield>
27. <datafield ind1=" " ind2=" " tag="040">
  1. <subfield code="a">ES-BaCBU</subfield>
  2. <subfield code="b">cat</subfield>
  3. <subfield code="e">rda</subfield>
  4. <subfield code="c">ES-BaCBU</subfield>
  </datafield>
28. <datafield ind1=" " ind2=" " tag="336">
  1. <subfield code="a">text</subfield>
  2. <subfield code="b">txt</subfield>
  3. <subfield code="2">rdacontent</subfield>
  </datafield>
29. <datafield ind1=" " ind2=" " tag="337">
  1. <subfield code="a">informàtic</subfield>
  2. <subfield code="b">c</subfield>
  3. <subfield code="2">rdamedia</subfield>
  </datafield>
30. <datafield ind1=" " ind2=" " tag="338">
  1. <subfield code="a">recurs en línia</subfield>
  2. <subfield code="b">cr</subfield>
  3. <subfield code="2">rdacarrier</subfield>
  </datafield>
</record>

mets

Descargar XML

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

<mets ID=" DSpace_ITEM_10803-669726" OBJID=" hdl:10803/669726" 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-10-03T18:08:51Z">
  1. <agent ROLE="CUSTODIAN" TYPE="ORGANIZATION">
    1. <name>TDX (Tesis Doctorals en Xarxa)</name>
    </agent>
  </metsHdr>
2. <dmdSec ID="DMD_10803_669726">
  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">authoremail</mods:roleTerm>
        </mods:role>
        <mods:namePart>bere.mtz.barona@gmail.com</mods:namePart>
        </mods:name>
        <mods:name>
        <mods:role>
        <mods:roleTerm type="text">authoremailshow</mods:roleTerm>
        </mods:role>
        <mods:namePart>false</mods:namePart>
        </mods:name>
        <mods:name>
        <mods:role>
        <mods:roleTerm type="text">director</mods:roleTerm>
        </mods:role>
        <mods:namePart>Balbuena Martínez, Camino</mods:namePart>
        </mods:name>
        <mods:name>
        <mods:role>
        <mods:roleTerm type="text">codirector</mods:roleTerm>
        </mods:role>
        <mods:namePart>Dalfó Simó, Cristina</mods:namePart>
        </mods:name>
        <mods:extension>
        <mods:dateAccessioned encoding="iso8601">2020-10-09T16:02:17Z</mods:dateAccessioned>
        </mods:extension>
        <mods:extension>
        <mods:dateAvailable encoding="iso8601">2020-10-09T16:02:17Z</mods:dateAvailable>
        </mods:extension>
        <mods:originInfo>
        <mods:dateIssued encoding="iso8601">2020-09-14</mods:dateIssued>
        </mods:originInfo>
        <mods:identifier type="uri">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" />
        <mods:subject>
        <mods:topic>Adjacency matrix</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Graph</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Digraph</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Dominating set</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Edge-identifying code</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Eigenvalues</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Eeigenvectors</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Linedigraph</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Separating set</mods:topic>
        </mods:subject>
        <mods:subject>
        <mods:topic>Spectra</mods:topic>
        </mods:subject>
        <mods:titleInfo>
        <mods:title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</mods:title>
        </mods:titleInfo>
        <mods:genre>info:eu-repo/semantics/doctoralThesis info:eu-repo/semantics/publishedVersion</mods:genre>
        </mods:mods>
      </xmlData>
    </mdWrap>
  </dmdSec>
3. <amdSec ID="FO_10803_669726_1">
  1. <techMD ID="TECH_O_10803_669726_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://www.tdx.cat/bitstream/10803/669726/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_10803_669726_6">
  1. <techMD ID="TECH_T_10803_669726_6">
    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://www.tdx.cat/bitstream/10803/669726/6/TBMB1de1.pdf.txt</premis:objectIdentifierValue>
        </premis:objectIdentifier>
        <premis:objectCategory>File</premis:objectCategory>
        <premis:objectCharacteristics>
        <premis:fixity>
        <premis:messageDigestAlgorithm>MD5</premis:messageDigestAlgorithm>
        <premis:messageDigest>7c9138055a889486445daceb3f160140</premis:messageDigest>
        </premis:fixity>
        <premis:size>161904</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_10803_669726_1" CHECKSUM="445c93aa81c14fbf30ee33ab673bb936" CHECKSUMTYPE="MD5" GROUPID="GROUP_BITSTREAM_10803_669726_1" ID="BITSTREAM_ORIGINAL_10803_669726_1" MIMETYPE="application/pdf" SEQ="1" SIZE="3395689">
      1. <FLocat LOCTYPE="URL" href="https://www.tdx.cat/bitstream/10803/669726/1/TBMB1de1.pdf" type="simple" />
      </file>
    </fileGrp>
  2. <fileGrp USE="TEXT">
    1. <file ADMID="FT_10803_669726_6" CHECKSUM="7c9138055a889486445daceb3f160140" CHECKSUMTYPE="MD5" GROUPID="GROUP_BITSTREAM_10803_669726_6" ID="BITSTREAM_TEXT_10803_669726_6" MIMETYPE="text/plain" SEQ="6" SIZE="161904">
      1. <FLocat LOCTYPE="URL" href="https://www.tdx.cat/bitstream/10803/669726/6/TBMB1de1.pdf.txt" type="simple" />
      </file>
    </fileGrp>
  </fileSec>
6. <structMap LABEL="DSpace Object" TYPE="LOGICAL">
  1. <div ADMID="DMD_10803_669726" TYPE="DSpace Object Contents">
    1. <div TYPE="DSpace BITSTREAM">
      1. <fptr FILEID="BITSTREAM_ORIGINAL_10803_669726_1" />
      </div>
    </div>
  </structMap>
</mets>

mods

Descargar XML

<?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-09T16:02:17Z</mods:dateAvailable>
  </mods:extension>
3. <mods:extension>
  1. <mods:dateAccessioned encoding="iso8601">2020-10-09T16:02:17Z</mods:dateAccessioned>
  </mods:extension>
4. <mods:originInfo>
  1. <mods:dateIssued encoding="iso8601">2020-09-14</mods:dateIssued>
  </mods:originInfo>
5. <mods:identifier type="uri">http://hdl.handle.net/10803/669726</mods:identifier>
6. <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>
7. <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>
8. <mods:language>
  1. <mods:languageTerm>eng</mods:languageTerm>
  </mods:language>
9. <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>
10. <mods:accessCondition type="useAndReproduction">http://creativecommons.org/licenses/by-nc-nd/4.0/</mods:accessCondition>
11. <mods:accessCondition type="useAndReproduction">info:eu-repo/semantics/openAccess</mods:accessCondition>
12. <mods:subject>
  1. <mods:topic>Adjacency matrix</mods:topic>
  </mods:subject>
13. <mods:subject>
  1. <mods:topic>Graph</mods:topic>
  </mods:subject>
14. <mods:subject>
  1. <mods:topic>Digraph</mods:topic>
  </mods:subject>
15. <mods:subject>
  1. <mods:topic>Dominating set</mods:topic>
  </mods:subject>
16. <mods:subject>
  1. <mods:topic>Edge-identifying code</mods:topic>
  </mods:subject>
17. <mods:subject>
  1. <mods:topic>Eigenvalues</mods:topic>
  </mods:subject>
18. <mods:subject>
  1. <mods:topic>Eeigenvectors</mods:topic>
  </mods:subject>
19. <mods:subject>
  1. <mods:topic>Linedigraph</mods:topic>
  </mods:subject>
20. <mods:subject>
  1. <mods:topic>Separating set</mods:topic>
  </mods:subject>
21. <mods:subject>
  1. <mods:topic>Spectra</mods:topic>
  </mods:subject>
22. <mods:titleInfo>
  1. <mods:title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</mods:title>
  </mods:titleInfo>
23. <mods:genre>info:eu-repo/semantics/doctoralThesis</mods:genre>
24. <mods:genre>info:eu-repo/semantics/publishedVersion</mods:genre>
</mods:mods>

oaire

Descargar XML

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

<oaire:record schemaLocation="http://namespaceopenaire.eu/schema/oaire/">
1. <dc:title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</dc:title>
2. <datacite:creator>
  1. <datacite:creatorName>Martínez Barona, Berenice</datacite:creatorName>
  </datacite:creator>
3. <datacite:contributor>bere.mtz.barona@gmail.com</datacite:contributor>
4. <datacite:contributor>false</datacite:contributor>
5. <datacite:contributor>Balbuena Martínez, Camino</datacite:contributor>
6. <datacite:contributor>Dalfó Simó, Cristina</datacite:contributor>
7. <datacite:contributor>Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística</datacite:contributor>
8. <dc:subject>Adjacency matrix</dc:subject>
9. <dc:subject>Graph</dc:subject>
10. <dc:subject>Digraph</dc:subject>
11. <dc:subject>Dominating set</dc:subject>
12. <dc:subject>Edge-identifying code</dc:subject>
13. <dc:subject>Eigenvalues</dc:subject>
14. <dc:subject>Eeigenvectors</dc:subject>
15. <dc:subject>Linedigraph</dc:subject>
16. <dc:subject>Separating set</dc:subject>
17. <dc:subject>Spectra</dc:subject>
18. <dc:subject>Àrees temàtiques de la UPC::Matemàtiques i estadística</dc:subject>
19. <dc:subject>512</dc:subject>
20. <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>
21. <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>
22. <dc:date>2020-10-09T16:02:17Z</dc:date>
23. <dc:date>2020-10-09T16:02:17Z</dc:date>
24. <dc:date>2020-09-14</dc:date>
25. <dc:type>info:eu-repo/semantics/doctoralThesis</dc:type>
26. <dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
27. <datacite:alternateIdentifier>http://hdl.handle.net/10803/669726</datacite:alternateIdentifier>
28. <dc:language>eng</dc:language>
29. <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>
30. <dc:rights>http://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
31. <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
32. <dc:format>102 p.</dc:format>
33. <dc:format>application/pdf</dc:format>
34. <dc:format>application/pdf</dc:format>
35. <dc:publisher>Universitat Politècnica de Catalunya</dc:publisher>
36. <dc:source>TDX (Tesis Doctorals en Xarxa)</dc:source>
37. <oaire:file>https://www.tdx.cat/bitstream/10803/669726/1/TBMB1de1.pdf</oaire:file>
</oaire:record>

ore

Descargar XML

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

<atom:entry schemaLocation="http://www.w3.org/2005/Atom http://www.kbcafe.com/rss/atom.xsd.xml">
1. <atom:id>http://hdl.handle.net/10803/669726/ore.xml</atom:id>
2. <atom:link href="http://hdl.handle.net/10803/669726" rel="alternate" />
3. <atom:link href="http://hdl.handle.net/10803/669726/ore.xml" rel="http://www.openarchives.org/ore/terms/describes" />
4. <atom:link href="http://hdl.handle.net/10803/669726/ore.xml#atom" rel="self" type="application/atom+xml" />
5. <atom:published>2020-10-09T16:02:17Z</atom:published>
6. <atom:updated>2020-10-09T16:02:17Z</atom:updated>
7. <atom:source>
  1. <atom:generator>TDX (Tesis Doctorals en Xarxa)</atom:generator>
  </atom:source>
8. <atom:title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</atom:title>
9. <atom:author>
  1. <atom:name>Martínez Barona, Berenice</atom:name>
  </atom:author>
10. <atom:category label="Aggregation" scheme="http://www.openarchives.org/ore/terms/" term="http://www.openarchives.org/ore/terms/Aggregation" />
11. <atom:category scheme="http://www.openarchives.org/ore/atom/modified" term="2020-10-09T16:02:17Z" />
12. <atom:category label="DSpace Item" scheme="http://www.dspace.org/objectModel/" term="DSpaceItem" />
13. <atom:link href="https://www.tdx.cat/bitstream/10803/669726/1/TBMB1de1.pdf" length="3395689" rel="http://www.openarchives.org/ore/terms/aggregates" title="TBMB1de1.pdf" type="application/pdf" />
14. <oreatom:triples>
  1. <rdf:Description about="http://hdl.handle.net/10803/669726/ore.xml#atom">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceItem" />
    2. <dcterms:modified>2020-10-09T16:02:17Z</dcterms:modified>
    </rdf:Description>
  2. <rdf:Description about="https://www.tdx.cat/bitstream/10803/669726/6/TBMB1de1.pdf.txt">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceBitstream" />
    2. <dcterms:description>TEXT</dcterms:description>
    </rdf:Description>
  3. <rdf:Description about="https://www.tdx.cat/bitstream/10803/669726/1/TBMB1de1.pdf">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceBitstream" />
    2. <dcterms:description>ORIGINAL</dcterms:description>
    </rdf:Description>
  4. <rdf:Description about="https://www.tdx.cat/bitstream/10803/669726/2/license_url">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceBitstream" />
    2. <dcterms:description>CC-LICENSE</dcterms:description>
    </rdf:Description>
  5. <rdf:Description about="https://www.tdx.cat/bitstream/10803/669726/3/license_text">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceBitstream" />
    2. <dcterms:description>CC-LICENSE</dcterms:description>
    </rdf:Description>
  6. <rdf:Description about="https://www.tdx.cat/bitstream/10803/669726/4/license_rdf">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceBitstream" />
    2. <dcterms:description>CC-LICENSE</dcterms:description>
    </rdf:Description>
  7. <rdf:Description about="https://www.tdx.cat/bitstream/10803/669726/5/TBMB1de1.pdf.xml">
    1. <rdf:type resource="http://www.dspace.org/objectModel/DSpaceBitstream" />
    2. <dcterms:description>MEDIA_DOCUMENT</dcterms:description>
    </rdf:Description>
  </oreatom:triples>
</atom:entry>

qdc

Descargar XML

<?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, Camino</dc:contributor>
4. <dc:contributor>Dalfó Simó, Cristina</dc:contributor>
5. <dc:subject>Adjacency matrix</dc:subject>
6. <dc:subject>Graph</dc:subject>
7. <dc:subject>Digraph</dc:subject>
8. <dc:subject>Dominating set</dc:subject>
9. <dc:subject>Edge-identifying code</dc:subject>
10. <dc:subject>Eigenvalues</dc:subject>
11. <dc:subject>Eeigenvectors</dc:subject>
12. <dc:subject>Linedigraph</dc:subject>
13. <dc:subject>Separating set</dc:subject>
14. <dc:subject>Spectra</dc:subject>
15. <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>
16. <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>
17. <dcterms:dateAccepted>2020-10-09T16:02:17Z</dcterms:dateAccepted>
18. <dcterms:available>2020-10-09T16:02:17Z</dcterms:available>
19. <dcterms:created>2020-10-09T16:02:17Z</dcterms:created>
20. <dcterms:issued>2020-09-14</dcterms:issued>
21. <dc:type>info:eu-repo/semantics/doctoralThesis</dc:type>
22. <dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
23. <dc:identifier>http://hdl.handle.net/10803/669726</dc:identifier>
24. <dc:language>eng</dc:language>
25. <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>
26. <dc:rights>http://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
27. <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
28. <dc:publisher>Universitat Politècnica de Catalunya</dc:publisher>
29. <dc:source>TDX (Tesis Doctorals en Xarxa)</dc:source>
</qdc:qualifieddc>

rdf

Descargar XML

<?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:www.tdx.cat:10803/669726">
  1. <dc:title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</dc:title>
  2. <dc:creator>Martínez Barona, Berenice</dc:creator>
  3. <dc:contributor>bere.mtz.barona@gmail.com</dc:contributor>
  4. <dc:contributor>false</dc:contributor>
  5. <dc:contributor>Balbuena Martínez, Camino</dc:contributor>
  6. <dc:contributor>Dalfó Simó, Cristina</dc:contributor>
  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:date>2020-10-09T16:02:17Z</dc:date>
  20. <dc:date>2020-10-09T16:02:17Z</dc:date>
  21. <dc:date>2020-09-14</dc:date>
  22. <dc:type>info:eu-repo/semantics/doctoralThesis</dc:type>
  23. <dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
  24. <dc:identifier>http://hdl.handle.net/10803/669726</dc:identifier>
  25. <dc:language>eng</dc:language>
  26. <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>
  27. <dc:rights>http://creativecommons.org/licenses/by-nc-nd/4.0/</dc:rights>
  28. <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  29. <dc:publisher>Universitat Politècnica de Catalunya</dc:publisher>
  30. <dc:source>TDX (Tesis Doctorals en Xarxa)</dc:source>
  </ow:Publication>
</rdf:RDF>

uketd_dc

Descargar XML

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

<uketd_dc:uketddc schemaLocation="http://naca.central.cranfield.ac.uk/ethos-oai/2.0/ http://naca.central.cranfield.ac.uk/ethos-oai/2.0/uketd_dc.xsd">
1. <dc:title>(1, ≤ ℓ)-identifying codes in digraphs and graphs</dc:title>
2. <dc:creator>Martínez Barona, Berenice</dc:creator>
3. <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>
4. <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>
5. <uketdterms:institution>Universitat Politècnica de Catalunya</uketdterms:institution>
6. <dcterms:issued>2020-09-14</dcterms:issued>
7. <dc:type>info:eu-repo/semantics/doctoralThesis</dc:type>
8. <dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
9. <dc:language type="dcterms:ISO639-2">eng</dc:language>
10. <dcterms:isReferencedBy>http://hdl.handle.net/10803/669726</dcterms:isReferencedBy>
11. <dcterms:hasFormat>https://www.tdx.cat/bitstream/10803/669726/6/TBMB1de1.pdf.txt</dcterms:hasFormat>
12. <uketdterms:checksum type="uketdterms:MD5">7c9138055a889486445daceb3f160140</uketdterms:checksum>
13. <dc:identifier type="dcterms:URI">https://www.tdx.cat/bitstream/10803/669726/1/TBMB1de1.pdf</dc:identifier>
14. <uketdterms:checksum type="uketdterms:MD5">445c93aa81c14fbf30ee33ab673bb936</uketdterms:checksum>
15. <uketdterms:embargodate>cap</uketdterms:embargodate>
16. <dc:subject>Adjacency matrix</dc:subject>
17. <dc:subject>Graph</dc:subject>
18. <dc:subject>Digraph</dc:subject>
19. <dc:subject>Dominating set</dc:subject>
20. <dc:subject>Edge-identifying code</dc:subject>
21. <dc:subject>Eigenvalues</dc:subject>
22. <dc:subject>Eeigenvectors</dc:subject>
23. <dc:subject>Linedigraph</dc:subject>
24. <dc:subject>Separating set</dc:subject>
25. <dc:subject>Spectra</dc:subject>
26. <dc:subject>Àrees temàtiques de la UPC::Matemàtiques i estadística</dc:subject>
</uketd_dc:uketddc>

xoai

Descargar XML

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

<metadata schemaLocation="http://www.lyncode.com/xoai http://www.lyncode.com/xsd/xoai.xsd">
1. <element name="dc">
  1. <element name="contributor">
    1. <element name="none">
      1. <field name="value">Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística</field>
      </element>
    2. <element name="author">
      1. <element name="none">
        <field name="value">Martínez Barona, Berenice</field>
        <field name="authority">913c97aa-beaa-404d-b584-5e328cb19d80</field>
        <field name="confidence">-1</field>
        </element>
      </element>
    3. <element name="authoremail">
      1. <element name="en_US">
        <field name="value">bere.mtz.barona@gmail.com</field>
        </element>
      </element>
    4. <element name="authoremailshow">
      1. <element name="en_US">
        <field name="value">false</field>
        </element>
      </element>
    5. <element name="director">
      1. <element name="none">
        <field name="value">Balbuena Martínez, Camino</field>
        <field name="authority">c09a47b6-263a-422a-a2ab-283aae6bcdf5</field>
        <field name="confidence">-1</field>
        </element>
      </element>
    6. <element name="codirector">
      1. <element name="none">
        <field name="value">Dalfó Simó, Cristina</field>
        <field name="authority">e55aa1e0-4aef-4109-b80f-3d22e135b28c</field>
        <field name="confidence">-1</field>
        </element>
      </element>
    </element>
  2. <element name="date">
    1. <element name="accessioned">
      1. <element name="none">
        <field name="value">2020-10-09T16:02:17Z</field>
        </element>
      </element>
    2. <element name="available">
      1. <element name="none">
        <field name="value">2020-10-09T16:02:17Z</field>
        </element>
      </element>
    3. <element name="issued">
      1. <element name="none">
        <field name="value">2020-09-14</field>
        </element>
      </element>
    </element>
  3. <element name="identifier">
    1. <element name="uri">
      1. <element name="none">
        <field name="value">http://hdl.handle.net/10803/669726</field>
        </element>
      </element>
    </element>
  4. <element name="description">
    1. <element name="abstract">
      1. <element name="en_US">
        <field name="value">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.</field>
        <field name="value">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</field>
        </element>
      </element>
    </element>
  5. <element name="format">
    1. <element name="extent">
      1. <element name="en_US">
        <field name="value">102 p.</field>
        </element>
      </element>
    2. <element name="mimetype">
      1. <element name="none">
        <field name="value">application/pdf</field>
        </element>
      </element>
    </element>
  6. <element name="language">
    1. <element name="iso">
      1. <element name="en_US">
        <field name="value">eng</field>
        </element>
      </element>
    </element>
  7. <element name="publisher">
    1. <element name="none">
      1. <field name="value">Universitat Politècnica de Catalunya</field>
      </element>
    </element>
  8. <element name="rights">
    1. <element name="license">
      1. <element name="none">
        <field name="value">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/</field>
        </element>
      </element>
    2. <element name="uri">
      1. <element name="*">
        <field name="value">http://creativecommons.org/licenses/by-nc-nd/4.0/</field>
        </element>
      </element>
    3. <element name="accessLevel">
      1. <element name="none">
        <field name="value">info:eu-repo/semantics/openAccess</field>
        </element>
      </element>
    </element>
  9. <element name="source">
    1. <element name="none">
      1. <field name="value">TDX (Tesis Doctorals en Xarxa)</field>
      </element>
    </element>
  10. <element name="subject">
    1. <element name="en_US">
      1. <field name="value">Adjacency matrix</field>
      2. <field name="value">Graph</field>
      3. <field name="value">Digraph</field>
      4. <field name="value">Dominating set</field>
      5. <field name="value">Edge-identifying code</field>
      6. <field name="value">Eigenvalues</field>
      7. <field name="value">Eeigenvectors</field>
      8. <field name="value">Linedigraph</field>
      9. <field name="value">Separating set</field>
      10. <field name="value">Spectra</field>
      </element>
    2. <element name="other">
      1. <element name="en_US">
        <field name="value">Àrees temàtiques de la UPC::Matemàtiques i estadística</field>
        </element>
      </element>
    3. <element name="udc">
      1. <element name="en_US">
        <field name="value">512</field>
        </element>
      </element>
    </element>
  11. <element name="title">
    1. <element name="en_US">
      1. <field name="value">(1, ≤ ℓ)-identifying codes in digraphs and graphs</field>
      </element>
    </element>
  12. <element name="type">
    1. <element name="none">
      1. <field name="value">info:eu-repo/semantics/doctoralThesis</field>
      2. <field name="value">info:eu-repo/semantics/publishedVersion</field>
      </element>
    </element>
  13. <element name="embargo">
    1. <element name="terms">
      1. <element name="en_US">
        <field name="value">cap</field>
        </element>
      </element>
    </element>
  </element>
2. <element name="bundles">
  1. <element name="bundle">
    1. <field name="name">TEXT</field>
    2. <element name="bitstreams">
      1. <element name="bitstream">
        <field name="name">TBMB1de1.pdf.txt</field>
        <field name="originalName">TBMB1de1.pdf.txt</field>
        <field name="description">Extracted text</field>
        <field name="format">text/plain</field>
        <field name="size">161904</field>
        <field name="url">https://www.tdx.cat/bitstream/10803/669726/6/TBMB1de1.pdf.txt</field>
        <field name="checksum">7c9138055a889486445daceb3f160140</field>
        <field name="checksumAlgorithm">MD5</field>
        <field name="sid">6</field>
        <field name="drm">open access</field>
        </element>
      </element>
    </element>
  2. <element name="bundle">
    1. <field name="name">ORIGINAL</field>
    2. <element name="bitstreams">
      1. <element name="bitstream">
        <field name="name">TBMB1de1.pdf</field>
        <field name="originalName">TBMB1de1.pdf</field>
        <field name="description" />
        <field name="format">application/pdf</field>
        <field name="size">3395689</field>
        <field name="url">https://www.tdx.cat/bitstream/10803/669726/1/TBMB1de1.pdf</field>
        <field name="checksum">445c93aa81c14fbf30ee33ab673bb936</field>
        <field name="checksumAlgorithm">MD5</field>
        <field name="sid">1</field>
        <field name="drm">open access</field>
        </element>
      </element>
    </element>
  3. <element name="bundle">
    1. <field name="name">CC-LICENSE</field>
    2. <element name="bitstreams">
      1. <element name="bitstream">
        <field name="name">license_url</field>
        <field name="originalName">license_url</field>
        <field name="format">text/plain; charset=utf-8</field>
        <field name="size">49</field>
        <field name="url">https://www.tdx.cat/bitstream/10803/669726/2/license_url</field>
        <field name="checksum">4afdbb8c545fd630ea7db775da747b2f</field>
        <field name="checksumAlgorithm">MD5</field>
        <field name="sid">2</field>
        <field name="drm">open access</field>
        </element>
      2. <element name="bitstream">
        <field name="name">license_text</field>
        <field name="originalName">license_text</field>
        <field name="format">text/html; charset=utf-8</field>
        <field name="size">0</field>
        <field name="url">https://www.tdx.cat/bitstream/10803/669726/3/license_text</field>
        <field name="checksum">d41d8cd98f00b204e9800998ecf8427e</field>
        <field name="checksumAlgorithm">MD5</field>
        <field name="sid">3</field>
        <field name="drm">open access</field>
        </element>
      3. <element name="bitstream">
        <field name="name">license_rdf</field>
        <field name="originalName">license_rdf</field>
        <field name="format">application/rdf+xml; charset=utf-8</field>
        <field name="size">0</field>
        <field name="url">https://www.tdx.cat/bitstream/10803/669726/4/license_rdf</field>
        <field name="checksum">d41d8cd98f00b204e9800998ecf8427e</field>
        <field name="checksumAlgorithm">MD5</field>
        <field name="sid">4</field>
        <field name="drm">open access</field>
        </element>
      </element>
    </element>
  4. <element name="bundle">
    1. <field name="name">MEDIA_DOCUMENT</field>
    2. <element name="bitstreams">
      1. <element name="bitstream">
        <field name="name">TBMB1de1.pdf.xml</field>
        <field name="originalName">TBMB1de1.pdf.xml</field>
        <field name="description">Document Consulta</field>
        <field name="format">text/xml</field>
        <field name="size">105</field>
        <field name="url">https://www.tdx.cat/bitstream/10803/669726/5/TBMB1de1.pdf.xml</field>
        <field name="checksum">6328c69ebe0f437a4df38ca04daf8c9e</field>
        <field name="checksumAlgorithm">MD5</field>
        <field name="sid">5</field>
        <field name="drm">open access</field>
        </element>
      </element>
    </element>
  </element>
3. <element name="others">
  1. <field name="handle">10803/669726</field>
  2. <field name="identifier">oai:www.tdx.cat:10803/669726</field>
  3. <field name="lastModifyDate">2023-10-13 12:13:23.732</field>
  4. <field name="drm">open access</field>
  </element>
4. <element name="repository">
  1. <field name="name">TDX (Tesis Doctorals en Xarxa)</field>
  2. <field name="mail">pir@csuc.cat</field>
  </element>
</metadata>