Pasar al contenido principal

OPTIMIZACION Y PROBLEMAS EXTREMALES EN TEORIA DE GRAFOS Y COMBINATORIA. APLICACIONES A LAS REDES DE COMUNICACION.

MTM2011-28800-C02-01

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2011
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 38
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

The jumping knight and other (super) edge-magic constructions

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
Let G be a graph of order p and size q with loops allowed. A bijective function f:V(G)∪E(G)→{i}p+qi=1 is an edge-magic labeling of G if the sum f(u)+f(uv)+f(v)=k is independent of the choice of the edge uv. The constant k is called either the valence, the magic weight or the magic sum of the labeling f. If a graph admits an edge-magic labeling, then it is called an edge-magic graph. Furthermore, if the function f meets the extra condition that f(V(G))={i}pi=1 then f is called a super edge-magic labeling and G is called a super edge-magic graph. A digraph D admits a labeling, namely l, if its underlying graph, und(D) admits l. In this paper, we introduce a new construction of super edge-magic labelings which are related to the classical jump of the knight on the chess game. We also use super edge-magic labelings of digraphs together with a generalization of the Kronecker product to get edge-magic labelings of some families of graphs., The research conducted in this document by the first and third authors has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Langford sequences and a product of digraphs

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
Skolem and Langford sequences and their many generalizations have applications in numerous areas. The -product is a generalization of the direct product of digraphs. In this paper we use the -product and super edge-magic digraphs to construct an exponential number of Langford sequences with certain order and defect. We also apply this procedure to extended Skolem sequences., The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and symbolically by the Catalan Research Council under grant 2014SGR1147.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Moments in graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Garriga, Ernest
Research supported by the Ministerio de Ciencia e Innovación (Spain) and the European Regional Development Fund under project MTM2011-28800-C02- 01, and by the Catalan Research Council under project 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Connectivity and other invariants of generalized products of graphs

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
Figueroa-Centeno et al. [4] introduced the following product of digraphs let D be a digraph and let Γ be a family of digraphs such that V (F) = V for every F∈Γ . Consider any function h:E(D)→Γ . Then the product D⊗hΓ is the digraph with vertex set V(D)×V and ((a,x),(b,y))∈E(D⊗hΓ) if and only if (a,b)∈E(D) and (x,y)∈E(h(a,b)) . In this paper, we deal with the undirected version of the ⊗h -product, which is a generalization of the classical direct product of graphs and, motivated by the ⊗h -product, we also recover a generalization of the classical lexicographic product of graphs, namely the ∘h -product, that was introduced by Sabidussi in 1961. We provide two characterizations for the connectivity of G⊗hΓ that generalize the existing one for the direct product. For G∘hΓ , we provide exact formulas for the connectivity and the edge-connectivity, under the assumption that V (F) = V , for all F∈Γ . We also introduce some miscellaneous results about other invariants in terms of the factors of both, the ⊗h -product and the ∘h -product. Some of them are easily obtained from the corresponding product of two graphs, but many others generalize the existing ones for the direct and the lexicographic product, respectively. We end up the paper by presenting some structural properties. An interesting result in this direction is a characterization for the existence of a nontrivial decomposition of a given graph G in terms of ⊗h -product., The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

