Total activity: 177

## Scientific and technological production Ordered by:  Date asc. Date desc. Title asc. Title desc. Researcher asc. Researcher desc.

1 to 50 of 177 results
• Combinatorics probability and computing

Combinatorics probability and computing
Vol. 23, num. 1, p. 50-65
DOI: 10.1017/S0963548313000485
Date of publication: 2014-01-06
Journal article

We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K 2m,2m , a result connected to a conjecture of Graham and Häggkvist. The result also implies that asymptotically almost surely a tree with m edges decomposes the complete graph with O(m 2) edges. An ingredient of the proof consists in showing that the bipartition classes of the base tree of a random tree have roughly equal size.

• Almost every tree with m edges decomposes K2m,2m

Combinatorics probability and computing
Vol. 23, num. 1, p. 50-65
DOI: 10.1017/S0963548313000485
Date of publication: 2014-01
Journal article

We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K2m,2m, a result connected to a conjecture of Graham and Häggkvist. The result also implies that asymptotically almost surely a tree with m edges decomposes the complete graph with O(m2) edges. An ingredient of the proof consists in showing that the bipartition classes of the base tree of a random tree have roughly equal size. © Cambridge University Press 2013.

• On vosperian and superconnected vertex-transitive digraphs

Hamidoune, Yahya O.; Llado Sanchez, Anna; López Masip, Susana Clara
Graphs and combinatorics
Vol. 29, num. 2, p. 241-251
DOI: 10.1007/s00373-011-1104-4
Date of publication: 2013
Journal article

• On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity

European journal of combinatorics
Vol. 34, num. 8, p. 1406-1410
DOI: 10.1016/j.ejc.2013.05.023
Date of publication: 2013-09-02
Journal article

• Algunas conjeturas sobre descomposiciones de grafos

Congreso de la Real Sociedad Española de Matemáticas
p. 1
Presentation's date: 2013-01-25
Presentation of work at congresses

• On a conjecture of Graham and Häggkvist for random trees

European Conference on Combinatorics, Graph Theory and Applications
p. 221-226
Presentation's date: 2013-09-11
Presentation of work at congresses

• On the modular sumset partition problem

Llado Sanchez, Anna; Moragas Vilarnau, Jordi
European journal of combinatorics
Vol. 33, num. 4, p. 427-434
DOI: 10.1016/j.ejc.2011.09.001
Date of publication: 2012-04-28
Journal article

A sequence m 1=m 2=¿;=m k of k positive integers isn-realizable if there is a partition X 1, X 2,..., X k of the integer interval [1, n] such that the sum of the elements in X i is m i for each i=1, 2,..., k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k=(p-1)/2 are realizable for any prime p=3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n=(4k) 3, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability. © 2011 Elsevier Ltd.

• Magic and antimagic H-decompositions

Inayah, Nur; Llado Sanchez, Anna; Moragas Vilarnau, Jordi
Discrete mathematics
Vol. 312, num. 7, p. 1367-1371
DOI: 10.1016/j.disc.2011.11.041
Date of publication: 2012-12-03
Journal article

A decomposition of a graph G into isomorphic copies of a graph H is H-magic if there is a bijection f:V(G)¿E(G)¿0,1,...,|V(G)|+|E(G)|-1 such that the sum of labels of edges and vertices of each copy of H in the decomposition is constant. It is known that complete graphs do not admit K2-magic decompositions for n>6. By using the results on the sumset partition problem, we show that the complete graph K2 m+1 admits T-magic decompositions by any graceful tree with m edges. We address analogous problems for complete bipartite graphs and for antimagic and (a,d)-antimagic decompositions. © 2012 Elsevier B.V. All rights reserved.

• Yahya Ould Hamidoune, 1948--2011

Llado Sanchez, Anna; Serra Albo, Oriol; Plagne, Alain
Date: 2012-03-01
Report

• Optimización y problemas extremales en teoria de grafos y combinatoria. Aplicacions a les redes de comunicación

