Wilfried Imrich (Avtor), Sandi Klavžar (Avtor)

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:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM PEF - Pedagoška fakulteta
UDK: 519.17:512.54
COBISS: 14075481 Povezava se bo odprla v novem oknu
ISSN: 0364-9024
Št. ogledov: 42
Št. prenosov: 23
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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