The (∆,D) and (∆,N) problems in double-step digraphs with unilateral distance

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
We study the (Delta,D) and (Delta,N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by changing the directions of all the arcs. The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree $\Delta$ and the unilateral diameter D*, whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices. Moreover, we compute the mean unilateral distance of the digraphs in the families considered., This research was supported by the Ministry of Science and Innovation (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01-1 and by the Catalan Research Council under project 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Rainbow eulerian multidigraphs and the product of cycles

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of digraphs such that $V(F)=V$ for every $F\in \Gamma$. Consider any function $h:E(D)\longrightarrow\Gamma $. Then the product $D\otimes_{h} \Gamma$ is the digraph with vertex set $V(D)\times V$ and $((a,x),(b,y))\in E(D\otimes_{h}\Gamma)$ if and only if $ (a,b)\in E(D)$ and $ (x,y)\in E(h (a,b))$. In this paper we use rainbow eulerian multidigraphs and permutations as a way to characterize the $\otimes_h$-product of oriented cycles. We study the behavior of the $\otimes_h$-product when applied to digraphs with unicyclic components. The results obtained allow us to get edge-magic labelings of graphs formed by the union of unicyclic components and with different magic sums., Supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

The Diameter of Cyclic Kautz Digraphs

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
A prominent problem in Graph Theory is to find extremal graphs or digraphs with restrictions in their diameter, degree and number of vertices. Here we obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and degree there is no other digraph with a smaller diameter. This new family is called modified cyclic digraphs M CK(d, l) and it is derived from the Kautz digraphs K(d, l). It is well-known that the Kautz digraphs K(d, l) have the smallest diameter among all digraphs with their number of vertices and degree. Here we define the cyclic Kautz digraphs CK(d, l), whose vertices are labeled by all possible sequences a1 . . . al of length l, such that each character ai is chosen from an alphabet con taining d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1 l = al., K. Böhmová is a recipient of the Google Europe Fellowship in Optimization Algorithms, and this research is supported in part by this Google Fellowship. Research of C. Dalfó supported by projects MINECO MTM2011-28800-C02-01, and 2014SGR1147 from the Catalan Government. Research of C. Huemer supported by projects MINECO MTM2012-30951 and Gen. Cat. DGR 2014SGR46.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

The degree/diameter problem in maximal planar bipartite graphs

  • Dalfó, Cristina
  • Huemer, Clemens
  • Salas Piñón, Julián
Research of C. Dalf ́o supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund under project MTM2011-28800-C02-01, and by the Catalan Research Council under project 2009SGR1387. Research of C. Huemer partially supported by projects MEC MTM2012-30951 and Gen. Cat. DGR 2009SGR1040, 2014SGR46 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: grant EUI- EURC-2011-4306. Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2011-28800-C02-02.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

New problems related to the valences of (super) edge-magic labelings

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
A graph G of order p and size q is edge-magic if there is a bijective function f : V (G) ∪ E(G) −→ {i} p+q i=1 such that f(x) + f(xy) + f(y) = k , for all xy ∈ E(G) . The function f is an edge-magic labeling of G and the sum k is called either the magic sum, the valence or the weight of f . Furthermore, if f(V (G)) = {i} p i=1 then f is a super edge-magic labeling of G . In this paper we study the valences that can be attained by (super) edge-magic labelings of some families of graphs., The first and the third author are supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

The Manhattan Product of Digraphs

  • Comellas Padró, Francesc
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
We study the main properties of a new product of bipartite digraphs which we call Manhattan product. This product allows us to understand the subjacent product in the Manhattan street networks and can be used to built other networks with similar good properties. It is shown that if all the factors of such a product are (directed) cycles, then the digraph obtained is a Manhattan street network, a widely studied topology for modeling some interconnection networks. To this respect, it is proved that many properties of these networks, such as high symmetries, reduced diameter and the presence of Hamiltonian cycles, are shared by the Manhattan product of some digraphs. Moreover, we show that the Manhattan product of two Manhattan streets networks is also a Manhattan street network. Finally, some sufficient conditions for the Manhattan product of two Cayley digraphs to be also a Cayley digraph are given. Throughout our study we use some interesting recent concepts, such as the unilateral distance and related graph invariants., This research was supported by the Ministry of Science and Innovation (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01-1 and by the Catalan Research Council under project 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

Labeling constructions using digraph products

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
In this paper we study the edge-magicness of graphs with equal size and order, and we use such graphs and digraph products in order to construct labelings of different classes and of different graphs. We also study super edge-magic labelings of 2-regular graphs with exactly two components and their implications to other labelings. The strength of the paper lays on the techniques used, since they are not only used in order to provide labelings of many different types of families of graphs, but they also show interesting relations among well studied types of labelings. We are able to obtain, in this way, deep results relating different types of labelings., The research conducted in this document by the first and third authors has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Repositori Obert UdL
Publicación Artículo científico (JournalArticle)

A problem on edge-magic labelings of cycles

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
Kotzig and Rosa defined in 1970 the concept of edge-magic labelings as follows: let G be a simple (p, q)-graph (that is, a graph of order p and size q without loops or multiple edges). A bijective function f : V (G)∪E(G) → {1, 2, . . . , p + q} is an edge-magic labeling of G if f(u) + f(uv) + f(v) = k, for all uv ∈ E(G). A graph that admits an edge-magic labeling is called an edgemagic graph, and k is called the magic sum of the labeling. An old conjecture of Godbold and Slater sets that all possible theoretical magic sums are attained for each cycle of order n ≥ 7. Motivated by this conjecture, we prove that for all n0 ∈ N, there exists n ∈ N, such that the cycle Cn admits at least n0 edge-magic labelings with at least n0 mutually distinct magic sums. We do this by providing a lower bound for the number of magic sums of the cycle Cn, depending on the sum of the exponents of the odd primes appearing in the prime factorization of n., The first and the third author are supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The spectral excess theorem for distance-regular graphs having distance-d graph with fewer distinct eigenvalues

  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
The final publication is available at Springer via http://dx.doi.org/10.1007/s10801-015-0654-6, Let Gamma be a distance-regular graph with diameter d and Kneser graph K = Gamma(d), the distance-d graph of Gamma. We say that Gamma is partially antipodal when K has fewer distinct eigenvalues than Gamma. In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with d + 1 distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Abelian Cayley digraphs with asymptotically large order for any given degree

  • Aguiló Gost, Francisco de Asis L.|||0000-0003-1572-8486
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Pérez Mansilla, Sonia|||0000-0001-9831-1066
Abelian Cayley digraphs can be constructed by using a generalization to Z(n) of the concept of congruence in Z. Here we use this approach to present a family of such digraphs, which, for every fixed value of the degree, have asymptotically large number of vertices as the diameter increases. Up to now, the best known large dense results were all non-constructive., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Symmetry breaking in tournaments

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S in V(T) is a determining set for a tournament T if every nontrivial automorphism of T moves at least one vertex of S, while S is a resolving set for T if every two distinct vertices in T have different distances to some vertex in S. We show that the minimum size of a determining set for an order n tournament (its determining number) is bounded by n/3, while the minimum size of a resolving set for an order n strong tournament (its metric dimension) is bounded by n/2. Both bounds are optimal., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the number of L-shapes in embedding dimension four numerical semigroups

  • Aguiló Gost, Francisco de Asis L.|||0000-0003-1572-8486
  • García Sánchez, Pedro A.
  • Llena, David
Minimum distance diagrams, also known as L-shapes, have been used to study some properties related to weighted Cayley digraphs of degree two and embedding dimension three numerical semigroups. In this particular case, it has been shown that these discrete structures have at most two related L-shapes. These diagrams are proved to be a good tool for studying factorizations and the catenary degree for semigroups and diameter and distance between vertices for digraphs.; This maximum number of L-shapes has not been proved to be kept when increasing the degree of digraphs or the embedding dimension of semigroups. In this work we give a family of embedding dimension four numerical semigroups S-n, for odd n >= 5, such that the number of related L-shapes is n+3/2. This family has her analogue to weighted Cayley digraphs of degree three.; Therefore, the number of L-shapes related to numerical semigroups can be as large as wanted when the embedding dimension is at least four. The same is true for weighted Cayley digraphs of degree at least three. This fact has several implications on the combinatorics of factorizations for numerical semigroups and minimum paths between vertices for weighted digraphs. (C) 2015 Elsevier B.V. All rights reserved., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Some spectral and quasi-spectral characterizations of distance-regular graphs

  • Abiad, Aida
  • Van Dam, Edwin R
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
© <2016>. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth. (C) 2016 Published by Elsevier Inc., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Online graph coloring with advice and randomized adversary

  • Muñoz López, Francisco Javier|||0000-0002-2560-3540
We generalize the model of online computation with three players (algorithm, adversary and an oracle called advisor) by strength- ening the power of the adversary by randomization. In our generalized model, the advisor knows everything about the adversary except the ran- dom bits the adversary may use. We examine the expected competitive ratio of online algorithms within this model in order to measure the hardness of online problems in a new way. We start our investigation by proving upper and lower bounds on the competitive ratio for the online graph coloring problem., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Quotient-polynomial graphs

  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
As a generalization of orbit-polynomial and distance-regular graphs, we introduce the concept of a quotient-polynomial graph. In these graphs every vertex uinduces the same regular partition around u, where all vertices of each cell are equidistant from u. Some properties and characterizations of such graphs are studied. For instance, all quotient-polynomial graphs are walk-regular and distance-polynomial. Also, we show that every quotient-polynomial graph generates a (symmetric) association scheme., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Quotient-polynomial graphs

  • Fiol Mora, Miquel Àngel
As a generalization of orbit-polynomial and distance-regular graphs, we introduce the concept of a quotient-polynomial graph. In these graphs every vertex uinduces the same regular partition around u, where all vertices of each cell are equidistant from u. Some properties and characterizations of such graphs are studied. For instance, all quotient-polynomial graphs are walk-regular and distance-polynomial. Also, we show that every quotient-polynomial graph generates a (symmetric) association scheme., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The jumping knight and other (super) edge-magic constructions

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
Let G be a graph of order p and size q with loops allowed. A bijective function f:V(G)∪E(G)→{i}p+qi=1 is an edge-magic labeling of G if the sum f(u)+f(uv)+f(v)=k is independent of the choice of the edge uv. The constant k is called either the valence, the magic weight or the magic sum of the labeling f. If a graph admits an edge-magic labeling, then it is called an edge-magic graph. Furthermore, if the function f meets the extra condition that f(V(G))={i}pi=1 then f is called a super edge-magic labeling and G is called a super edge-magic graph. A digraph D admits a labeling, namely l, if its underlying graph, und(D) admits l. In this paper, we introduce a new construction of super edge-magic labelings which are related to the classical jump of the knight on the chess game. We also use super edge-magic labelings of digraphs together with a generalization of the Kronecker product to get edge-magic labelings of some families of graphs., The research conducted in this document by the first and third authors has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A problem on edge-magic labelings of cycles

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
Kotzig and Rosa defined in 1970 the concept of edge-magic labelings as follows: let G be a simple (p, q)-graph (that is, a graph of order p and size q without loops or multiple edges). A bijective function f : V (G)∪E(G) → {1, 2, . . . , p + q} is an edge-magic labeling of G if f(u) + f(uv) + f(v) = k, for all uv ∈ E(G). A graph that admits an edge-magic labeling is called an edgemagic graph, and k is called the magic sum of the labeling. An old conjecture of Godbold and Slater sets that all possible theoretical magic sums are attained for each cycle of order n ≥ 7. Motivated by this conjecture, we prove that for all n0 ∈ N, there exists n ∈ N, such that the cycle Cn admits at least n0 edge-magic labelings with at least n0 mutually distinct magic sums. We do this by providing a lower bound for the number of magic sums of the cycle Cn, depending on the sum of the exponents of the odd primes appearing in the prime factorization of n., The first and the third author are supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The (∆,D) and (∆,N) problems in double-step digraphs with unilateral distance

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
We study the (Delta,D) and (Delta,N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by changing the directions of all the arcs. The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree $\Delta$ and the unilateral diameter D*, whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices. Moreover, we compute the mean unilateral distance of the digraphs in the families considered., This research was supported by the Ministry of Science and Innovation (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01-1 and by the Catalan Research Council under project 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The Manhattan Product of Digraphs

  • Comellas Padró, Francesc
  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
We study the main properties of a new product of bipartite digraphs which we call Manhattan product. This product allows us to understand the subjacent product in the Manhattan street networks and can be used to built other networks with similar good properties. It is shown that if all the factors of such a product are (directed) cycles, then the digraph obtained is a Manhattan street network, a widely studied topology for modeling some interconnection networks. To this respect, it is proved that many properties of these networks, such as high symmetries, reduced diameter and the presence of Hamiltonian cycles, are shared by the Manhattan product of some digraphs. Moreover, we show that the Manhattan product of two Manhattan streets networks is also a Manhattan street network. Finally, some sufficient conditions for the Manhattan product of two Cayley digraphs to be also a Cayley digraph are given. Throughout our study we use some interesting recent concepts, such as the unilateral distance and related graph invariants., This research was supported by the Ministry of Science and Innovation (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01-1 and by the Catalan Research Council under project 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The Diameter of Cyclic Kautz Digraphs

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
A prominent problem in Graph Theory is to find extremal graphs or digraphs with restrictions in their diameter, degree and number of vertices. Here we obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and degree there is no other digraph with a smaller diameter. This new family is called modified cyclic digraphs M CK(d, l) and it is derived from the Kautz digraphs K(d, l). It is well-known that the Kautz digraphs K(d, l) have the smallest diameter among all digraphs with their number of vertices and degree. Here we define the cyclic Kautz digraphs CK(d, l), whose vertices are labeled by all possible sequences a1 . . . al of length l, such that each character ai is chosen from an alphabet con taining d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1 l = al., K. Böhmová is a recipient of the Google Europe Fellowship in Optimization Algorithms, and this research is supported in part by this Google Fellowship. Research of C. Dalfó supported by projects MINECO MTM2011-28800-C02-01, and 2014SGR1147 from the Catalan Government. Research of C. Huemer supported by projects MINECO MTM2012-30951 and Gen. Cat. DGR 2014SGR46.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Labeling constructions using digraph products

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
In this paper we study the edge-magicness of graphs with equal size and order, and we use such graphs and digraph products in order to construct labelings of different classes and of different graphs. We also study super edge-magic labelings of 2-regular graphs with exactly two components and their implications to other labelings. The strength of the paper lays on the techniques used, since they are not only used in order to provide labelings of many different types of families of graphs, but they also show interesting relations among well studied types of labelings. We are able to obtain, in this way, deep results relating different types of labelings., The research conducted in this document by the first and third authors has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Online graph coloring with advice and randomized adversary

  • Muñoz López, Francisco Javier
We generalize the model of online computation with three players (algorithm, adversary and an oracle called advisor) by strength- ening the power of the adversary by randomization. In our generalized model, the advisor knows everything about the adversary except the ran- dom bits the adversary may use. We examine the expected competitive ratio of online algorithms within this model in order to measure the hardness of online problems in a new way. We start our investigation by proving upper and lower bounds on the competitive ratio for the online graph coloring problem., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the number of L-shapes in embedding dimension four numerical semigroups

  • Aguiló Gost, Francisco de Asis L.
  • García Sánchez, Pedro A.
  • Llena, David
Minimum distance diagrams, also known as L-shapes, have been used to study some properties related to weighted Cayley digraphs of degree two and embedding dimension three numerical semigroups. In this particular case, it has been shown that these discrete structures have at most two related L-shapes. These diagrams are proved to be a good tool for studying factorizations and the catenary degree for semigroups and diameter and distance between vertices for digraphs.; This maximum number of L-shapes has not been proved to be kept when increasing the degree of digraphs or the embedding dimension of semigroups. In this work we give a family of embedding dimension four numerical semigroups S-n, for odd n >= 5, such that the number of related L-shapes is n+3/2. This family has her analogue to weighted Cayley digraphs of degree three.; Therefore, the number of L-shapes related to numerical semigroups can be as large as wanted when the embedding dimension is at least four. The same is true for weighted Cayley digraphs of degree at least three. This fact has several implications on the combinatorics of factorizations for numerical semigroups and minimum paths between vertices for weighted digraphs. (C) 2015 Elsevier B.V. All rights reserved., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The degree/diameter problem in maximal planar bipartite graphs

  • Dalfó, Cristina
  • Huemer, Clemens
  • Salas Piñón, Julián
Research of C. Dalf ́o supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund under project MTM2011-28800-C02-01, and by the Catalan Research Council under project 2009SGR1387. Research of C. Huemer partially supported by projects MEC MTM2012-30951 and Gen. Cat. DGR 2009SGR1040, 2014SGR46 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: grant EUI- EURC-2011-4306. Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2011-28800-C02-02.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

New problems related to the valences of (super) edge-magic labelings

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
  • Rius Font, Miquel
A graph G of order p and size q is edge-magic if there is a bijective function f : V (G) ∪ E(G) −→ {i} p+q i=1 such that f(x) + f(xy) + f(y) = k , for all xy ∈ E(G) . The function f is an edge-magic labeling of G and the sum k is called either the magic sum, the valence or the weight of f . Furthermore, if f(V (G)) = {i} p i=1 then f is a super edge-magic labeling of G . In this paper we study the valences that can be attained by (super) edge-magic labelings of some families of graphs., The first and the third author are supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Symmetry breaking in tournaments

  • Lozano Boixadors, Antoni
We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S in V(T) is a determining set for a tournament T if every nontrivial automorphism of T moves at least one vertex of S, while S is a resolving set for T if every two distinct vertices in T have different distances to some vertex in S. We show that the minimum size of a determining set for an order n tournament (its determining number) is bounded by n/3, while the minimum size of a resolving set for an order n strong tournament (its metric dimension) is bounded by n/2. Both bounds are optimal., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Moments in graphs

Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The spectral excess theorem for distance-regular graphs having distance-d graph with fewer distinct eigenvalues

  • Fiol Mora, Miquel Àngel
The final publication is available at Springer via http://dx.doi.org/10.1007/s10801-015-0654-6, Let Gamma be a distance-regular graph with diameter d and Kneser graph K = Gamma(d), the distance-d graph of Gamma. We say that Gamma is partially antipodal when K has fewer distinct eigenvalues than Gamma. In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with d + 1 distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Connectivity and other invariants of generalized products of graphs

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
Figueroa-Centeno et al. [4] introduced the following product of digraphs let D be a digraph and let Γ be a family of digraphs such that V (F) = V for every F∈Γ . Consider any function h:E(D)→Γ . Then the product D⊗hΓ is the digraph with vertex set V(D)×V and ((a,x),(b,y))∈E(D⊗hΓ) if and only if (a,b)∈E(D) and (x,y)∈E(h(a,b)) . In this paper, we deal with the undirected version of the ⊗h -product, which is a generalization of the classical direct product of graphs and, motivated by the ⊗h -product, we also recover a generalization of the classical lexicographic product of graphs, namely the ∘h -product, that was introduced by Sabidussi in 1961. We provide two characterizations for the connectivity of G⊗hΓ that generalize the existing one for the direct product. For G∘hΓ , we provide exact formulas for the connectivity and the edge-connectivity, under the assumption that V (F) = V , for all F∈Γ . We also introduce some miscellaneous results about other invariants in terms of the factors of both, the ⊗h -product and the ∘h -product. Some of them are easily obtained from the corresponding product of two graphs, but many others generalize the existing ones for the direct and the lexicographic product, respectively. We end up the paper by presenting some structural properties. An interesting result in this direction is a characterization for the existence of a nontrivial decomposition of a given graph G in terms of ⊗h -product., The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Some spectral and quasi-spectral characterizations of distance-regular graphs

  • Abiad, Aida
  • Van Dam, Edwin R
  • Fiol Mora, Miquel Àngel
© <2016>. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth. (C) 2016 Published by Elsevier Inc., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Rainbow eulerian multidigraphs and the product of cycles

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of digraphs such that $V(F)=V$ for every $F\in \Gamma$. Consider any function $h:E(D)\longrightarrow\Gamma $. Then the product $D\otimes_{h} \Gamma$ is the digraph with vertex set $V(D)\times V$ and $((a,x),(b,y))\in E(D\otimes_{h}\Gamma)$ if and only if $ (a,b)\in E(D)$ and $ (x,y)\in E(h (a,b))$. In this paper we use rainbow eulerian multidigraphs and permutations as a way to characterize the $\otimes_h$-product of oriented cycles. We study the behavior of the $\otimes_h$-product when applied to digraphs with unicyclic components. The results obtained allow us to get edge-magic labelings of graphs formed by the union of unicyclic components and with different magic sums., Supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Abelian Cayley digraphs with asymptotically large order for any given degree

  • Aguiló Gost, Francisco de Asis L.
  • Fiol Mora, Miquel Àngel
  • Pérez Mansilla, Sonia
Abelian Cayley digraphs can be constructed by using a generalization to Z(n) of the concept of congruence in Z. Here we use this approach to present a family of such digraphs, which, for every fixed value of the degree, have asymptotically large number of vertices as the diameter increases. Up to now, the best known large dense results were all non-constructive., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Langford sequences and a product of digraphs

  • López Masip, Susana-Clara
  • Muntaner Batle, Francesc Antoni
Skolem and Langford sequences and their many generalizations have applications in numerous areas. The -product is a generalization of the direct product of digraphs. In this paper we use the -product and super edge-magic digraphs to construct an exponential number of Langford sequences with certain order and defect. We also apply this procedure to extended Skolem sequences., The research conducted in this document by the first author has been supported by the Spanish Research Council under project MTM2011-28800-C02-01 and symbolically by the Catalan Research Council under grant 2014SGR1147.