Processing math: 100%
| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document Help

Title:Dominating direct products of graphs
Authors:ID Brešar, Boštjan (Author)
ID Klavžar, Sandi (Author)
ID Rall, Douglas F. (Author)
Files:URL http://dx.doi.org/10.1016/j.disc.2006.09.013
 
Language:English
Work type:Not categorized
Typology:1.01 - Original Scientific Article
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:Dokazana je zgornja meja za dominantno število direktnega produkta grafov. V posebnem primeru iz meje sledi, da za poljubna grafa G in H velja gamma(GtimesH)le3gamma(G)gamma(H). Konstruirani so grafi s poljubno velikimi dominantnimi števili, za katere je ta meja dosežena. Za gornje dominantno število dokažemo, da velja Gamma(GtimesH)geGamma(G)Gamma(H), s čimer je potrjena domneva iz [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Nazadnje za dominacijo v parih direktnih produktov dokažemo, da za poljubna grafa G in H velja gammarmpr(GtimesH)legammarmpr(G)gammarmpr(H). Predstavimo tudi neskončne družine grafov, pri katerih je ta meja dosežena.
Keywords:matematika, teorija grafov, dominacija, dominacija v parih, gornja dominacija, kartezični produkt grafov, mathematics, graph theory, domination, paired-domination, upper domination, direct product
Year of publishing:2007
Number of pages:str. 1636-1642
Numbering:Vol. 307, iss. 13
PID:20.500.12556/DKUM-51595 New window
UDC:519.17
ISSN on article:0012-365X
COBISS.SI-ID:14286937 New window
NUK URN:URN:SI:UM:DK:6FX9XHHM
Publication date in DKUM:10.07.2015
Views:1240
Downloads:98
Metadata:XML DC-XML DC-RDF
Categories:Misc.
:
BREŠAR, Boštjan, KLAVŽAR, Sandi and RALL, Douglas F., 2007, Dominating direct products of graphs. Discrete mathematics [online]. 2007. Vol. 307, no. 13, p. 1636–1642. [Accessed 21 January 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2006.09.013
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and 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 mathematics
Shortened title:Discrete math.
Publisher:North-Holland
ISSN:0012-365X
COBISS.SI-ID:1118479 New window

Secondary language

Language:Unknown
Title:Dominiranje direktnih produktov grafov
Abstract:An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, gamma(GtimesH)le3gamma(G)gamma(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Gamma(GtimesH)geGamma(G)Gamma(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that gammarmpr(GtimesH)legammarmpr(G)gammarmpr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica