Povzetek

A dominating set ▫$D$▫ gor a graph ▫$G$▫ is a subset ▫$V(G)$▫ such that any vertex in ▫$V(G)-D$▫ has a neighbor in ▫$D$▫, and a domination number ▫$\gamma(G)$▫ is the size of a minimum dominating set for ▫$G$▫. For the Cartesian product ▫$G \Box H$▫ Vizing's conjecture states that ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫ for every pair of graphs ▫$G,H$▫. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when ▫$\gamma(G) = \gamma(H) = 3$▫.

Ključne besede

matematika;teorija grafov;graf;kartezični produkt;dominantno število;mathematics;graph theory;graph;Cartesian product;domination number;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FKBV - Fakulteta za kmetijstvo in biosistemske vede
UDK: 519.17
COBISS: 11010137 Povezava se bo odprla v novem oknu
ISSN: 1234-3099
Št. ogledov: 912
Št. prenosov: 87
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: O Vizingovi domnevi
Sekundarni povzetek: Dominirajoča množica ▫$D$▫ grafa ▫$G$▫ je taka podmnožica množice ▫$V(G)$▫, za katero ima vsaka točka iz množice ▫$V(G)-D$▫ kako sosedo v ▫$D$▫; dominantno število ▫$\gamma(G)$▫ pa je velikost najmanjše dominirajoče množice grafa ▫$G$▫. Za kartezični produkt grafov ▫$G \Box H$▫ Vizingova domneva trdi, da je ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫, kjer sta ▫$G$▫ in ▫$H$▫ poljubna grafa. V članku vpeljemo nov koncept, ki posploši običajno dominacijo grafov in dokažemo, da domneva drži v promeru, ko je ▫$\gamma(G) = \gamma(H) = 3$▫.
Sekundarne ključne besede: matematika;teorija grafov;graf;kartezični produkt;dominantno število;
URN: URN:SI:UM:
Vrsta dela (COBISS): Znanstveno delo
Strani: str. 5-11
Letnik: ǂVol. ǂ21
Zvezek: ǂno. ǂ1
Čas izdaje: 2001
ID: 9595946
Priporočena dela:
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu