Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 251
Encontrada(s) 3 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

IEEE 802.11 graph models

  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
  • Marsa-Maestre, Ivan
  • Cruz-Piris, Luis
  • Orden, David
  • Tejedor-Romero, Marino
[EN] There are several recent research lines addressing Wi-Fi network planning and optimiza-tion, both in terms of channel assignment and access point deployment. The problem with these works is that evaluation is usually performed with specific and closed models regarding signal prop-agation, throughput computation, and utility definition. Also, many of the models in the literature make assumptions about the role of wireless stations, or the co-channel interference, which-while being valid in the context of a single research work-makes very difficult to compare different approaches, to re-use concepts from previous mechanisms to create new ones, or to generalize mechanisms to other scenarios. This makes the different research lines in Wi-Fi network planning and optimization progress in an isolated manner.This paper aims to address such a recurring problem by proposing a graph-based generic model for Wi-Fi utility computation in network planning scenarios, as well as providing a collection of scenario graphs which may be used to benchmark different planning and optimization approaches. Experiments are conducted to show the validity of the model and the significance of its features, along with its extensibility to other scenarios., This work has been partially funded by Projects PID2019-10 4855RB-I00/AEI/10.13039/501100011033 and PID2019-10412 9GB-I00/AEI/10.13039/501100011033, by Project SBPLY/19/180501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER, by Projects UCeNet (CM/JIN/2019-031) and WiDAI (CM/JIN/2021-004) of the Comunidad de Madrid and University of Alcala, and by H2020-MSCA-RISE project 734922 - CONNECT. The publication is also part of project TED2021-131387B-I00 funded by MCIN/AEI/10.13039/501100011033 and by the European Union "NextGenerationEU"/PRTR and of project PID2021-123168NB-I00 funded by MCIN/AEI/10.13039/50110001103 3/FEDER, UE.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Distributed Remote E-Voting System Based on Shamir&apos, s Secret Sharing Scheme

  • Tejedor-Romero, Marino
  • Orden, David
  • Marsa-Maestre, Ivan
  • Junquera-Sanchez, Javier
  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
[EN] A number of e-voting systems have been proposed in the last decades, attracting the interest of the research community. The challenge is far from being fully addressed, especially for remote systems. In this work, we propose DiverSEC, a distributed, remote e-voting system based on Shamir secret sharing, operations in Galois field and mixnets, which enables end-to-end vote verification. Parties participate as nodes in the network, protecting their interests and ensuring process integrity due to the conflicting interests. The threat model is very conservative, not letting even the most privileged actors to compromise votes privacy or integrity. Security in depth is implemented, overlapping different mechanisms to offer guarantees even in the most adverse operating conditions. The main contributions of the resulting system are our proposal for secret-sharing among the political parties, which guarantees that no party can compromise the integrity of the ballot without being detected and identified in real time, and the computational and architectural scalability of the proposal, which make it easy to implement., M.T.-R. is funded by a predoctoral grant from the University of Alcala. M.T.-R., I.M.-M. and J.M.G.-G. are partially funded by Project PID2019-104855RB-I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, by Project SBPLY/19/180501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER and by Project UCeNet (CM/JIN/2019-031) of the Comunidad de Madrid and University of Alcala. D.O. is partially supported by Project PID2019-104129GB-I00/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and by H2020-MSCA-RISE project 734922-CONNECT.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

On the Benefits of Channel Bonding in Dense, Decentralized Wi-Fi 4 Networks

  • Gimenez-Guzman, Jose Manuel|||0000-0002-1645-8476
  • Marsa-Maestre,Ivan
  • Orden, David
  • Fernandez, Susel
  • Tejedor-Romero, Marino
[EN] Channel bonding is a technique first defined in the IEEE 802.11n standard to increase the throughput in wireless networks by means of using wider channels. In IEEE 802.11n (nowadays also known as Wi-Fi 4), it is possible to use 40 MHz channels instead of the classical 20 MHz channels. Although using channel bonding can increase the throughput, the classic 802.11 setting only allows for two orthogonal channels in the 2.4 GHz frequency band, which is not enough for proper channel assignment in dense settings. For that reason, it is commonly accepted that channel bonding is not suitable for this frequency band. However, to the best of our knowledge, there is not any accurate study that deals with this issue thoroughly. In this work, we study in depth the effect of channel bonding in Wi-Fi 4 dense, decentralized networks operating in the 2.4 GHz frequency band. We confirm the negative effect of using channel bonding in the 2.4 GHz frequency band with 11 channels which are 20 MHz wide (as in North America), but we also show that when there are 13 or more channels at hand (as in many other parts of the world, including Europe and Japan), the use of channel bonding yields consistent throughput improvements. For that reason, we claim that the common assumption of not considering channel bonding in the 2.4 GHz band should be revised., Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, David Orden, and Susel Fernandez were partially funded by Project SBPLY/19/180 501/000171 of the Junta de Comunidades de Castilla-La Mancha and FEDER and by Project UCeNet (CM/JIN/2019-031) of the Comunidad de Madrid and University of Alcala. Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, and Susel Fernandez were also funded by Project PID2019-104855RB-I00/AEI/10.130 39/501 100 011 033 of the Spanish Ministry of Science and Innovation. David Orden was also partially supported by Project PID2019-104129GB-I00/AEI/10.130 39/501 100 011 033 of the Spanish Ministry of Science and Innovation and by H2020-MSCA-RISE Project 734922 - CONNECT. Marino Tejedor-Romero was funded by a predoctoral contract from University of Alcala.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Iterated line digraphs are asymptotically dense

  • Dalfó, Cristina
We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well-known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs., This research is supported by projects MINECO MTM2014-60127-P, and 2014SGR1147 of the Catalan Government. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Decompositions of a rectangle into non-congruent rectangles of equal area

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
  • Martínez Pérez, Álvaro
In this paper, we deal with a simple geometric problem: Is it possible to partition a rectangle into k non-congruent rectangles of equal area? This problem is motivated by the so-called 'Mondrian art problem' that asks a similar question for dissections with rectangles of integer sides. Here, we generalize the Mondrian problem by allowing rectangles of real sides. In this case, we show that the minimum value of k for a rectangle to have a 'perfect Mondrian partition' (that is, with non-congruent equal-area rectangles) is seven. Moreover, we prove that such a partition is unique (up to symmetries) and that there exist exactly two proper perfect Mondrian partitions for k=8. Finally, we also prove that any square has a perfect Mondrian decomposition for k >= 7., The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó, Cristina
  • Duque, F.
  • Fabila Monroy, R.
  • Fiol Mora, Miguel Ángel
  • Huemer, Clemens
  • Zaragoza Martínez, F.J.
  • Trujillo Negrete, A.L.
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

On the Randić index of graphs

  • Dalfó, Cristina
For a given graph G = (V, E), the degree mean rate of an edge uv ∈ E is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees d(u) and d(v). In this note, we derive tight bounds for the Randić index of G in terms of its maximum and minimum degree mean rates over its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randić index for graphs with order n large enough, when the minimum degree δ is greater than (approximately) ∆1/3 , where ∆ is the maximum degree. As a by-product, this proves that almost all random (Erdös-Rényi) graphs satisfy the conjecture., This research is partially supported by the project 017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Government of Catalonia. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

