Janja Jerebic (Avtor), Sandi Klavžar (Avtor)

Povzetek

Označitev grafa ▫$G$▫ je razlikovalna, če jo ohranja le trivialni avtomorfizem grafa ▫$G$▫. Razlikovalno kromatično število grafa ▫$G$▫ je najmanjše naravno število, za katero obstaja razlikovalna označitev grafa, ki je hkrati tudi dobro barvanje. Za vse ▫$k$▫ in ▫$n$▫ je določeno razlikovalno kromatično število kartezičnih produktov ▫$K_k\Box K_n$▫. V večini primerov je enako kromatičnemu številu, kar med drugim odgovori na vprašanje Choia, Hartkeja and Kaula, ali obstajajo še kakšni drugi grafi, za katere velja enakost.

Ključne besede

teorija grafov;razlikovalno kromatično število;grafovski avtomorfizem;kartezični produkt grafov;graph theory;distinguishing chromatic number;graph automorphism;Cartesian product of graphs;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 0 - Ni določena
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 14609753 Povezava se bo odprla v novem oknu
ISSN: 1318-4865
Št. ogledov: 750
Št. prenosov: 72
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: Neznan jezik
Sekundarni naslov: Razlikovalno kromatično število kartezičnega produkta dveh polnih grafov
Sekundarni povzetek: A labeling of a graph ▫$G$▫ is distinguishing if it is only preserved by the trivial automorphism of ▫$G$▫. The distinguishing chromatic number of ▫$G$▫ is the smallest integer ▫$k$▫ such that ▫$G$▫ has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product $K_k\Box K_n$ is determined for all ▫$k$▫ and ▫$n$▫. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.
Sekundarne ključne besede: teorija grafov;razlikovalno kromatično število;grafovski avtomorfizem;kartezični produkt grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 1-11
Letnik: ǂVol. ǂ46
Zvezek: ǂšt. ǂ1045
Čas izdaje: 2008
ID: 67278