The distinguishing number of Cartesian products of complete graphs

Imrich, Wilfried; Jerebic, Janja; Klavžar, Sandi

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	The distinguishing number of Cartesian products of complete graphs
Avtorji:	ID Imrich, Wilfried (Avtor) ID Jerebic, Janja (Avtor) ID Klavžar, Sandi (Avtor)
Datoteke:	http://dx.doi.org/doi:10.1016/j.ejc.2007.11.018
Jezik:	Angleški jezik
Vrsta gradiva:	Članek v reviji
Tipologija:	1.08 - Objavljeni znanstveni prispevek na konferenci
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	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, mathematics, graph theory, distingushing number, complete graphs, Cartesian product
Status publikacije:	Objavljeno
Verzija publikacije:	Objavljena publikacija
Leto izida:	2008
Št. strani:	Str. 922-929
PID:	20.500.12556/DKUM-51670
UDK:	519.17
COBISS.SI-ID:	14626905
ISSN pri članku:	0195-6698
NUK URN:	URN:SI:UM:DK:HHXKS69U
Datum objave v DKUM:	10.07.2015
Število ogledov:	1121
Število prenosov:	78
Metapodatki:
Področja:	Ostalo
:	IMRICH, Wilfried, JEREBIC, Janja in KLAVŽAR, Sandi, 2008, The distinguishing number of Cartesian products of complete graphs. V : Homomorphisms: Structure and Highlights [na spletu]. Objavljeni znanstveni prispevek na konferenci. 2008. p. 922–929. [Dostopano 27 marec 2025]. Pridobljeno s: http://dx.doi.org/doi:10.1016/j.ejc.2007.11.018 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

The preparation and characterization of low-temperature foams based on the alkali activation of waste stone wool
Preparation of façade panels based on alkali-activated waste mineral wool, their characterization and durability aspects
Potential of green ceramics waste for alkali activated foams
Influence of microwaves in the early stage of alkali activation on the mechanical strength of alkali-activated materials
Pilot production of façade panels

Podobna dela iz ostalih repozitorijev:

Ni podobnih del

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del zbornika

Naslov:	Homomorphisms: Structure and Highlights
COBISS.SI-ID:	14626649

Gradivo je del revije

Naslov:	European journal of combinatorics
Skrajšan naslov:	Eur. j. comb.
Založnik:	Academic Press
ISSN:	0195-6698
COBISS.SI-ID:	25427968

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Razlikovalno število kartezičnih produktov polnih grafov
Opis:	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.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj