Povzetek
Razlikovalno število ▫$D(G)$▫ grafa je najmanjše celo število ▫$d$▫, za katero obstaja taka ▫$d$▫-označitev točk grafa ▫$G$▫, da je ne ohranja noben avtomorfizem grafa ▫$G$▫. Dokažemo, da je razlikovalno število kvadrata in višjih potenc povezanega grafa ▫$G \ne K_2, K_3$▫, glede na kartezični produkt, vedno enako 2. Ta rezultat je močnejši od rezultatov Albertsona [Electron J Combin, 12 (2005), N17] za potence pra-grafov in tudi od rezultatov Klavžarja and Zhuja [European J. Combin, v tisku]. Bolj splošno, dokažemo tudi, da je ▫$(G \Box H) = 2$▫, če sta ▫$G$▫ in ▫$H$▫ relativno tuja grafa in je ▫$|H| \le |G| < 2^{|H|} - |H|$▫. Pod podobnimi pogoji veljajo sorodni rezultati tudi za potence grafov glede na krepki in direktni produkt grafov.
Ključne besede
matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov;mathematics;graph theory;distingushing number;graph automorphism;products of graphs;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2006 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM PEF - Pedagoška fakulteta |
UDK: |
519.17:512.54 |
COBISS: |
14075481
|
ISSN: |
0364-9024 |
Št. ogledov: |
42 |
Št. prenosov: |
23 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Slovenski jezik |
Sekundarni naslov: |
Razlikovanje kartezičnih potenc grafov |
Sekundarni povzetek: |
The distinguishing number ▫$D(G)$▫ of a graph is the least integer ▫$d$▫ such that there is a ▫$d$▫-labeling of the vertices of ▫$G$▫ that is not preserved by any nontrivial automorphism of ▫$G$▫. We show that the distinguishing number of the square and higher powers of a connected graph ▫$G \ne K_2, K_3$▫ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 (2005), N17] on powers of prime graphs, and results of Klavžar and Zhu [Eu J Combin, to appear]. More generally, we also prove thatd ▫$(G \Box H) = 2$▫ if ▫$G$▫ and ▫$H$▫ are relatively prime and ▫$|H| \le |G| < 2^{|H|} - |H|$▫. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. |
Sekundarne ključne besede: |
matematika;teorija grafov;razlikovalno število;grafovski avtomorfizem;produkti grafov; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 250-260 |
Letnik: |
ǂVol. ǂ53 |
Zvezek: |
ǂiss. ǂ3 |
Čas izdaje: |
2006 |
ID: |
1472826 |