On defining numbers of vertex colouring of regular graphs (Q1292860): Difference between revisions

In a given graph \(G\), a set of vertices \(S\) with an assignment of colours to them is called a defining set of the vertex colouring of \(G\), if there exists a unique extension of the colours of \(S\) to a \(\chi (G)\)-colouring of the vertices of \(G\), \(\chi (G)\) being the chromatic number of \(G\). A defining set with minimum cardinality is called a minimum defining set (of a vertex colouring) and its cardinality is the defining number, denoted by \(d(G,\chi)\). Among other results, the exact value of \(d(n,r,\chi =r)\), the minimum defining number of all \(r\)-regular \(r\)-chromatic graphs of order \(n\) is determined for some small values of \(r\). Namely for \(r=3,4\), and 5 we have \(d(n,r,\chi =r)=\lfloor ((r-2)(n+ r-3)+2)/(2(r-1))\rfloor \), except possibly for \((n,r)=(10,5)\).