On d-Fibonacci digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
The d-Fibonacci digraphs F(d, k), introduced here, have the number of vertices following some generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(d, k) has diameter d + k − 2 and is semi-pancyclic; that is, it has a cycle of every length between 1 and ℓ, with ℓ ∈ {2k − 2, 2k − 1}. Moreover, it turns out that several other numbers of F(d, k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of vertices of the d-Fibonacci digraphs., The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A general method to obtain the spectrum and local spectra of a graph from its regular partitions

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C-local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The spectra of lifted digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Sirán, Jozef
We present a method to derive the complete spectrum of the lift Γα of a base digraph Γ , with voltage assignment α on a (finite) group G. The method is based on assigning to Γ a quotient-like matrix whose entries are elements of the group algebra C[G] , which fully represents Γα . This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalizes some previous results of Lovász and Babai concerning the spectra of Cayley digraphs., The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 734922. Research of the first two authors is supported by AGAUR under Project 2017SGR1087. The third author acknowledges support from the research Grants APVV 0136/12, APVV-15-0220, VEGA 1/0026/16, and VEGA 1/0142/17.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A survey on the missing Moore graph

  • Dalfó, Cristina
This is a survey on some known properties of the possible Moore graph (or graphs) ϒ with degree 57 and diameter 2. Moreover, we give some new results about it, such as the following. When we consider the distance partition of ϒ induced by a vertex subset C, the following graphs are distance-regular: The induced graph of the vertices at distance 1 from C when C is a set of 400 independent vertices; the induced graphs of the vertices at distance 2 from C when C is a vertex or an edge, and the line graph of ϒ. Besides, ϒ is an edge-distance-regular graph., This research is partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Government of Catalonia. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
It is known that many networks modeling real-life complex systems are small-word (large local clustering and small diameter) and scale-free (power law of the degree distribution), and very often they are also hierarchical. Although most of the models are based on stochastic methods, some deterministic constructions have been recently proposed, because this allows a better computation of their properties. Here a new deterministic family of hierarchical networks is presented, which generalizes most of the previous proposals, such as the so-called binomial tree. The obtained graphs can be seen as graphs on alphabets (where vertices are labeled with words of a given alphabet, and the edges are defined by a specific rule relating different words). This allows us the characterization of their main distance-related parameters, such as the radius and diameter. Moreover, as a by-product, an efficient shortest-path local algorithm is proposed., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
We describe, in a very explicit way, a method for determining the spec-tra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regularor not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. Research of the two first authors has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

An algebraic approach to lifts of digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
  • Sirán, Jozef
We present some applications of a new matrix approach for studying the properties of the lift of a voltage digraph, which has arcs weighted by the elements of a group. As a main result, when the involved group is Abelian, we completely determine the spectrum of . As some examples of our technique, we study some basic properties of the Alegre digraph, and completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and the Hoffman-Singleton graph, The research of the first two authors have been partially supported by the Agency for Management of University and Research Grants of Catalonia (AGAUR) under project 2017SGR1087. The fifth author acknowledges support from the research grants APVV 0136/12, APVV-15-0220, VEGA 1/0026/16, and VEGA 1/0142/17. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

From Subkautz Digraphs to Cyclic Kautz Digraphs

  • Dalfó, Cristina
Kautz digraphs K(d, l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d, l) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d, l), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, l) and CK(d, l). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, l) and CK(d, l) are maximally vertex-connected and super-edge-connected. Whereas K(d, `) are optimal with respect to the diameter, we show that sK(d, l) and CK(d, l) are optimal with respect to the mean distance, whose exact values are given for both families when l = 3. Finally, we provide a lower bound on the girth of CK(d, l and sK(d, l)., This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Graphs, friends and acquaintances

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
A graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Many of the first results concerning graphs made reference to relationships between groups of people. In this article, we comment on four results of this kind: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distance-regularity and coding theory), and Hall's Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks., This research has been partially supported by the Agency for Management of Universities and Research Grants of Catalonia (AGAUR) under the project 2017SGR1087. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
Given an integer ≥1, a (1, ≤ )-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most have distinct closed in-neighborhoods within C . In this paper, we prove that every line digraph of min- imum in-degree one does not admit a (1, ≤ )-identifying code for ≥3. Then we give a characterization so that a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree one admits a (1, ≤2)-identifying code. The identifying number of a digraph D , −→ γID (D ) , is the minimum size of all the identifying codes of D . We establish for digraphs without digons with both vertices of in-degree one that −→ γID (LD ) is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Then we show that −→ γID (LD ) attains the equality for a digraph having a 1- factor with minimum in-degree two and without digons with both vertices of in-degree two. We finish by giving an algorithm to construct identifying codes in oriented digraphs with minimum in-degree at least two and minimum out-degree at least one., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087 . The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agree- ment No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

New results for the Mondrian art problem

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
The Mondrian problem consists of dissecting a square of side length n ∈ N into non-congruent rectangles with natural length sides such that the difference d(n) between the largest and the smallest areas of the rectangles partitioning the square is minimum. In this paper, we compute some bounds on d(n) in terms of the number of rectangles of the square partition. These bounds provide us optimal partitions for some values of n ∈ N. We provide a sequence of square partitions such that d(n)/n2 tends to zero for n large enough. For the case of 'perfect' partitions, that is, with d(n) = 0, we show that, for any fixed powers s1, . . . , sm, a square with side length n = p s1 1 · · · p smm , can have a perfect Mondrian partition only if p1 satisfies a given lower bound. Moreover, if n(x) is the number of side lengths x (with n ≤ x) of squares not having a perfect partition, we prove that its 'density' n(x) x is asymptotic to (log(log(x))2 2 log x , which improves previous results., The research of C. Dalfó and N. López has been partially supported by grant MTM2017-86767-R (Spanish Ministerio de Ciencia e Innovación). The research of C. Dalfó and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by Spanish Ministerio de Ciencia e Innovación from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

New cyclic Kautz digraphs with optimal diameter

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
We obtain a new family of digraphs with minimal diameter, that is, given the number of vertices and out-degree, there is no other digraph with a smaller diameter. This new family of digraphs are called `modified cyclic digraphs' MCK(d,ℓ)MCK(d,ℓ), and it is derived from the Kautz digraphs K(d,ℓ)K(d,ℓ) and from the so-called cyclic Kautz digraphs CK(d,ℓ)CK(d,ℓ). The cyclic Kautz digraphs CK(d,ℓ)CK(d,ℓ) were defined as the digraphs whose vertices are labeled by all possible sequences a1…aℓa1…aℓ of length ℓℓ, such that each character aiai is chosen from an alphabet of d+1d+1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and also requiring that a1≠aℓa1≠aℓ. Their arcs are between vertices a1a2…aℓa1a2…aℓ and a2…aℓaℓ+1a2…aℓaℓ+1, with a1≠aℓa1≠aℓ and a2≠aℓ+1a2≠aℓ+1. Since CK(d,ℓ)CK(d,ℓ) do not have minimal diameter for their number of vertices, we construct the modified cyclic Kautz digraphs to obtain the same diameter as in the Kautz digraphs, and we also show that MCK(d,ℓ)MCK(d,ℓ) are dd-out-regular. Moreover, for t≥1t≥1, we compute the number of vertices of the iterated line digraphs Lt(CK(d,ℓ))Lt(CK(d,ℓ))., The research of C. Dalfo has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087, grant PGC2018-095471-BI00 funded by MCIN/AEI/10.13039/501100011033 and ERDF “A way of making Europe”, by the European Union, and grant PID2020-115442RB-I00 from MCIN/AEI/10.13039/501100011033. The research of C. Huemer was supported by PID2019-104129GB-I00/AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A new approach to gross error detection for GPS networks

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
We present a new matrix-based approach to detect and correct gross errors in GPS geodetic control networks. The study is carried out by introducing a new matrix, whose entries are powers of a (real or complex) variable, which fully represents the network., This research have been partially supported by the Catalan Research Council, AGAUR, under project 2017SGR1087. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The spectra of subKautz and cyclic Kautz digraphs

  • Dalfó, Cristina
Kautz digraphs K(d, `) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz CK(d, `) and the subKautz sK(d, 2) digraphs were recently introduced by B¨ohmov´a, Huemer and the author. In this paper we propose a new method to obtain the complete spectra of subKautz sK(d, 2) and cyclic Kautz CK(d, 3) digraphs, for all d ≥ 3, through the HoffmanMcAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity., This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

From expanded digraphs to lifts of voltage digraphs and line digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
In this note we present a general approach to construct large digraphs from small ones. These are called expanded digraphs, and, as particular cases, we show the close relationship between lifted digraphs of voltage digraphs and line digraphs, which are two known ways to obtain dense digraphs. In the same context, we show the equivalence between the vertex-splitting and partial line digraph techniques. Then, we give a sufficient condition for a lifted digraph of a base line digraph to be again a line digraph. Some of the results are illustrated with two well-known families of digraphs, namely, the De Bruijn and Kautz digraphs, where it is shown that both families can be seen as lifts of smaller De Bruijn digraphs with appropriate voltage assignments., Research of the first two authors is supported by MINECO under project MTM2014-60127-P, and by AGAUR under project 2014SGR1147. The first author has also received funding from the European Union’s Horizon 2020 rese
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Characterizing identifying codes from the spectrum of a graph or digraph

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
A (1, ≤ ℓ)-identifying code in digraph D is a dominating subset C of vertices of D, such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on ℓ for digraphs. The results obtained here can also be applied to graphs., This research is supported by the Catalan Research Council under project 2014SGR1147. The second and third authors have also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The spectral excess theorem for graphs with few eigenvalues whose distance- 2 or distance-1-or-2 graph is strongly regular

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Koolen, Jack
We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs Γ (among regular graphs with few distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex, where d+1 is the number of different eigenvalues of Γ. This can be seen as another version of the so-called spectral excess theorem, which characterizes in a similar way those regular graphs that are distance-regular., Research of C. Dalfó and M. A. Fiol is partially supported by Agència de Gestió d'Ajuts Universitaris i de Recerca (AGAUR) under project 2017SGR1087. Research of J. Koolen is partially supported by the National Natural Science Foundation of China under project No. 11471009, and the Chinese Academy of Sciences under its ‘100 talent’ programme. The research of C. Dalfó has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

On quotient digraphs and voltage digraphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Miller, Mirka
  • Ryan, Joe
We study the relationship between two key concepts in the theory of digraphs, those of quotient digraphs and voltage digraphs. These techniques contract or expand a given digraph in order to study its characteristics, or to obtain more involved structures. As an application, we relate the spectrum of a digraph Γ, called a voltage digraph or base, with the spectrum of its lifted digraph Γα . We prove that all the eigenvalues of Γ (including multiplicities) are, in addition, eigenvalues of Γα . This study is carried out by introducing several reduced matrix representations of Γ α . As an example of our techniques, we study some basic properties of the Alegre digraph and its base., Research of the first two authors is supported by MINECO under project MTM2014-60127-P, and by AGAUR under project 2014SGR1147. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

New Moore-Like Bounds and Some Optimal Families of Abelian Cayley Mixed Graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are Cayley graphs of abelian groups. Such groups can be constructed using a generalization to Zn of the concept of congruence in Z. Here we use this approach to present some families of mixed graphs, which, for every fixed value of the degree, have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal., The research of C. Dalfó has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant agreement no. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

An improved upper bound for the order of mixed graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • López Lorenzo, Ignacio
A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a complete enumeration of all optimal (1; 1)-regular mixed graphs with diameter three is presented, so proving that, in general, the proposed bound cannot be improved., The research of C. Dalfó has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Sufficient conditions for a digraph to admit a (1,≤ℓ)-identifying code

  • Balbuena Martínez, Camino
  • Dalfó, Cristina
  • Martínez Barona, Berenice
A (1, ≤ `)-identifying code in a digraph D is a subset C of vertices of D such that all distinct subsets of vertices of cardinality at most ` have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree δ − ≥ 1 to admit a (1, ≤ `)- identifying code for ` ∈ {δ −, δ− + 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree δ ≥ 2 and girth at least 7 admits a (1, ≤ δ)-identifying code. Moreover, we prove 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 characterize all the 2-in-regular digraphs admitting a (1, ≤ `)-identifying code for ` ∈ {2, 3}., This research has been partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Generalitat de Catalunya. The last two authors have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

The diameter of cyclic Kautz digraphs

  • Böhmová, Katerina
  • Dalfó, Cristina
  • Huemer, Clemens
We present a new kind of digraphs, called cyclic Kautz digraphs CK(d, ɭ), which are subdigraphs of the well-known Kautz digraphs K(d,ɭ). The latter have the smallest diameter among all digraphs with their number of vertices and degree. Cyclic Kautz digraphs CK(d, ɭ) have vertices labeled by all possible sequences a1 . . . aɭ of length ɭ, such that each character ai is chosen from an alphabet containing d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1 ≠ aɭ. Their arcs are between vertices a1a2 . . . aɭ and a2 . . . aɭ aɭ + 1, with a1 ≠ aɭ and a2 ≠ aɭ + 1. We give the diameter of CK(d, ɭ) for all the values of d and ɭ, and also its number of vertices and arcs., Research of C. Dalfo is supported by projects MINECO MTM2014-60127-P, and AGAUR 2014SGR1147. Research of C. Huemer is supported by projects MINECO MTM2015-63791-R, and AGAUR 2014SGR46. C. Dalfo and C. Huemer have also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

A new general family of mixed graphs

  • Dalfó, Cristina
A new general family of mixed graphs is presented, which generalizes both the pancake graphs and the cycle prefix digraphs. The obtained graphs are vertex transitive and, for some values of the parameters, they constitute the best infinite families with asymptotically optimal (or quasi-optimal) number of vertices for their diameter., This research has been partially supported by AGAUR under project 2017SGR1087. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíková, Sona
  • Sirán, Jozef
The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U=c1A+c2D+c3I+c4J, with ci∈R and c1≠0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of the two first authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The third and fourth authors acknowledge support from the APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
  • Pavlíiková, Sona
  • Sirán, Jozef
We describe, in a very explicit way, a method for determining the spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not)., he first author has received funding from the European Union’s Horizon 2020 research and innovationprogramme under the Marie Skłodowska-Curie Grant Agreement No. 734922.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó, Cristina
  • Fiol Mora, Miguel Ángel
In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs P(n) and to a recent known family of mixed graphs Γ(d, n, r) (having edges with and without direction). As a byproduct, the existence of perfect codes s in P(n) allows us to give a lower bound for the multiplicity of its eigenvalue −1., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Matching points with disks with a common intersection

  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We consider matchings with diametral disks between two sets of points R and B. More precisely, for each pair of matched points p ¿ R and q ¿ B, we consider the disk through p and q with the smallest diameter. We prove that for any R and B such that |R| = |B|, there exists a perfect matching such that the diametral disks of the matched point pairs have a common intersection. In fact, our result is stronger, and shows that a maximum weight perfect matching has this property.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On the Laplacian spectra of token graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Huemer, Clemens|||0000-0001-7557-0823
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
© 2021 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4, We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that , the Laplacian spectrum of is contained in the Laplacian spectrum of . We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph and the star , respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement . This generalizes to tokens graphs a well-known property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of . Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph., This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Award-winning
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On maximum-sum matchings of points

  • Bereg, Sergey
  • Chacón Rivera, Oscar
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B with |R|=|B| , the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. Each pair of matched points p¿R and q¿B induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point., We thank the GeoGebra open source software and its developers [17]. S. B. was supported in part by NSF award CCF-1718994. D. F-P. was partially supported by PAPIIT IN120520 (UNAM, Mexico). C. H. and C. S. were partially supported by project MICINN 2020-2024 PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. P. P-L. was partially supported by projects DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

An algebraic approach to lifts of digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Miller, Mirka
  • Ryan, Joe
  • Siran, Josef
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study the relationship between two key concepts in the theory of (di)graphs: the quotient digraph, and the lift Ga of a base (voltage) digraph. These techniques contract or expand a given digraph in order to study its characteristics, or obtain more involved structures. This study is carried out by introducing a quotient-like matrix, with complex polynomial entries, which fully represents Ga. In particular, such a matrix gives the quotient matrix of a regular partition of Ga, and when the involved group is Abelian, it completely determines the spectrum of Ga. As some examples of our techniques, we study some basic properties of the Alegre digraph. In addition we completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and that of the Hoffman-Singleton graph, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations

  • Alegría Galicia, Carlos
  • Orden Martin, David
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
This is a post-peer-review, pre-copyedit version of an article published in Journal of Global Optimization. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10898-020-00953-5, Let P be a set of n points in the plane. We compute the value of ¿¿[0,2p) for which the rectilinear convex hull of P, denoted by RHP(¿), has minimum (or maximum) area in optimal O(nlogn) time and O(n) space, improving the previous O(n2) bound. Let O be a set of k lines through the origin sorted by slope and let ai be the sizes of the 2k angles defined by pairs of two consecutive lines, i=1,…,2k. Let Ti=p-ai and T=min{Ti:i=1,…,2k}. We obtain: (1) Given a set O such that T=p2, we provide an algorithm to compute the O-convex hull of P in optimal O(nlogn) time and O(n) space; If T<p2, the time and space complexities are O(nTlogn) and O(nT) respectively. (2) Given a set O such that T=p2, we compute and maintain the boundary of the O¿-convex hull of P for ¿¿[0,2p) in O(knlogn) time and O(kn) space, or if T<p2, in O(knTlogn) time and O(knT) space. (3) Finally, given a set O such that T=p2, we compute, in O(knlogn) time and O(kn) space, the angle ¿¿[0,2p) such that the O¿-convex hull of P has minimum (or maximum) area over all ¿¿[0,2p)., Carlos Alegría: Research supported in part by UNAM Project PAEP, and by MIUR Proj. “AHeAD” No. 20174LF3T8. David Orden: Research supported by Projects MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE), and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACYT 80268, PAPPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica UNAM. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñazola, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Let S ¿ [0, 1]2 be a set of n points, randomly and uniformly selected. Let R ¿ B be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random number M(n) of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n) = 0.83 n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A new lower bound on the maximum number of plane graphs using production matrices

  • Huemer, Clemens|||0000-0001-7557-0823
  • Pilz, Alexander
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We use the concept of production matrices to show that there exist sets of n points in the plane that admit ¿(42.11n ) crossing-free geometric graphs. This improves the previously best known bound of ¿(41.18n ) by Aichholzer et al. (2007).
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The intersection graph of the disks with diameters the sides of a convex n-gon

  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Given a convex polygon of sides, one can draw disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the disks and two disks are adjacent if and only if they have a point in common. We introduce the study of this graph by proving that it is planar for every convex polygon.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The spectra of lifted digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Siran, Josef
This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-018-0862-y, We present a method to derive the complete spectrum of the lift Ga of a base digraph G, with voltage assignment a on a (finite) group G. The method is based on assigning to G a quotient-like matrix whose entries are elements of the group algebra C[G], which fully represents Ga. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalizes some previous results of Lov´asz and Babai concerning the spectra of Cayley digraphs, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A new approach to gross error detection for GPS networks

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
We present a new matrix-based approach to detect and correct gross errors in GPS geodetic control networks. The study is carried out by introducing a new matrix, whose entries are powers of a (real or complex) variable, which fully represents the network., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Carathodory's theorem in depth

  • Fabila Monroy, Ruy
  • Huemer, Clemens|||0000-0001-7557-0823
Let X be a finite set of points in RdRd . The Tukey depth of a point q with respect to X is the minimum number tX(q)tX(q) of points of X in a halfspace containing q. In this paper we prove a depth version of Carathéodory’s theorem. In particular, we prove that there exist a constant c (that depends only on d and tX(q)tX(q) ) and pairwise disjoint sets X1,…,Xd+1¿XX1,…,Xd+1¿X such that the following holds. Each XiXi has at least c|X| points, and for every choice of points xixi in XiXi , q is a convex combination of x1,…,xd+1x1,…,xd+1 . We also prove depth versions of Helly’s and Kirchberger’s theorems.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • López Lorenzo, Nacho
  • Ryan, Joe
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We consider the case in which mixed graphs (with both directed and undirected edges) are Cayley graphs of Abelian groups. In this case, some Moore bounds were derived for the maximum number of vertices that such graphs can attain. We first show these bounds can be improved if we know more details about the order of some elements of the generating set. Based on these improvements, we present some new families of mixed graphs. For every fixed value of the degree, these families have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal., The first two authors have been partially supported by the project 2017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Catalan Government, and by MICINN from the Spanish Government under project PGC2018- 095471-B-I00. The first and the third authors have been supported in part by grant MTM2017-86767-R of the Spanish Government., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Capturing points with a rotating polygon (and a 3D extension)

  • Alegría Galicia, Carlos
  • Orden, David
  • Palios, Leonidas
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
This is a post-peer-review, pre-copyedit version of an article published in Theory of computing systems: an international journal. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00224-018-9885-y, We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a segment or a line. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s,t) , which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s,t) , which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path SGPw(s,t) , which is a shortest path whose edges are edges of the tessellation. The ratios ¿SGPw(s,t)¿¿SPw(s,t)¿ , ¿SVPw(s,t)¿¿SPw(s,t)¿ , ¿SGPw(s,t)¿¿SVPw(s,t)¿ provide estimates on the quality of the approximation. Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that ¿SGPw(s,t)¿¿SPw(s,t)¿=23v˜1.15 in the worst case, and this is tight., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Resolving sets tolerant to failures in three-dimensional grids

  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Souto Salorio, María josé
  • Tarrío Tobar, Ana Dorotea
The version of record is available online at: http://dx.doi.org/10.1007/s00009-022-02096-1, An ordered set S of vertices of a graph G is a resolving set for G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set. In this paper we study resolving sets tolerant to several failures in three-dimensional grids. Concretely, we seek for minimum cardinality sets that are resolving after removing any k vertices from the set. This is equivalent to finding (k+1)-resolving sets, a generalization of resolving sets, where, for every pair of vertices, the vector of distances to the vertices of the set differs in at least k + 1 coordinates. This problem is also related with the study of the (k+1)-metric dimension of a graph, defined as the minimum cardinality of a (k + 1)-resolving set. In this work, we first prove that the metric dimension of a three-dimensional grid is 3 and establish some properties involving resolving sets in these graphs. Secondly, we determine the values of k = 1 for which there exists a (k + 1)-resolving set and construct such a resolving set of minimum cardinality in almost all cases., This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

New Moore-like bounds and some optimal families of abelian Cayley mixed graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • López Lorenzo, Nacho
The final publication is available at Springer via http://dx.doi.org/10.1007/s00026-020-00496-2, Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are Cayley graphs of Abelian groups. Such groups can be constructed by using a generalization to Z n of the concept of congruence in Z. Here we use this approach to present some families of mixed graphs, which, for every fixed value of the degree, have an asymptotically large number of vertices as the diameter increases. In some cases, the results obtained are shown to be optimal., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A note on a new general family of deterministic hierarchical networks

UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path , which is a shortest path from s to t in the space; a weighted shortest vertex path , which is an any-angle shortest path; and a weighted shortest grid path , which is a shortest path whose edges are edges of the tessellation. Given any arbitrary weight assignment to the faces of a triangular tessellation, thus extending recent results by Bailey et al. (2021) [6], we prove upper and lower bounds on the ratios , , , which provide estimates on the quality of the approximation. It turns out, surprisingly, that our worst-case bounds are independent of any weight assignment. Our main result is that in the worst case, and this is tight. As a corollary, for the weighted any-angle path we obtain the approximation result ., P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is also funded by an FPU of the Universidad de Alcalá., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Pavlíková, Sona
  • Siran, Josef
We describe, in a very explicit way, a method for determining the spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Colored Ray configurations

  • Fabila Monroy, Ruy
  • Garcia Olaverri, Alfredo Martin
  • Hurtado Díaz, Fernando Alfredo|||0000-0002-0108-9671
  • Jaume, Rafel
  • Pérez Lantero, Pablo
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Tejel Altarriba, Francisco Javier
  • Urrutia Galicia, Jorge
We study the cyclic sequences induced at in nity by pairwise-disjoint colored rays with apices on a given bal- anced bichromatic point set, where the color of a ray is inherited from the color of its apex. We derive a lower bound on the number of color sequences that can be realized from any xed point set. We also examine se- quences that can be realized regardless of the point set and exhibit negative examples as well. In addition, we provide algorithms to decide whether a sequence is re- alizable from a given point set on a line or in convex position, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Affine invariant triangulations

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set S for any (unknown) affine transformation of S. Our work is based on a method by Nielson [A characterization of an affine invariant triangulation. Geom. mod, 191-210. Springer, 1993] that uses the inverse of the covariance matrix of S to define an affine invariant norm, denoted AS, and an affine invariant triangulation, denoted DT AS [S]. We revisit the AS-norm from a geometric perspective, and show that DT AS [S] can be seen as a standard Delaunay triangulation of a transformed point set based on S. We prove that it retains all of its well-known properties. In addition, we provide different affine invariant order methods of a point set S and of the vertices of a polygon P that can be combined with well-known algorithms in order to obtain other affine invariant triangulation methods of S and P., ∗P.B. was partially supported by NSERC. P.C. was supported by CONACyT. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Dominating 2-broadcast in graphs: complexity, bounds and extremal graphs

  • Cáceres, José
  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
  • Puertas González, María Luz
Limited dominating broadcasts were proposed as a variant of dominating broadcasts, where the broadcast function is upper bounded. As a natural extension of domination, we consider dominating 2-broadcasts along with the associated parameter, the dominating 2-broadcast number. We prove that computing the dominating 2-broadcast number is a NP-complete problem, but can be achieved in linear time for trees. We also give an upper bound for this parameter, that is tight for graphs as large as desired., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14]., A. Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR); M. Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT; and C. Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Convex quadrangulations of bichromatic point sets

  • Pilz, Alexander
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Electronic version of an article published as International journal of computational geometry and applications, 5 May 2020, vol. 29, núm. 4, p. 289-299. Article DOI 10.1142/S0218195919500109 © 2020 copyright World Scientific Publishing Company. Journal URL: https://www.worldscientific.com/doi/abs/10.1142/S0218195919500109, We consider quadrangulations of red and blue points in the plane where each face is convex and no edge connects two points of the same color. In particular, we show that the following problem is NP-hard: Given a finite set S of points with each point either red or blue, does there exist a convex quadrangulation of S in such a way that the predefined colors give a valid vertex 2-coloring of the quadrangulation? We consider this as a step towards solving the corresponding long-standing open problem on monochromatic point sets., This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Optimizing generalized kernels of polygons

  • Martínez Moraian, Alejandra
  • Orden Martin, David
  • Palios, Leonidas
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Zylinski, Pawel
This is a post-peer-review, pre-copyedit version of an article published in Journal of Global Optimization. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10898-021-01020-3, Let O be a set of k orientations in the plane, and let P be a simple polygon in the plane. Given two points p, q inside P, we say that p O-sees q if there is an O-staircase contained in P that connects p and q. The O-Kernel of the polygon P, denoted by O-Kernel(P), is the subset of points of P which O-see all the other points in P. This work initiates the study of the computation and maintenance of O-Kernel(P) as we rotate the set O by an angle ¿, denoted by O-Kernel¿(P). In particular, we consider the case when the set O is formed by either one or two orthogonal orientations, O={0°} or O={0°,90°}. For these cases and P being a simple polygon, we design efficient algorithms for computing the O-Kernel¿(P) while ¿ varies in [-p2,p2), obtaining: (i) the intervals of angle ¿ where O-Kernel¿(P) is not empty, (ii) a value of angle ¿ where O-Kernel¿(P) optimizes area or perimeter. Further, we show how the algorithms can be improved when P is a simple orthogonal polygon. In addition, our results are extended to the case of a set O={a1,…,ak}., This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Trees whose even-degree vertices induce a path are antimagic

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tey Carrera, Joaquín
An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however, the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Discrete Math. 331 (2014) 9–14].
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Hamiltonicity for convex shape Delaunay and Gabriel graphs

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape \(\mathcal {C}\) . Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- \({DG}_{\mathcal {C}}(S)\) , has vertex set S and edge pq provided that there exists some homothet of \(\mathcal {C}\) with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k- \({GG}_{\mathcal {C}}(S)\) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of \(\mathcal {C}\) with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- \({GG}_{\mathcal {C}}(S)\) is Hamiltonian. Since k- \({GG}_{\mathcal {C}}(S)\) \(\subseteq \) k- \({DG}_{\mathcal {C}}(S)\) , all results carry over to k- \({DG}_{\mathcal {C}}(S)\) . In particular, we give upper bounds of 24 for every \(\mathcal {C}\) and 15 for every point-symmetric \(\mathcal {C}\) . We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for \(t \ge 10)\) . These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs., P.B. was partially supported by NSERC. P.C. was supported by CONACyT. M.S. was supported by the Czech Science Foundation, grant number GJ19-06792Y, and by institutional support RVO:67985807. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

