Graphs which have \(n/2\)-minimal line-distinguishing colourings (Q1923477)

A graph \(G\) is defined to be \(k\)-MLD-colorable if \(G\) has a \(k\)-vertex coloring (not necessarily proper) for which each pair of colors (not necessarily distinct) appear on exactly one edge of \(G\). Given \(G\) with \(p\) vertices and degree sequence \(S\) which is \(p/2\)-MLD-colorable, the authors show how to obtain any other graph on \(p\) vertices and degree sequence \(S\). For each \(r\geq1\), an \(r\)-regular \(p/2\)-MLD-colorable graph is constructed; for \(r=3, 5\), and \(r\geq 7\) the graphs can be constructed so as to have diameter 2. For \(r=1\) and \(r=2\), the unique examples are \(K_2\) and \(C_6\) respectively; neither has diameter 2. Thus only the cases \(r=4\) and \(r=6\) are open.