Seminár z teórie grafov - Anna Dresslerova (7.4.2016)

vo štvrtok 7.4.2016 o 9:50 hod. v miestnosti M/213

---

Prednášajúca: Anna Dresslerová

Názov: L(2,1)-labelling of cacti

Termín: 7.4.2016, 9:50 hod., M/213

Abstrakt:
An L(2,1)-labelling is a labelling of the vertex set of graph with non-negative integers such that the labels of adjacent vertices differ by at least 2 and the labels of vertices at distance 2 are distinct. It is required to determine, for a given graph G, the smallest integer k such that G admits an L(2,1)-labelling with integers not exceeding k; this invariant is denoted by $\lambda(G)$. Determining $\lambda(G)$ is known to be a hard problem. To test whether $\lambda(G) \leq k$ is NP-complete even for series-parallel graphs. On the other hand, there exist classes of graphs where this problem is polynomially solvable (e.g. trees or their mild generalisations). In this talk we derive tight upper and lower bounds for the $\lambda$-number of cacti. We also present a polynomial-time algorithm which computes the $\lambda$-number of an arbitrary cycle-tree (cactus with disjoint cycles).

 

 

---