Name
Abstract | ||
|---|---|---|
We introduce the total distinguishing number D "(G) of a graph G as the least number d such that G has a total colouring (not necessarily proper) with d colours that is only preserved by the trivial automorphism. This is an analog to the notion of the distinguishing number D (G), and the distinguishing index D' (G), which are defined for colourings of vertices and edges, respectively. We obtain a general sharp upper bound: D "(G) <= [root Delta(G)] for every connected graph G. We also introduce the total distinguishing chromatic number chi(")(D)(G) similarly defined for proper total colourings of a graph G. We prove that chi(")(D)(G) <= chi "(G) + 1 for every connected graph G with the total chromatic number chi "(G). Moreover, if chi "(G) >= Delta(G)+ 2, then chi(")(D)(G) = chi "(G). We prove these results by setting sharp upper bounds for the minimal number of colours in a proper total colouring such that each vertex has a distinct set of colour walks emanating from it. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.26493/1855-3974.751.9a8 | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Total colourings of graphs,symmetry breaking in graphs,total distinguishing number,total distinguishing chromatic number | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Chromatic scale,Automorphism,Upper and lower bounds,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
11 | 1 | 1855-3966 |
Citations | PageRank | References |
1 | 0.41 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rafał Kalinowski | 1 | 48 | 10.75 |
| Monika Pilśniak | 2 | 28 | 9.31 |
| Mariusz Woźniak | 3 | 204 | 34.54 |