Rainbow domination in the lexicographic product of graphs

Kraner Šumenjak, Tadeja; Rall, Douglas F.; Tepeh, Aleksandra

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Rainbow domination in the lexicographic product of graphs
Authors:	ID Kraner Šumenjak, Tadeja (Author) ID Rall, Douglas F. (Author) ID Tepeh, Aleksandra (Author)
Files:	http://dx.doi.org/10.1016/j.dam.2013.03.011
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FKBV - Faculty of Agriculture and Life Sciences
Abstract:	Preslikava iz množice vozlišč grafa ▫$G$▫ v potenčno množico množice ▫${1,2,dots, k}$▫ se imenuje ▫$k$▫-mavrična dominantna funkcija, če za poljubno vozlišče ▫$v$▫ z lastnostjo ▫$f(v) = emptyset$▫ velja ▫${1,dots,k} = bigcup_{u in N(v)}f(u)$▫. Obravnavamo ▫$k$▫-mavrično dominantno število grafa ▫$G$▫, ▫$gamma_{rk}(G)$▫, ki je minimalna vsota (po vseh vozliščih grafa ▫$G$▫) moči podmnožic, ki so vozliščem dodeljena s ▫$k$▫-mavrično dominantno funkcijo. V članku se osredotočimo na 2-mavrično dominantno število leksikografskega produkta grafov in dokažemo natančno spodnjo in zgornjo mejo za to število. Dejansko pokažemo natančno vrednost za ▫$gamma_{r2}(G circ H)$▫, razen v primeru, ko je ▫$gamma_{r2}(H) = 3$▫ in obstaja taka minimalna 2-mavrična dominantna funkcija grafa $H$, ki nekemu vozlišču v grafu ▫$H$▫ dodeli oznako ▫${1,2}$▫.
Keywords:	dominacija, popolna dominacija, mavrična dominacija, leksikografski produkt, domination, total domination, rainbow domination, lexicographic product
Year of publishing:	2013
Number of pages:	str. 2133-2141
Numbering:	Vol. 161, iss. 13-14
PID:	20.500.12556/DKUM-51430
UDC:	519.17
ISSN on article:	0166-218X
COBISS.SI-ID:	3514668
NUK URN:	URN:SI:UM:DK:T5MCBN6Z
Publication date in DKUM:	10.07.2015
Views:	1508
Downloads:	118
Metadata:
Categories:	Misc.
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discrete applied mathematics
Shortened title:	Discrete appl. math.
Publisher:	Elsevier
ISSN:	0166-218X
COBISS.SI-ID:	25342464

Secondary language

Language:	English
Title:	Mavrična dominacija v leksikografskem produktu grafov
Abstract:	A ▫$k$▫-rainbow dominating function of a graph ▫$G$▫ is a map ▫$f$▫ from ▫$V(G)$▫ to the set of all subsets of ▫${1,2,dots,k}$▫ such that ▫${1,dots,k} = bigcup_{u in N(v)}f(u)$▫ whenever ▫$v$▫ is a vertex with ▫$f(v) = emptyset$▫. The ▫$k$▫-rainbow domination number of ▫$G$▫ is the invariant ▫$gamma_{rk}(G)$▫, which is the minimum sum (over all the vertices of ▫$G$▫) of the cardinalities of the subsets assigned by a ▫$k$▫-rainbow dominating function. We focus on the 2-rainbow domination number of the lexicographic product of graphs and prove sharp lower and upper bounds for this number. In fact, we prove the exact value of ▫$gamma_{r2}(G circ H)$▫ in terms of domination invariants of ▫$G$▫ except for the case when ▫$gamma_{r2}(H) = 3$▫ and there exists a minimum 2-rainbow dominating function of ▫$H$▫ such that there is a vertex in ▫$H$▫ with the label ▫${1,2}$▫.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back