On integer domination in graphs and Vizing-like problems

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2006
Typology:	1.01 - Original Scientific Article
Organization:	UM PEF - Faculty of Education
UDC:	519.17
COBISS:	14099545
ISSN:	1027-5487
Views:	834
Downloads:	56
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	O celoštevilski dominaciji v grafih in problemih Vizingovega tipa
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;▫$\{k\}$▫-dominantna funkcija;celoštevilska dominacija;Vizingova domneva;kartezični produkt grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str.1317-1328
Volume:	ǂVol. ǂ10
Issue:	ǂno. ǂ5
Chronology:	2006
ID:	1472852