On integer domination in graphs and Vizing-like problems

Boštjan Brešar (Avtor), Michael A. Henning (Avtor), Sandi Klavžar (Avtor)

Povzetek

Nadaljujemo študij ▫$\{k\}$▫-dominantnih funkcij v grafih (ali, kot bomo tudi rekli, celoštevilske dominacije), ki so jo začeli Domke, Hedetniemi, Laskar in Fricke. Za celo število ▫$k \ge 1$▫ je funkcija ▫$f: V(G) \to \{0,1,...,k\}$▫, definirana na točkah grafa ▫$G$▫, ▫$\{k\}$▫-dominantna funkcija, če je vsota funkcijskih vrednosti na vsaki zaprti okolici vsaj ▫$k$▫. Teža ▫$\{k\}$▫-dominantne funkcije je vsota funkcijskih vrednosti po vseh točkah. ▫$\{k\}$▫-dominantno število grafa ▫$G$▫ je najmanjša teža ▫$\{k\}$▫-dominantne funkcije na ▫$G$▫. Obravnavamo ▫$\{k\}$▫-dominantno število kartezičnega produkta grafov, predvsem probleme povezane s slavno Vizingovo domnevo. Študirana je tudi povezava med ▫$\{k\}$▫-dominantnim številom in drugimi tipi dominacijskih parametrov.

Ključne besede

matematika;teorija grafov;▫$\{k\}$▫-dominantna funkcija;celoštevilska dominacija;Vizingova domneva;kartezični produkt grafov;mathematics;graph theory;▫$\{k}$▫-dominating function;integer domination;Vizing's conjecture;Cartesian product;

Podatki

Jezik:	Angleški jezik
Leto izida:	2006
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM PEF - Pedagoška fakulteta
UDK:	519.17
COBISS:	14099545
ISSN:	1027-5487
Št. ogledov:	834
Št. prenosov:	56
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	O celoštevilski dominaciji v grafih in problemih Vizingovega tipa
Sekundarni povzetek:	We continue the study of ▫$\{k\}$▫-dominating functions in graphs (or integer domination as we shall also say) started by Domke, Hedetniemi, Laskar, and Fricke. For ▫$k \ge 1$▫ an integer, a function ▫$f: V (G) \to \{0,1,...,k\}$▫ defined on the vertices of a graph ▫$G$▫ is called a ▫$\{k\}$▫-dominating function if the sum of its function values over any closed neighborhood is at least k. ▫$T$▫he weight of a ▫$\{k\}$▫-dominating function is the sum of its function values over all vertices. The ▫$\{k\}$▫-domination number of ▫$G$▫ is the minimum weightof a ▫$\{k\}$▫-dominating function of ▫$G$▫. We study the ▫$\{k\}$▫-domination number on the Cartesian product of graphs, mostly on problems related to the famous Vizing¡ s conjecture. A connection between the ▫$\{k\}$▫-domination number and other domination type parameters is also studied.
Sekundarne ključne besede:	matematika;teorija grafov;▫$\{k\}$▫-dominantna funkcija;celoštevilska dominacija;Vizingova domneva;kartezični produkt grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str.1317-1328
Letnik:	ǂVol. ǂ10
Zvezek:	ǂno. ǂ5
Čas izdaje:	2006
ID:	1472852