Name
Abstract | ||
|---|---|---|
The distinguishing index of a graph G, denoted by D' (G), is the least number of colours in an edge colouring of G not preserved by any non-trivial automorphism. We characterize all connected graphs G with D' (G) >= Delta(G). We show that D'(G) <= 2 if G is a traceable graph of order at least seven, and D'(G) <= 3 if G is either claw-free or 3-connected and planar. We also investigate the Nordhaus-Gaddum type relation: 2 <= D'(G) + D'((G) over bar) <= max { Delta(G); Delta((G) over bar)} + 2 and we confirm it for some classes of graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.26493/1855-3974.981.ff0 | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Edge colouring,symmetry breaking in graph,distinguishing index,claw-free graph,planar graph | Topology,Discrete mathematics,Graph,Combinatorics,Claw-free graph,Automorphism,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
13 | 2 | 1855-3966 |
Citations | PageRank | References |
2 | 0.48 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Monika Pilśniak | 1 | 28 | 9.31 |