Boštjan Brešar (Avtor), Sandi Klavžar (Avtor), Douglas F. Rall (Avtor)

Povzetek

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 (G \times H) \le 3\gamma(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(G \times H) \ge \Gamma(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 ▫$\gamma_{\rm{pr}}(G \times H) \le \gamma_{\rm{pr}} (G)\gamma_{\rm{pr}}(H)$▫. Predstavimo tudi neskončne družine grafov, pri katerih je ta meja dosežena.

Ključne besede

matematika;teorija grafov;dominacija;dominacija v parih;gornja dominacija;kartezični produkt grafov;mathematics;graph theory;domination;paired-domination;upper domination;direct product;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 14286937 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 37
Št. prenosov: 22
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: Slovenski jezik
Sekundarni naslov: Dominiranje direktnih produktov grafov
Sekundarni povzetek: 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 (G \times H) \le 3\gamma(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(G \times H) \ge \Gamma(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 ▫$\gamma_{\rm{pr}}(G \times H) \le \gamma_{\rm{pr}}(G)\gamma_{\rm{pr}}(H)$▫ for arbitrary graphs ▫$G$▫ and ▫$H$▫, and also present some infinite families of graphs that attain this bound.
Sekundarne ključne besede: matematika;teorija grafov;dominacija;dominacija v parih;gornja dominacija;kartezični produkt grafov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 1636-1642
Letnik: ǂVol. ǂ307
Zvezek: ǂiss. ǂ13
Čas izdaje: 2007
ID: 1473063