Source author record

Anna Lladó

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Distance-constrained labellings of Cartesian products of graphs

An $L(h_1, h_2, \ldots, h_l)$ -labelling of a graph $G$ is a mapping $ϕ: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$ , we have $|ϕ(u) - ϕ(v)| \geq h_i$ . The span of $ϕ$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $ϕ$ , and $λ_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$ -labellings of $G$ . In this paper we study $λ_{h, 1, \ldots, 1}$ for Cartesian products of graphs, where $(h, 1, \ldots, 1)$ is an $l$ -tuple with $l \ge 3$ . We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$ -th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$ . All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\ldots ,q_d}$ satisfies $λ_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1$ whenever $q_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d$ . In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.

preprint2015arXiv

Decomposing almost complete graphs by random trees

An old conjecture of Ringel states that every tree with $m$ edges decomposes the complete graph $K_{2m+1}$ . The best known lower bound for the order of a complete graph which admits a decomposition by every given tree with $m$ edges is $O(m^3)$ . We show that asymptotically almost surely a random tree with $m$ edges and $p=2m+1$ a prime decomposes $K_{2m+1}(r)$ for every $r\ge 2$ , the graph obtained from the complete graph $K_{2m+1}$ by replacing each vertex by a coclique of order $r$ . Based on this result we show, among other results, that a random tree with $m+1$ edges a.a.s. decomposes the compete graph $K_{6m+5}$ minus one edge.

preprint2015arXiv

On star-forest ascending subgraph decomposition

The Ascending Subgraph Decomposition (ASD) Conjecture asserts that every graph $G$ with ${n+1\choose 2}$ edges admits an edge decomposition $G=H_1\oplus\cdots \oplus H_n$ such that $H_i$ has $i$ edges and it is isomorphic to a subgraph of $H_{i+1}$ , $i=1,\ldots ,n-1$ . We show that every bipartite graph $G$ with ${n+1\choose 2}$ edges such that the degree sequence $d_1,\ldots ,d_k$ of one of the stable sets satisfies $d_{k-i}\ge n-i\; \text{for each}\; 0\le i\le k-1,$ , admits an ascending subgraph decomposition with star forests. We also give a necessary condition on the degree sequence which is not far from the above sufficient one.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.