Aguilo Gost, Francisco de Asis Luis; Abiad Monge, Aida; Andrés Yebra, José Luis; Barriere Figueroa, Eulalia; Cámara Vallejo, Marc; Ball, Simeon Michael; Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Gomez Marti, Jose; Llado Sanchez, Anna; López Masip, Susana Clara; Miralles De La Asuncion, Alicia; Mitjana Riera, Margarida; Muñoz Lopez, Francisco Javier; Pelayo Melero, Ignacio Manuel; Garriga Valle, Ernest; Pérez Mansilla, Sonia; Rius Font, Miquel; Serra Albo, Oriol; Vena, Lluis; Vilaltella Castanyer, Joan; Zaragoza Monroig, Maria Luisa; Espona Dones, Margarida; Sau Valls, Ignasi; Montejano Cantoral, Amanda; Perarnau Llobet, Guillem; Moragas Vilarnau, Jordi; Vena Cros, Lluís; Andres Yebra, Jose Luis; Fiol Mora, Miquel Àngel
Participation in a competitive project

• Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors

Hamidoune, Yayha Old; Llado Sanchez, Anna; López Masip, Susana Clara
Journal of graph theory
Vol. 67, num. 2, p. 124-138
DOI: 10.1002/jgt.20521
Date of publication: 2011-06
Journal article

A d-regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex and its neighbors will be called vosperian. Let Γ be a vertex-transitive graph of degree d with order at least d+4. We give necessary and sufficient conditions for the vosperianity of Γ. Moreover, assuming that distinct vertices have distinct neighbors, we show that Γ is vosperian if and only if it is superconnected. Let G be a group and let S⊂G\{1} with S=S−1. We show that the Cayley graph, Cay(G, S), defined on G by S is vosperian if and only if G\(S∪{1}) is not a progression and for every non-trivial subgroup H and every a∈G, If moreover S is aperiodic, then Cay(G, S) is vosperian if and only if it is superconnected.

• Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors

Hamidoune, Yayha Old; Llado Sanchez, Anna; López Masip, Susana Clara
Journal of graph theory
Vol. 67, num. 2, p. 124-138
DOI: 10.1002/jgt.20521
Date of publication: 2011-12-05
Journal article

• Almost every tree decomposes K2n,2n

European Conference on Combinatorics, Graph Theory and Applications
p. 571-574
DOI: 10.1016/j.endm.2011.09.093
Presentation's date: 2011-09-06
Presentation of work at congresses

• Every tree is a large subtree of a tree that decomposes Kn or Kn,n

Llado Sanchez, Anna; López Masip, Susana Clara; Moragas Vilarnau, Jordi
Discrete mathematics
Vol. 310, num. 4, p. 838-842
DOI: 10.1016/j.disc.2009.09.021
Date of publication: 2010-02-28
Journal article

Let T be a tree with m edges. A well-known conjecture of Ringel states that T decomposes the complete graph $K_{2m+1}$. Graham and Häggkvist conjectured that T also decomposes the complete bipartite graph $K_{m,m}$. In this paper we show that there exists an integer n with n ≤[(3m - 1)/2] and a tree T₁ with n edges such that T₁ decomposes $K_{2n+1}$ and contains T. We also show that there exists an integer n' with n' ≥ 2m-1 and a tree T₂ with n' edges such that T₂ decomposes $K_{n',n'}$and contains T. In the latter case, we can improve the bound if there exists a prime p such that [3m/2] ≤ p < 2m - 1.

• Graph labelings and decompositions by partitioning sets of integers

Moragas Vilarnau, Jordi
Department of Applied Mathematics IV, Universitat Politècnica de Catalunya
Theses

This work is a contribution to the study of various problems that arise from two strongly connected areas of the Graph Theory: graph labelings and graph decompositions. Most graph labelings trace their origins to the ones presented in 1967 by Rosa. One of these labelings, widely known as the graceful labeling, originated as a means of attacking the conjecture of Ringel, which states that the complete graph of order 2m+1 can be decomposed into m copies of a given tree of size m. Here, we study related labelings that give some approaches to Ringel's conjecture, as well as to another conjecture by Graham and Häggkvist that, in a weak form, asks for the decomposition of a complete bipartite graph by a given tree of appropriate size. Our main contributions in this topic are the proof of the latter conjecture for double sized complete bipartite graphs being decomposed by trees with large growth and prime number of edges, and the proof of the fact that every tree is a large subtree of two trees for which both conjectures hold respectively. These results are mainly based on a novel application of the so-called polynomial method by Alon. Another kind of labelings, the magic labelings, are also treated. Motivated by the notion of magic squares in Number Theory, in these type of labelings we want to assign integers to the parts of a graph (vertices, edges, or vertices and edges) in such a way that the sums of the labels assigned to certain substructures of the graph remain constant. We develop techniques based on partitions of certain sets of integers with some additive conditions to construct cycle-magic labelings, a new brand introduced in this work that extends the classical magic labelings. Magic labelings do not provide any graph decomposition, but the techniques that we use to obtain them are the core of another decomposition problem, the ascending subgraph decomposition (ASD). In 1987, was conjectured by Alavi, Boals. Chartrand, Erdös and Oellerman that every graph has an ASD. Here, we study ASD of bipartite graphs, a class of graphs for which the conjecture has not been shown to hold. We give a necessary and a sufficient condition on the one sided degree sequence of a bipartite graph in order that it admits an ASD by star forests. Here the techniques are based on the existence of edge-colorings in bipartite multigraphs. Motivated by the ASD conjecture we also deal with the sumset partition problem, which asks for a partition of [n] in such a way that the sum of the elements of each part is equal to a prescribed value. We give a best possible condition for the modular version of the sumset partition problem that allows us to prove the best known results in the integer case for n a prime. The proof is again based on the polynomial method.

