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

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2016
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17:004
COBISS:	17696601
ISSN:	1365-8050
Views:	606
Downloads:	118
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Particije grafa G, ki zagotavljajo učinkovito odprto dominiranost grafa G[Box]H
Secondary abstract:	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.
Secondary keywords:	učinkovita odprta dominacija;kartezični produkt;označevanje vozlišč;totalna dominacija;
URN:	URN:SI:UM:
Type (COBISS):	Scientific work
Pages:	15 str.
Volume:	ǂVol. ǂ18
Issue:	ǂno. ǂ3
Chronology:	2016
ID:	10847397