Szczegóły publikacji
Opis bibliograficzny
The distinguishing index of the Cartesian product of finite graphs / Aleksandra GORZKOWSKA, Rafał KALINOWSKI, Monika PILŚNIAK // Ars Mathematica Contemporanea ; ISSN 1855-3966. — 2017 — vol. 12 no. 1, s. 77–87. — Bibliogr. s. 86–87, Abstr. — Publikacja dostępna online od: 2016-05-20
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 97986 |
|---|---|
| Data dodania do BaDAP | 2016-06-10 |
| Tekst źródłowy | URL |
| DOI | 10.26493/1855-3974.909.0e1 |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Ars Mathematica Contemporanea |
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ʹ(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.