• On the ASD conjecture

Llado Sanchez, Anna; Moragas Vilarnau, Jordi
Jornadas de Matemática Discreta y Algorítmica
p. 409-423
Presentation's date: 2010-06-10
Presentation of work at congresses

Let G be a graph of size ($\displaystyle\frac{n+1}{2}$) for some integer n ≥ 1. G is said to have an ascending subgraph decomposition (ASD) if can be decomposed into n subgraphs H1, . . . ,Hn such that Hi has i edges and is isomorphic to a subgraph of Hi+1, i = 1, . . . , n−1. In this work we deal with ascending subgraph decompositions of bipartite graphs. In order to do so, we consider ascending subgraph decompositions in which each factor is a forest of stars. We show that every bipartite graph G with($\displaystyle\frac{n+1}{2}$)edges such that the degree sequence d1 ≥ · · · ≥ dk of one of the partite sets satisfies d1 ≥ (k − 1)(n − k + 1), and di ≥ n − i + 2 for 2 ≤ i < k, admits an ASD with star forests. We also give a necessary condition on the degree sequence of G to have an ascending subgraph decomposition into star forests that is not far from the above sufficient one. Our results are based on the existence of certain matrices that we call ascending and the construction of edge-colorings of some bipartite graphs with parallel edges.

• On the sumset partition problem

Llado Sanchez, Anna; Moragas Vilarnau, Jordi
French Combinatorial Conference
Presentation's date: 2010-07-02
Presentation of work at congresses

• On the ascending subgraph decomposition problem for bipartite graphs

Moragas Vilarnau, Jordi; Llado Sanchez, Anna
Joint Mathematical Conference CSASC
Presentation's date: 2010-01-26
Presentation of work at congresses

• On vosperian and superconnected arc-transitive digraphs

Hamidoune, Yayha Old; Llado Sanchez, Anna; López Masip, Susana Clara
International Workshop on Optimal Network Topologies
p. 143-150
Presentation's date: 2010-06-08
Presentation of work at congresses

• On a conjecture of Graham and Haggkvist with the polynomial method

Cámara Vallejo, Marc; Llado Sanchez, Anna; Moragas Vilarnau, Jordi
European journal of combinatorics
Vol. 30, num. 7, p. 1585-1592
DOI: 10.1016/j.ejc.2009.03.008
Date of publication: 2009-10
Journal article

• PROBLEMAS EXTREMALES Y DE OPTIMIZACIÓN EN TEORIA DE GRAFOS Y COMBINATORIA: APLICACIÓN AL ANALISIS Y ALGORITMOS DE REDES DE COMUNICAC

Abiad Monge, Aida; Andres Yebra, Jose Luis; Aguilo Gost, Francisco de Asis Luis; Aroca Farrerons, Josep Maria; Ball, Simeon Michael; Barajas Tomas, Javier; Barguilla Navarrete, Jorge; Barriere Figueroa, Eulalia; Cámara Vallejo, Marc; Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Espona Dones, Margarida; Fàbrega Canudas, Josep; Gago Alvarez, Silvia; Garriga Valle, Ernest; Gomez Marti, Jose; Llado Sanchez, Anna; López Masip, Susana Clara; Miralles De La Asuncion, Alicia; Mitjana Riera, Margarida; Montejano Cantoral, Amanda; Moragas Vilarnau, Jordi; Muñoz Lopez, Francisco Javier; Pelayo Melero, Ignacio Manuel; Perarnau Llobet, Guillem; Pérez Mansilla, Sonia; Rius Font, Miquel; Sau Valls, Ignasi; Serra Albo, Oriol; Vena, Lluis; Vilaltella Castanyer, Joan; Zaragoza Monroig, Maria Luisa; Vena Cros, Lluís; Fiol Mora, Miquel Àngel
Participation in a competitive project

