Name
Abstract | ||
|---|---|---|
The distinguishing index D'(G) of a graph G is the least natural number d such that G has an edge colouring with d colours that is only preserved by the identity automorphism. In this paper we investigate the distinguishing index of the Cartesian product of connected finite graphs. We prove that for every k >= 2, the k -th Cartesian power of a connected graph G has distinguishing index equal 2, with the only exception D'(K-2(2)) - 3. We also prove that if G and H are connected graphs that satisfy the relation 2 <= vertical bar G vertical bar <= vertical bar H vertical bar <= 2 vertical bar G vertical bar (2(parallel to G parallel to) - 1 vertical bar G vertical bar + 2, then D'(G square H) <= 2 unless G square H = K-2(2). |
Year | Venue | Keywords |
|---|---|---|
2017 | ARS MATHEMATICA CONTEMPORANEA | Edge colouring,symmetry breaking,distinguishing index,Cartesian product of graphs |
Field | DocType | Volume |
Discrete mathematics,Graph,Natural number,Combinatorics,Symmetry breaking,Automorphism,Cartesian product,Cartesian product of graphs,Connectivity,Mathematics,Cartesian coordinate system | Journal | 12 |
Issue | ISSN | Citations |
1 | 1855-3966 | 2 |
PageRank | References | Authors |
0.41 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandra Gorzkowska | 1 | 2 | 2.11 |
| Rafał Kalinowski | 2 | 48 | 10.75 |
| Monika Pilśniak | 3 | 28 | 9.31 |