- FR
- EN
lundi 28 Janvier 2019, 14h, salle A (2ième étage)
Abstract :
A graceful difference labeling of a directed graph G with vertex set V is a bijection f from the vertex set V to the integers from 1 to n (n being the number of vertices) such that, when each arc uv is assigned the difference label f (v)-f (u), the resulting arc labels are distinct.
We are interested in the case where G is a union of vertex disjoint directed cycles. When G is a collection of n directed vertex disjoint triangles, we show that G has a graceful difference labeling if and only if n is not one.
The proof is constructive. Let t be the number of triangles. From the remainder of t divided by 7 four subcases are considered. Then the main ingredient is a recurrence in which the basic cases are from t equals 2 to t equals 9.
Then we use this result to prove more general cases.
The talk is based on joint works wirh A. Hertz.