From subkautz digraphs to cyclic kautz digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
Kautz digraphs K(d,l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d,l) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d,l), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d,l) and CK(d,l). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d,l) and CK(d,l) are maximally vertex-connected and super-edge-connected. Whereas K(d,l) are optimal with respect to the diameter, we show that sK(d,l) and CK(d,l) are optimal with respect to the mean distance, whose exact values are given for both families when l = 3. Finally, we provide a lower bound on the girth of CK(d,l) and sK(d,l), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Metric dimension of maximal outerplanar graphs

  • Claverol Aguas, Mercè|||0000-0002-9138-8594
  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Maureso Sánchez, Montserrat|||0000-0001-6429-2776
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Hernández Peñalver, Gregorio
  • Garcia Olaverri, Alfredo Martin
  • Tejel, Javier
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On the Oß-hull of a planar point set

  • Alegría Galicia, Carlos
  • Orden, David
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study the Oß-hull of a planar point set, a generalization of the Orthogonal Convex Hull where the coordinate axes form an angle ß. Given a set P of n points in the plane, we show how to maintain the Oß-hull of P while ß runs from 0 to p in T(n log n) time and O(n) space. With the same complexity, we also find the values of ß that maximize the area and the perimeter of the Oß-hull and, furthermore, we find the value of ß achieving the best fitting of the point set P with a two-joint chain of alternate interior angle ß., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

