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: |
2016 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
UDK: |
519.17:004 |
COBISS: |
17696601
|
ISSN: |
1365-8050 |
Št. ogledov: |
606 |
Št. prenosov: |
118 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
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 |