On defining numbers of vertex colouring of regular graphs (Q1292860): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q322366 |
||
Property / author | |||
Property / author: Ebadollah S. Mahmoodian / rank | |||
Revision as of 21:57, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On defining numbers of vertex colouring of regular graphs |
scientific article |
Statements
On defining numbers of vertex colouring of regular graphs (English)
0 references
3 November 1999
0 references
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)\).
0 references
regular graph
0 references
colouring
0 references
defining set
0 references
defining number
0 references