K-1,K-3-covering red and blue points in the plane

  • Ábrego, Bernardo M.
  • Fernández Merchant, Silvia
  • Kano, Mikio
  • Orden, David
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Tejel Altarriba, Francisco Javier
We say that a finite set of red and blue points in the plane in general position can be K1,3-covered if the set can be partitioned into subsets of size 4, with 3 points of one color and 1 point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set R of r red points and a set B of b blue points in the plane in general position, how many points of R ¿ B can be K1,3-covered? and we prove the following results: (1) If r = 3g + h and b = 3h + g, for some non-negative integers g and h, then there are point sets R ¿ B, like {1, 3}-equitable sets (i.e., r = 3b or b = 3r) and linearly separable sets, that can be K1,3-covered. (2) If r = 3g + h, b = 3h + g and the points in R ¿ B are in convex position, then at least r + b - 4 points can be K1,3-covered, and this bound is tight. (3) There are arbitrarily large point sets R ¿ B in general position, with r = b + 1, such that at most r + b - 5 points can be K1,3-covered. (4) If b = r = 3b, then at least 8 9 (r + b - 8) points of R ¿ B can be K1,3-covered. For r > 3b, there are too many red points and at least r - 3b of them will remain uncovered in any K1,3-covering., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Iterated line digraphs are asymptotically dense

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
© 2017. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well- known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On quotient digraphs and voltage digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Miller, Mirka
  • Ryan, Joe
