Some Constructions on Total Labelling of m Triangles

摘要

Let mK_3 = (V_m, E_m) be a finite disconnected graph consisting of m disjoint triangles K_3, where V_m is the set of vertices, E_m is the set of edges and both V_m and E_m are of the same size 3m. A total labelling of mK_3 is a function f which maps the elements in V_m and E_m to positive integer values, i.e. f : V_m ∪ E_m → {1,2,3,…}. Let c be a positive integer. A triangle is said have a c-Erdosian triangle labelling if it is a total labelling f : V_m ∪ E_m → {c,c + 1,…,c + 6m - 1} such that f(x) + f(y) = f(xy) for any x, y ∈ V_m and an edge xy ∈ E_m joining them. In order to find all the c-Erdosian triangle labelling, a straightforward is to use the exhaustive search. However, the exhaustive search is only able to find c-Erdosian triangle labelling for m ≤ 5 due to combinatorial explosion. By studying the constant sum of vertex labels, we propose a strong permutation approach, which allows us to generate a certain classes of c-Erdosian triangle labelling up until m = 8.