Geodesic
The distinguishing index of the Cartesian product of finite graphs
Ars mathematica contemporanea, Tome 12 (2017) no. 1, pp. 77-87 Cet article a éte moissonné depuis la source Ars Mathematica Contemporanea website

Voir la notice de l'article

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ʹ(K22) = 3. We also prove that if G and H are connected graphs that satisfy the relation 2 ≤ ∣G∣ ≤ ∣H∣ ≤ 2^∣G∣(2^∣∣G∣∣ − 1) − ∣G∣ + 2, then Dʹ(G□ H) ≤ 2 unless G□ H = K22.
DOI : 10.26493/1855-3974.909.0e1
Keywords: Edge colouring, symmetry breaking, distinguishing index, Cartesian product of graphs 
@article{10_26493_1855_3974_909_0e1,
     author = {Aleksandra Gorzkowska and Rafa{\l} Kalinowski and Monika Pil\'sniak},
     title = {
		{The} distinguishing index of the {Cartesian} product of finite graphs
	},
     journal = {Ars mathematica contemporanea},
     pages = {77--87},
     year = {2017},
     volume = {12},
     number = {1},
     doi = {10.26493/1855-3974.909.0e1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.909.0e1/}
}
TY  - JOUR
AU  - Aleksandra Gorzkowska
AU  - Rafał Kalinowski
AU  - Monika Pilśniak
TI  - The distinguishing index of the Cartesian product of finite graphs
	
JO  - Ars mathematica contemporanea
PY  - 2017
SP  - 77
EP  - 87
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.909.0e1/
DO  - 10.26493/1855-3974.909.0e1
LA  - en
ID  - 10_26493_1855_3974_909_0e1
ER  - 
%0 Journal Article
%A Aleksandra Gorzkowska
%A Rafał Kalinowski
%A Monika Pilśniak
%T The distinguishing index of the Cartesian product of finite graphs
	
%J Ars mathematica contemporanea
%D 2017
%P 77-87
%V 12
%N 1
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.909.0e1/
%R 10.26493/1855-3974.909.0e1
%G en
%F 10_26493_1855_3974_909_0e1
Aleksandra Gorzkowska; Rafał Kalinowski; Monika Pilśniak. The distinguishing index of the Cartesian product of finite graphs. Ars mathematica contemporanea, Tome 12 (2017) no. 1, pp. 77-87. doi: 10.26493/1855-3974.909.0e1

Cité par Sources :