We study the relationship between two key concepts in the theory of digraphs, those of quotient digraphs and voltage digraphs. These techniques contract or expand a given digraph in order to study its characteristics,or to obtain more involved structures. As an application, we relate the spectrum of a digraph Γ, called a voltage digraph or base, with the spectrum of its lifted digraph Γα. We prove that all the eigenvalues of Γ (including multiplicities) are, in addition, eigenvalues of Γα. This study is carried out by introducing several reduced matrix representations of Γα. As an example of our techniques, we study some basic properties of the Alegre digraph and its base.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Pole Dancing: 3D Morphs for Tree Drawings

  • Arseneva, Elena
  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • D'Angelo, Anthony
  • Dujmovic, Vida
  • Frati, Fabrizio
  • Langerman, Stefan
  • Tappini, Alessandra
We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter T(n) steps are always sufficient and sometimes necessary.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Sufficient conditions for a digraph to admit a (1,=l)-identifying code

  • Balbuena Martínez, Maria Camino Teófila|||0000-0003-4190-4287
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Martínez Barona, Berenice|||0000-0003-4336-6881
A (1, = `)-identifying code in a digraph D is a subset C of vertices of D such that all distinct subsets of vertices of cardinality at most ` have distinct closed in-neighbourhoods within C. In this paper, we give some sufficient conditions for a digraph of minimum in-degree d - = 1 to admit a (1, = `)- identifying code for ` ¿ {d -, d- + 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree d = 2 and girth at least 7 admits a (1, = d)-identifying code. Moreover, we prove 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 characterize all the 2-in-regular digraphs admitting a (1, = `)-identifying code for ` ¿ {2, 3}., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The spectral excess theorem for graphs with few eigenvalues whose distance-2 or distance-1-or-2 graph is strongly regular

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Koolen, Jack
This is an Accepted Manuscript of an article published by Taylor & Francis Group in Linear and multilinear algebra on july 2018, available online at: http://www.tandfonline.com/10.1080/03081087.2018.1491944., We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs G (among regular graphs with few distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex, where d+ 1 is the number of different eigenvalues of G. This can be seen as another version of the so-called spectral excess theorem, which characterizes in a similar way those regular graphs that are distance-regular.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Metric-locating-dominating sets of graphs for constructing related subsets of vertices

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • González Herrera, Antonio
© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, A dominating set S of a graph is a metric-locating-dominating set if each vertex of the graph is uniquely distinguished by its distances from the elements of S , and the minimum cardinality of such a set is called the metric-location-domination number. In this paper, we undertake a study that, in general graphs and specific families, relates metric-locating-dominating sets to other special sets: resolving sets, dominating sets, locating-dominating sets and doubly resolving sets. We first characterize the extremal trees of the bounds that naturally involve metric-location-domination number, metric dimension and domination number. Then, we prove that there is no polynomial upper bound on the location-domination number in terms of the metric-location-domination number, thus extending a result of Henning and Oellermann. Finally, we show different methods to transform metric-locating-dominating sets into locating-dominating sets and doubly resolving sets. Our methods produce new bounds on the minimum cardinalities of all those sets, some of them concerning parameters that have not been related so far, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Graphs, friends and acquaintances

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
Published in: Electronic journal of graph theory and applications (http://www.ejgta.org), A graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Many of the first results concerning graphs made reference to relationships between groups of people. In this article, we comment on four results of this kind: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distance-regularity and coding theory), and Hall’s Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks.
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

Neighbor-locating colorings in graphs

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
  • Alcón, Liliana
  • Gutierrez, Marisa
A k -coloring of a graph G is a k -partition ¿ = { S 1 ,...,S k } of V ( G ) into independent sets, called colors . A k -coloring is called neighbor-locating if for every pair of vertices u,v belonging to the same color S i , the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v . The neighbor-locating chromatic number ¿ NL ( G ) is the minimum cardinality of a neighbor-locating coloring of G . We establish some tight bounds for the neighbor-locating chromatic number of a graph, in terms of its order, maximum degree and independence number. We determine all connected graphs of order n = 5 with neighbor-locating chromatic number n or n - 1. We examine the neighbor-locating chromatic number for two graph operations: join and disjoint union, and also for two graph families: split graphs and Mycielski graphs
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On maximum-sum matchings of points

  • Bereg, Sergey
  • Chacón Rivera, Oscar
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
Huemer et al. (Discrete Math., 2019) proved that for any two point sets R and B with |R| = |B|, the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. In this work we study the perfect matching that maximizes the total Euclidean distance. First, we prove that this setting does not always ensure the common intersection property of the disks. Second, we extend the study for sets of 2n uncolored points. As the main result, we prove that in this case all disks of the matching do have a common point.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Hamiltonicity for convex shape Delaunay and Gabriel Graphs

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DGC(S), has vertex set S, and edges defined as follows. Given p, q ¿ S, pq is an edge of k-DGC(S) provided there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph, denoted k-GGC(S), is defined analogously, except that the homothets considered are restricted to be smallest homothets of C with p and q on the boundary. We provide upper bounds on the minimum value of k for which k-GGC(S) is Hamiltonian. Since k-GGC(S) ¿ k-DGC(S), all results carry over to k-DGC(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve these bounds to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t = 10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. In addition, we show lower bounds of k = 3 and k = 6 on the existence of a bottleneck Hamiltonian cycle in the k-order Gabriel graph for squares and hexagons, respectively. Finally, we construct a point set such that for an infinite family of regular polygons Pt, the Delaunay graph DGPt does not contain a Hamiltonian cycle., ∗P.B. was partially supported by NSERC. P.C. was supported by CONACyT. M.S. was supported by the Czech Science Foundation, grant number GJ19-06792Y, and by institutional support RVO:67985807. R.S. was supported by MINECO through the Ram´on y Cajal program. P.C. and R.S. were also supported by projects MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On d-Fibonacci digraphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
The d-Fibonacci digraphs F(d, k), introduced here, have the number of vertices following some generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(d, k) has diameter d + k - 2 and is semi-pancyclic; that is, it has a cycle of every length between 1 and l, with l ¿ {2k - 2, 2k - 1}. Moreover, it turns out that several other numbers of F(d, k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of vertices of the d-Fibonacci digraphs., This research has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Decompositions of a rectangle into non-congruent rectangles of equal area

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • López Lorenzo, Nacho
  • Martínez Pérez, Álvaro
© 2021 Elsevier. 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 deal with a simple geometric problem: Is it possible to partition a rectangle into k non-congruent rectangles of equal area? This problem is motivated by the so-called ‘Mondrian art problem’ that asks a similar question for dissections with rectangles of integer sides. Here, we generalize the Mondrian problem by allowing rectangles of real sides. In this case, we show that the minimum value of k for a rectangle to have a ‘perfect Mondrian partition’ (that is, with non-congruent equalarea rectangles) is seven. Moreover, we prove that such a partition is unique (up to symmetries) and that there exist exactly two proper perfect Mondrian partitions for k = 8. Finally, we also prove that any square has a perfect Mondrian decomposition for k = 7., The research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On bipartite-mixed graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • López Lorenzo, Nacho
This is the peer reviewed version of the following article: Dalfo, C., Fiol, M., López, N. On bipartite-mixed graphs. "Journal of graph theory", 24 Abril 2018, p. 1-9, which has been published in final form at https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.22257. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving., Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite. As main results, we show that in this context the Moore-like bound is attained in the case of diameter k = 3, and that bipartite mixed graphs of diameter k ≥ 4 do not exist.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Matching random colored points with rectangles

  • Corujo, Josué
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Pérez Lantero, Pablo
Let S[0,1]2 be a set of n points, randomly and uniformly selected. Let RB be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n)=0.83n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain., Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Sequences of spanning trees for L-infinity Delaunay triangulations

  • Bose, Prosenjit
  • Cano Vila, María del Pilar|||0000-0002-4318-5282
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We extend a known result about L2-Delaunay triangulations to L∞-Delaunay. Let TS be the set of all non-crossing spanning trees of a planar n-point set S. We prove that for each element T of TS, there exists a length-decreasing sequence of trees T0, . . . , Tk in the L∞-metric such that T0 = T, Tk = MST(S) and Ti does not cross Ti−1 for all i = 1, . . . , k, where MST(S) denotes the minimum spanning tree of S in the L∞ metric. We also give an Ω(log n) lower bound for the length of the sequence, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Identifying codes in line digraphs

  • Balbuena Martínez, Maria Camino Teófila|||0000-0003-4190-4287
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Martínez Barona, Berenice|||0000-0003-4336-6881
© 2020 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, Given an integer ` = 1, a (1, = `)-identifying code in a digraph is a dominating subset C of vertices such that all distinct subsets of vertices of cardinality at most ` have distinct closed in-neighbourhood within C. In this paper, we prove that every k-iterated line digraph of minimum in-degree at least 2 and k = 2, or minimum indegree at least 3 and k = 1, admits a (1, = `)-identifying code with ` = 2, and in any case it does not admit a (1, = `)-identifying code for ` = 3. Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in-degree at least 2., This research is supported by MICINN from the Spanish Government under project PGC2018-095471-B-I00 and partially by AGAUR from the Catalan Government under project 2017SGR1087. The research of the second author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. B. Martínez-Barona has received funding from the scholarship 254379/438356 from CONACYT from Mexico. The second and third authors have received funding research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The voronoi diagram of rotating rays with applications to floodlight illumination

  • Alegria, Carlos
  • Mantas, Ioannis
  • Papadopoulou, Evanthia|||0000-0003-0144-7384
  • Savic, Marko
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Suderland, Martin|||0000-0002-6604-6381
34 p. This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/[10.1007/s00453-025-01368-y], We study the Voronoi Diagram of Rotating Rays, a Voronoi structure where the input sites are rays and the distance function between a point and a site/ray is their counterclockwise angular distance. This novel Voronoi diagram is motivated by illumination and coverage problems, where a domain must be covered by floodlights, which are wedges of uniform angle, and the goal is to find the minimum angle necessary to cover the domain. This angle is called the Brocard angle and it is encoded in the Voronoi diagram of rotating rays. We study the diagram in the plane and present its structural properties, its combinatorial complexity bounds, and a construction algorithm. If the rays are induced by a convex polygon, we show how to construct the rotating rays Voronoi diagram within the polygon in optimal linear time. We can thus compute the Brocard angle of the polygon in the same time. Floodlights are used to model devices with limited sensing range, like surveillance cameras or directional antennas. In this context, the Brocard angle reveals the minimum range necessary for a set of devices to cover a domain., Acknowledgements: Initial discussions took place at the Intensive Research Program in Discrete, Combinatorial and Computational Geometry in Barcelona, Spain, in 2018. We are grateful to the 44 organizers for providing the platform to meet and collaborate. We also thank Hendrik Schrezenmaier 45 for early discussions related to the results of Section 3.1. Funding: Carlos Alegría: Supported by projects MIUR Proj. “AHeAD” no 20174LF3T8 and European Union’s Horizon 2020 No. 734922. Ioannis Mantas: Supported in part by SNF project 200021E_154387. Evanthia Papadopoulou: Supported in part by SNF projects 200021E_154387 and 200021E_201356. Marko Savić: Supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2022-14/200125), and the Provincial Secretariat for Higher Education and Scientific Research, Province of Vojvodina. Carlos Seara: Supported by projects PID2023-150725NB-I00 funded by Ministerio de Ciencia e Innovación/AEI/10.13039/501100011033 and European Union’s Horizon 2020 No. 734922. Martin Suderland: Supported in part by SNF project 200021E_201356., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The diameter of cyclic Kautz digraphs

  • Böhmová, Katerina
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Huemer, Clemens|||0000-0001-7557-0823
We present a new kind of digraphs, called cyclic Kautz digraphs CK(d, `), which are subdigraphs of the well-known Kautz digraphs K(d, `). The latter have the smallest diameter among all digraphs with their number of vertices and degree. Cyclic Kautz digraphs CK(d, `) have vertices labeled by all possible sequences a1 . . . a` of length `, such that each character ai is chosen from an alphabet containing d + 1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1 , a` . Their arcs are between vertices a1a2 . . . a` and a2 . . . aà`+1, with a1 , a` and a2 , a`+1. We give the diameter of CK(d, `) for all the values of d and `, and also its number of vertices and arcs
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On the randic index of graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, For a given graph G = (V, E), the degree mean rate of an edge uv ¿ E is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees d(u) and d(v). In this note, we derive tight bounds for the Randic index of G in terms of its maximum and minimum degree mean rates over its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randic index for graphs with order n large enough, when the minimum degree d is greater than (approximately) ¿1/3 , where ¿ is the maximum degree. As a by-product, this proves that almost all random (Erdos–Rényi) graphs satisfy the conjecture, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Locating domination in bipartite graphs and their complements

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, A set S of vertices of a graph G is distinguishing if the sets of neighbors in S for every pair of vertices not in S are distinct. A locating-dominating set of G is a dominating distinguishing set. The location-domination number of G, λ(G), is the minimum cardinality of a locating-dominating set. In this work we study relationships between λ(G) and λ(G) for bipartite graphs. The main result is the characterization of all connected bipartite graphs G satisfying λ(G) = λ(G) + 1. To this aim, we define an edge-labeled graph GS associated with a distinguishing set S that turns out to be very helpful., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Colored ray configurations

  • Fabila Monroy, Ruy
  • Garcia Olaverri, Alfredo Martin
  • Hurtado Díaz, Fernando Alfredo|||0000-0002-0108-9671
  • Jaume, Rafel
  • Pérez Lantero, Pablo
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Tejel Altarriba, Francisco Javier
  • Urrutia Galicia, Jorge
© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be T(n2) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Perfect matchings with crossings

  • Aichholzer, Oswin
  • Fabila Monroy, Ruy
  • Kindermann, Philipp
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Paul, Rosna
  • Perz, Daniel
  • Schnider, Patrick
  • Vogtenhuber, Birgit
For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least Cn/2 different plane perfect matchings, where Cn/2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k=164n2-3532nn--v+122564n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 572n2-n4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k=0,1,2 , and maximize the number of perfect matchings with (n/22) crossings and with (n/22)-1 crossings., Research on this work was initiated at the 16th European Research Week on Geometric Graphs which was held from November 18 to 22, 2019, near Strobl (Austria). We thank all participants for the good atmosphere as well as for discussions on the topic. Further, we thank Clemens Huemer for bringing this problem to our attention in the course of a meeting of the H2020-MSCA-RISE Project 734922 - CONNECT. O. A. and R. P. supported by FWF Grant W1230. P. S. supported by ERC Grant ERC StG 716424-CASe. D. P., I. P., and B. V. supported by FWF Project I 3340-N35. I. P. supported by the Independent Research Fund Denmark Grant 2020-2023 (9131-00044B) “Dynamic Network Analysis” and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity

  • Fabila Monroy, Ruy
  • Hidalgo Toscano, Carlos
  • Huemer, Clemens|||0000-0001-7557-0823
  • Lara, Dolores
  • Mitsche, Dieter
This is a post-peer-review, pre-copyedit version of an article published in International Symposium on Graph Drawing and Network Visualization. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-04414-5_42, How to draw the vertices of a complete multipartite graph G on different points of a bounded d-dimensional integer grid, such that the sum of squared distances between vertices of G is (i) minimized or (ii) maximized? For both problems we provide a characterization of the solutions. For the particular case d = 1, our solution for (i) also settles the minimum-2-sum problem for complete bipartite graphs; the minimum2-sum problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This motivates us to study which properties of the algebraic connectivity of graphs carry over to the restricted setting of drawings of graphs with integer coordinates.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
© 2020. 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 present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on n letters. We prove that every partition of the number n gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs and to a recent known family of mixed graphs (having edges with and without direction). As a byproduct, the existence of perfect codes in allows us to give a lower bound for the multiplicity of its eigenvalue -1., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Coloring decompositions of complete geometric graphs

  • Huemer, Clemens|||0000-0001-7557-0823
  • Lara, Dolores
  • Rubio-Montiel, Christian
This is a post-peer-review, pre-copyedit version of an article published in Acta Mathematica Hungarica. The final authenticated version is available online at: https://doi.org/10.1007/s10474-019-00963-0, A decomposition of a non-empty simple graph G is a pair [G,P] such that P is a set of non-empty induced subgraphs of G, and every edge of G belongs to exactly one subgraph in P. The chromatic index ¿'([G,P]) of a decomposition [G,P] is the smallest number k for which there exists a k-coloring of the elements of P in such a way that for every element of P all of its edges have the same color, and if two members of P share at least one vertex, then they have different colors. A long standing conjecture of Erdos–Faber–Lovász states that every decomposition [Kn,P] of the complete graph Kn satisfies ¿'([Kn,P])=n. In this paper we work with geometric graphs, and inspired by this formulation of the conjecture, we introduce the concept of chromatic index of a decomposition of the complete geometric graph. We present bounds for the chromatic index of several types of decompositions when the vertices of the graph are in general position. We also consider the particular case when the vertices are in convex position and present bounds for the chromatic index of a few types of decompositions.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Resolving dominating partitions in graphs

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
A partition ¿ ={S1,...,Sk}of the vertex set of a connected graphGis called aresolvingpartitionofGif for every pair of verticesuandv,d(u,Sj)6=d(v,Sj), for some partSj. Thepartition dimensionßp(G) is the minimum cardinality of a resolving partition ofG. A resolvingpartition ¿ is calledresolving dominatingif for every vertexvofG,d(v,Sj) = 1, for some partSjof ¿. Thedominating partition dimension¿p(G) is the minimum cardinality of a resolvingdominating partition ofG.In this paper we show, among other results, thatßp(G)=¿p(G)=ßp(G) + 1. We alsocharacterize all connected graphs of ordern=7 satisfying any of the following conditions:¿p(G) =n,¿p(G) =n-1,¿p(G) =n-2 andßp(G) =n-2. Finally, we present some tightNordhaus-Gaddum bounds for both the partition dimensionßp(G) and the dominating partitiondimension¿p(G)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The diameter of cyclic Kautz digraphs

  • Böhmová, Katerina
  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Huemer, Clemens|||0000-0001-7557-0823
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 MCK(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 containing d+1 distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that a1¿al. The cyclic Kautz digraphs CK(d,l) have arcs between vertices a1a2…al and a2…alal+1, with a1¿al, a2¿al+1, and ai¿ai+1 for i=1,…,l-1. The cyclic Kautz digraphs CK(d,l) are subdigraphs of the Kautz digraphs K(d,l). We give the main parameters of CK(d,l) (number of vertices, number of arcs, and diameter). Moreover, we construct the modified cyclic Kautz digraphs MCK(d,l) to obtain the same diameter as in the Kautz digraphs, and we show that MCK(d,l) are d -out-regular. Finally, we compute the number of vertices of the iterated line digraphs of CK(d,l).
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A general method to obtain the spectrum and local spectra of a graph from its regular partitions

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C -local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Received by the editors on February 20, 2020. Accepted for publication on May 27, 2020. Handling Editor: Sebastian M.Cioaba. Corresponding Author: Cristina Dalf ́o.†Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia (cristina.dalfo@udl.cat). Partiallysupported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922.‡Departament de Matem`atiques, Barcelona Graduate School of Mathematics, Universitat Polit`ecnica de Catalunya,Barcelona, Catalonia, (miguel.angel.fiol@upc.edu). Partially supported by AGAUR from the Catalan Government under project2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Spanning ratio of shortest paths in weighted square tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path SPw(s, t), which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path SGPw(s, t), which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio kSGPw(s,t)k kSPw(s,t)k is at most v 2 2+v 2 ˜ 1.08, irrespective of the weight assignment., P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is funded by an FPU of the Universidad de Alcalá., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Farthest color Voronoi diagrams: complexity and algorithms

  • Mantas, Ioannis
  • Papadopoulou, Evanthia|||0000-0003-0144-7384
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
The farthest-color Voronoi diagram (FCVD) is a farthestsite Voronoi structure defined on a family P of m point-clusters in the plane, where the total number of points is n. The FCVD finds applications in problems related to color spanning objects and facility location. We identify structural properties of the FCVD, refine its combinatorial complexity bounds, and list conditions under which the diagram has O(n) complexity. We show that the diagram may have complexity ¿(n + m2 ) even if clusters have disjoint convex hulls. We present construction algorithms with running times ranging from O(n log n), when certain conditions are met, to O((n+s(P)) log3 n) in general, where s(P) is a parameter reflecting the number of straddles between pairs of clusters in P (s(P) ¿ O(mn)). A pair of points q1, q2 ¿ Q is said to straddle p1, p2 ¿ P if the line segment q1q2 intersects (straddles) the line through p1, p2 and the disks through (p1, p2, q1) and (p1, p2, q2) contain no points of P, Q. The complexity of the diagram is shown to be O(n + s(P))., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Spectra and eigenspaces of arbitrary lifts of graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Pavlíková, Sona
  • Siran, Josef
This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-021-01049-3, We describe, in a very explicit way, a method for determining the spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not)., The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The authors S. Pavl´ıkov´a and J. Sir´aˇn acknowledge support from the ˇ APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Antimagic labelings of caterpillars

  • Lozano Boixadors, Antoni|||0000-0002-3633-063X
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Seara Ojea, Carlos|||0000-0002-0095-1725
A k-antimagic labeling of a graph G is an injection from E(G) to {1,2, ..., |E(G)|+k} such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to edges incident to u. We call a graph k-antimagic when it has a k-antimagic labeling, and antimagic when it is 0-antimagic. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic, but the conjecture is still open even for trees. Here we study k-antimagic labelings of caterpillars. We use algorithmic and constructive techniques, instead of the standard Combinatorial NullStellenSatz method, to prove our results: (i) any caterpillar of order n is (⌊(n−1)/2⌋−2)-antimagic; (ii) any caterpillar with a spine of order s with either at least ⌊(3s+1)/2⌋ leaves or ⌊(s−1)/2⌋ consecutive vertices of degree at most 2 at one end of a longest path, is antimagic; and (iii) if p is a prime number, any caterpillar with a spine of order p, p−1 or p−2 is 1-antimagic., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Maximum box problem on stochastic points

  • Caraballo, Luis E.
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Ventura, Inmaculada
This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00453-021-00882-z., Given a finite set of weighted points in Rd (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in d=1 these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For d=2, we consider that each point is colored red or blue, where red points have weight +1 and blue points weight -8. The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane., This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

General bounds on limited broadcast domination

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Pelayo Melero, Ignacio Manuel|||0000-0002-6523-0611
  • Cáceres, José
  • Puertas, M. Luz
Dominating broadcasting is a domination-type structure that models a transmission antenna network. In this paper, we study a limited version of this structure, that was proposed as a common framework for both broadcast and classical domination. In this limited version, the broadcast function is upper bounded by an integer k and the minimum cost of such function is the dominating k-broadcast number. Our main result is a unified upper bound on this parameter for any value of k in general graphs, in terms of both k and the order of the graph. We also study the computational complexity of the associated decision problem
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Separating bichromatic point sets in the plane by restricted orientation convex hulls

  • Alegría Galicia, Carlos
  • Orden Martin, David
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Urrutia Galicia, Jorge
The version of record is available online at: http://dx.doi.org/10.1007/s10898-022-01238-9, We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and O be a set of k=2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of O for which the O-convex hull of R contains no points of B. For k=2 orthogonal lines we have the rectilinear convex hull. In optimal O(nlogn) time and O(n) space, n=|R|+|B|, we compute the set of rotation angles such that, after simultaneously rotating the lines of O around the origin in the same direction, the rectilinear convex hull of R contains no points of B. We generalize this result to the case where O is formed by k=2 lines with arbitrary orientations. In the counter-clockwise circular order of the lines of O, let ai be the angle required to clockwise rotate the ith line so it coincides with its successor. We solve the problem in this case in O(1/T·NlogN) time and O(1/T·N) space, where T=min{a1,…,ak} and N=max{k,|R|+|B|}. We finally consider the case in which O is formed by k=2 lines, one of the lines is fixed, and the second line rotates by an angle that goes from 0 to p. We show that this last case can also be solved in optimal O(nlogn) time and O(n) space, where n=|R|+|B|., Carlos Alegría: Research supported by MIUR Proj. “AHeAD” no 20174LF3T8. David Orden: Research supported by Project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACY, This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie Grant Agreement No 734922., Peer Reviewed