Graphs which have n/2-minimal line-distinguishing colourings Original Research Article

A graph G is said to be k-MLD-colourable if G possesses a k-vertex colouring such that each pair of colours appears on precisely one edge of G. Given G with n vertices and valency sequence S which is n/2-MLD-colourable it is shown how any other graph on n vertices with valency sequence S can be obtained. For each ϱ ⩾ 1 a ϱ-regular n/2-MLD-colourable graph is constructed and for ϱ = 3, 5 and ϱ ⩾ 7 such a graph having diameter 2 is found. Since the cases ϱ = 1 and ϱ = 2 are trivial this leaves only the cases ϱ = 4 and ϱ = 6 unsettled.