Gašper Mekiš (Avtor)

Povzetek

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.

Ključne besede

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 0 - Ni določena
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 15246425 Povezava se bo odprla v novem oknu
ISSN: 1318-4865
Št. ogledov: 50
Št. prenosov: 6
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarne ključne besede: matematika;teorija grafov;dominacijska množica;dominacijsko število;celotna dominacijska množica;celotno dominacijsko število;direktni produkt grafov;poln graf;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 1-15
Letnik: ǂVol. ǂ47
Zvezek: ǂšt. ǂ1100
Čas izdaje: 2009
ID: 1474419