• COMBINATÒRIA , TEORIA DE GRAFS I APLICACIONS

López Masip, Susana Clara; Comellas Padro, Francesc de Paula; Fiol Mora, Miquel Àngel; Cámara Vallejo, Marc; Moragas Vilarnau, Jordi; Aguilo Gost, Francisco de Asis Luis; Aroca Farrerons, Josep Maria; Rius Font, Miquel; Espona Dones, Margarida; Garriga Valle, Ernest; Dalfo Simo, Cristina; Muñoz Lopez, Francisco Javier; Fàbrega Canudas, Josep; Miralles De La Asuncion, Alicia; Gomez Marti, Jose; Zaragoza Monroig, Maria Luisa; Pérez Mansilla, Sonia; Andres Yebra, Jose Luis; Ball, Simeon Michael; Barriere Figueroa, Eulalia; Llado Sanchez, Anna; Mitjana Riera, Margarida; Gago Alvarez, Silvia; Pelayo Melero, Ignacio Manuel; Serra Albo, Oriol
Participation in a competitive project

• On vosperian and superconnected vertex-transitive digraphs

López Masip, Susana Clara; Hamidoune, Yayha Old; Llado Sanchez, Anna
British Combinatorial Conference
p. 21
DOI: 10.1007/s00373-011-1104-4
Presentation's date: 2009-07
Presentation of work at congresses

Weinvestigatethestructureofadigraphhavingatransitiveautomorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization of vosperian arc-transitive digraphs. It states that an arc-transitive strongly connected digraph is vosperian if and only if it is irreducible. In particular, this is the case if the degree is coprime with the order of the digraph. We give also a complete characterization of vosperian Cayley digraphs and a complete characterization of irreducible superconnected Cayley digraphs. These two last characterizations extend the corresponding ones in Abelian Cayley digraphs and the ones in the undirected case.

• On the sumset partition problem

Llado Sanchez, Anna; Moragas Vilarnau, Jordi
European Conference on Combinatorics, Graph Theory and Applications
p. 15-19
Presentation's date: 2009-09
Presentation of work at congresses

• Chairman session

Building Bridges
Presentation's date: 2008-08-09
Presentation of work at congresses

• Cyclic decompositions of K_n and K_n,n by a tree with a given large subtree

Llado Sanchez, Anna; López Masip, Susana Clara; Moragas Vilarnau, Jordi
Jornadas de Matemática Discreta y Algorítmica
p. 425-430
Presentation's date: 2008-07-22
Presentation of work at congresses

• Cyclic decompositions of K_n by a given tree

Jornadas de Matemática Discreta y Algorítmica
Presentation's date: 2008-07-21
Presentation of work at congresses

• Sumset Partition Problem

Jornadas de Matemática Discreta y Algorítmica
p. 431-437
Presentation of work at congresses

• Sumset Partition Problem

Jornadas de Matemática Discreta y Algorítmica
Presentation's date: 2008-07-21
Presentation of work at congresses

• Minisimposia Combstru

European Congress of Mathematics
Presentation's date: 2008-07-14
Presentation of work at congresses

• Cyclic decompositions of Kn and Kn,n by a tree with a given subtree

Llado Sanchez, Anna; López Masip, Susana Clara
Jornadas de Matemática Discreta y Algorítmica
p. 425-431
Presentation of work at congresses

• Invitación a la matemática discreta

Matousek, Jirka; Jaroslav, Nesetril; Llado Sanchez, Anna
Date of publication: 2008-06-30
Book

• On complete subsets of the cyclic group

Hamidoune, Yahya O.; Llado Sanchez, Anna; Serra Albo, Oriol
Journal of combinatorial theory. Series A
Vol. 115, num. 7, p. 1279-1285
Date of publication: 2008-10
Journal article

• Partición de un conjunto de enteros con sumas prescritas

