Harmonious colouring of line graph of commuting and non-commuting graph of \(D_{2n}\) (Q7005316)

Harmonious coloring of a graph \(G=(V,E)\) is a coloring of its vertices such that each pair of colors appears at most on one pair of adjacent vertices (and there are no adjacent vertices colored in the same color). The minimum number of colors required for a harmonious coloring of \(G\) is called the harmonious chromatic number \(\chi_H(G)\). It has many applications in radio navigation systems, addressing the blocks, communication networks, etc. The problem whether \(\chi_H(G)\leq k\) for a given \(k\leq \vert V\vert\) was defined in [\textit{J. E. Hopcroft} and \textit{M. S. Krishnamoorthy}, SIAM J. Algebraic Discrete Methods 4, 306--311 (1983; Zbl 0543.05028)] and it was shown that it is NP-complete. \N\NThe line graph \(L(G)\) of the graph \(G\) has vertices the set \(E\) of the edges of \(G\) and two vertices of \(L(G)\) are adjacent if the corresponding edges of \(G\) share a common vertex. \N\NIn the paper under review, the authors study the harmonious colorings of the line graphs of the commuting and non-commuting graphs of the dihedral group \(D_{2n}\). Recall that the elements of \(D_{2n}\) are the vertices of the commuting graph \(C(D_{2n})\) and \(\{x,y\}\) is an edge of \(C(D_{2n})\) if \(xy=yx\), \(x,y\in D_{2n}\). In their previous paper [Sarajevo J. Math. 17(30), No. 2, 143--150 (2021; Zbl 1513.05187)], the authors obtained the chromatic number, the clique number and the genus of the line graph \(G=L(C(D_{2n}))\). Now, they determine its harmonious chromatic number \(\chi_H(G)\):\N\[\N\chi_H(G)=\frac{n(n+1)}{2}\text{ for }n\text{ odd and }\chi_H(G)=\frac{n(n+3)}{2}\text{ for }n\text{ even.}\N\]\NThe vertices of the non-commuting graph \(\mathrm{NC}(D_{2n})\) are the non-central elements of \(D_{2n}\) and \(\{x,y\}\) is an edge if \(xy\not= yx\). The second result of the paper under review gives the harmonious chromatic number \(\chi_H(G)\) for \(G=L(\mathrm{NC}(D_{2n}))\):\N\[\N\chi_H(G)=\frac{3n(n-1)}{2}\text{ for }n\text{ odd and }\chi_H(G)=\frac{3n(n-2)}{2}\text{ for }n\text{ even.}\N\]