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

Abstract

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.

Keywords

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

Data

Language: English
Year of publishing:
Typology: 1.08 - Published Scientific Conference Contribution
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17
COBISS: 14626905 Link will open in a new window
ISSN: 0195-6698
Views: 1121
Downloads: 75
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: Razlikovalno število kartezičnih produktov polnih grafov
Secondary abstract: 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.
Secondary keywords: Matematika;Teorija grafov;
URN: URN:SI:UM:
Type (COBISS): Article
Pages: Str. 922-929
DOI: 10.1016/j.ejc.2007.11.018
ID: 1473512