Povzetek

Graf imenujemo učinkovito odprto dominiran, če zanj obstaja podmnožica vozlišč, katerih odprte okolice porajajo particijo množice vseh vozlišč. Karakteriziramo take grafe ▫$G$▫, da je kartezični produkt ▫$G \Box H$▫ učinkovito odprto dominiran v primerih, ko je ▫$H$▫ poln graf na vsaj treh vozliščih ali poln dvodelni graf. V obeh primerih karakterizacija temelji na obstoju določenega tipa šibke particije množice ▫$V(G)$▫. Za drevesa je, ko je ▫$H$▫ poln graf na vsaj treh vozliščih, karakterizacija konstrukcijska. Prav tako med kartezičnimi produkti ▫$G \Box H$▫ karakteriziramo posebne tipe učinkovito odprto dominiranih grafov, ko je ǂ$H$ǂ 5-cikel ali 4-cikel.

Ključne besede

učinkovita odprta dominacija;kartezični produkt;označevanje vozlišč;totalna dominacija;efficient open domination;Cartesian product;vertex labeling;total domination;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK: 519.17:004
COBISS: 17696601 Povezava se bo odprla v novem oknu
ISSN: 1365-8050
Št. ogledov: 606
Št. prenosov: 118
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: Particije grafa G, ki zagotavljajo učinkovito odprto dominiranost grafa G[Box]H
Sekundarni povzetek: A graph is an efficient open domination graph if there exists a subset of vertices whose open neighborhoods partition its vertex set. We characterize those graphs ▫$G$▫ for which the Cartesian product ▫$G \Box H$▫ is an efficient open domination graph when ▫$H$▫ is a complete graph of order at least 3 or a complete bipartite graph. The characterization is based on the existence of a certain type of weak partition of ▫$V(G)$▫. For the class of trees when ▫$H$▫ is complete of order at least 3, the characterization is constructive. In addition, a special type of efficient open domination graph is characterized among Cartesian products ▫$G \Box H$▫ when ▫$H$▫ is a 5-cycle or a 4-cycle.
Sekundarne ključne besede: učinkovita odprta dominacija;kartezični produkt;označevanje vozlišč;totalna dominacija;
URN: URN:SI:UM:
Vrsta dela (COBISS): Znanstveno delo
Strani: 15 str.
Letnik: ǂVol. ǂ18
Zvezek: ǂno. ǂ3
Čas izdaje: 2016
ID: 10847397
Priporočena dela:
, ni podatka o podnaslovu
, na študijskem programu 2. stopnje Matematika
, ni podatka o podnaslovu