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

Povzetek

Razlikovalno število ▫$D(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$d$▫, tako da ▫$G$▫ premore označitev z ▫$d$▫ oznakami, ki jo ohranja le trivialni avtomorfizem. Dokažemo, da lahko kartezične produkte relativno tujih grafov, katerih velikosti se ne razlikujejo preveč, razlikujemo z majhnim številom barv. Za vse ▫$k$▫ in ▫$n$▫ določimo razlikovalno število kartezičnega produkta ▫$K_k \square K_k$▫ in sicer bodisi eksplicitno, bodisi s kratko rekurzijo. Vpeljemo tudi stolpčno-invariantne množice vektorjev in dokažemo preklopno lemo, ki igra ključno vlogo v dokazih.

Ključne besede

matematika;teorija grafov;razlikovalno število;polni grafi;kartezični produkt grafov;ne zaključna dela;mathematics;graph theory;distingushing number;complete graphs;Cartesian product;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 14626905 Povezava se bo odprla v novem oknu
ISSN: 0195-6698
Št. ogledov: 1121
Št. prenosov: 75
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: Razlikovalno število kartezičnih produktov polnih grafov
Sekundarni povzetek: The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least integer ▫$d$▫ such that ▫$G$▫ has a labeling with ▫$d$▫ labels that is preserved only by a trivial automorphism. We prove that Cartesian products of relatively prime graphs whose sizes do not differ too much can be distinguished with a small number of colors. We determine the distinguishing number of the Cartesian product ▫$K_k \square K_k$▫ forall ▫$k$▫ and ▫$n$▫, either explicitly or by a short recursion. We also introduce column-invariant sets of vectors and prove a switching lemma that plays a key role in the proofs.
Sekundarne ključne besede: Matematika;Teorija grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Članek v reviji
Strani: Str. 922-929
DOI: 10.1016/j.ejc.2007.11.018
ID: 1473512