Partitioning the vertex set of G to make G[Box]H an efficient open domination graph

Tadeja Kraner Šumenjak (Avtor), Iztok Peterin (Avtor), Douglas F. Rall (Avtor), Aleksandra Tepeh (Avtor)

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