Llado Sanchez, Anna; Moragas Vilarnau, Jordi
Jornadas de Matemática Discreta y Algorítmica
p. 431-436
Presentation's date: 2008-07
Presentation of work at congresses

• Largest cliques in connected supermagic graphs

European journal of combinatorics
Vol. 28, num. 8, p. 2240-2247
Date of publication: 2007-11
Journal article

• Cycle-magic graphs

Discrete mathematics
Vol. 307, num. 23, p. 2925-2933
Date of publication: 2007-09
Journal article

A simple graph G=(V,E) admits a cycle-covering if every edge in E belongs at least to one subgraph of G isomorphic to a given cycle C. Then the graph G is C-magic if there exists a total labelling f : V ∪ E → {1, 2, . . . , |V | + |E|} such that, for every subgraph H'=(V',E') of G isomorphic to C, $\Sigma_{v\in V'^{f{(v)}}}$ + $\Sigma{e \in E'}f^{(e)}$ is constant. When f(V)= {1, . . . , |V|}, then G is said to be C-supermagic. We study the cyclic-magic and cyclic-supermagic behavior of several classes of connected graphs. We give several families of Cr -magic graphs for each r≥3. The results rely on a technique of partitioning sets of integers with special properties.

• On a Häggkvist's Conjecture with the Polynomial Method

Cámara Vallejo, Marc; Llado Sanchez, Anna; Moragas Vilarnau, Jordi
Electronic notes in discrete mathematics
Vol. 29, num. C, p. 559-563
Date of publication: 2007-08
Journal article

• On a H¨aggkvist¿s Conjecture with the Polynomial Method

European Conference on Combinatorics, Graph Theory, and Applications
p. 559-563
Presentation of work at congresses

• Magic coverings

Journal of combinatorial mathematics and combinatorial computing
Vol. 55, p. 43-56
Date of publication: 2006-01
Journal article

• Any tree is a large subgraph of a magic tree

The australasian journal of combinatorics
Vol. 35, p. 291-297
Date of publication: 2006-05
Journal article

• Grafos H-magicos

Jornadas de Matemática Discreta y Algorítmica
p. 327-334
Presentation's date: 2006-07-12
Presentation of work at congresses

• Grafos H-mágicos

Llado Sanchez, Anna; Moragas Vilarnau, Jordi
Jornadas de Matemática Discreta y Algorítmica
p. 327-334
Presentation's date: 2006-07
Presentation of work at congresses

• Edge-decompositions of K {n,n} into isomorphic copies of a given tree

Llado Sanchez, Anna; López Masip, Susana Clara
Journal of graph theory
Vol. 48, num. 1, p. 1-18
Date of publication: 2005-01
Journal article

• Combinatòria, Teoria de Grafs i Aplicacions

Serra Albo, Oriol; Aguilo Gost, Francisco de Asis Luis; Andrés Yebra, José Luis; Balbuena Martinez, Maria Camino Teofila; Ball, Simeon Michael; Barajas Tomas, Javier; Barguilla Navarrete, Jorge; Barriere Figueroa, Eulalia; Comellas Padro, Francesc de Paula; Dalfo Simo, Cristina; Fàbrega Canudas, Josep; Fiol Mora, Miquel Àngel; Garriga Valle, Ernest; Gomez Marti, Jose; Llado Sanchez, Anna; López Masip, Susana Clara; Marcote Ordax, Francisco Javier; Miralles De La Asuncion, Alicia; Mitjana Riera, Margarida; Moragas Vilarnau, Jordi; Montejano Cantoral, Amanda; Muñoz Lopez, Francisco Javier; Pelayo Melero, Ignacio Manuel; Pérez Mansilla, Sonia; Rius Font, Miquel; Zaragoza Monroig, Maria Luisa
Participation in a competitive project

• Largest cliques in supermagic graphs

European Conference on Combinatorics, Graph Theory and Applications
Presentation's date: 2005-09-06
Presentation of work at congresses

• Coverings and morphisms

2nd Workshop on Morphisms on Graphs and applications
Presentation's date: 2005-09-24
Presentation of work at congresses

• Largest cliques in supermagic graphs

European Conference on Combinatorics, Graph Theory and Applications
p. 212-222
Presentation of work at congresses

• Coverings and morphisms

2nd Workshop on Morphisms on Graphs and applications
Presentation's date: 2005-09-24
Presentation of work at congresses

• Largest cliques in supermagic graphs