Gašper Mekiš (Author)

Abstract

An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$\gamma(\times_{i=1}^t K_{n_i} \ge t+1$▫, ▫$t \ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$\gamma(G \times H) \ge \gamma(G) + \gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$\gamma_t(G \times H) = \gamma(G) + \gamma(H) - 1$▫. Some additional parallels with the total domination number are made.

Keywords

matematika;teorija grafov;dominacijska množica;dominacijsko število;celotna dominacijska množica;celotno dominacijsko število;direktni produkt grafov;poln graf;mathematics;graph theory;dominating set;domination number;total dominating set;total domination number;direct product graphs;complete graphs;

Data

Language: English
Year of publishing:
Typology: 0 - Not set
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17
COBISS: 15246425 Link will open in a new window
ISSN: 1318-4865
Views: 50
Downloads: 6
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary keywords: matematika;teorija grafov;dominacijska množica;dominacijsko število;celotna dominacijska množica;celotno dominacijsko število;direktni produkt grafov;poln graf;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 1-15
Volume: ǂVol. ǂ47
Issue: ǂšt. ǂ1100
Chronology: 2009
ID: 1474419