Boštjan Brešar (Avtor), Csilla Bujtás (Avtor), Tanja Gologranc (Avtor), Sandi Klavžar (Avtor), Gašper Košmrlj (Avtor), Tilen Marc (Avtor), Balázs Patkós (Avtor), Zsolt Tuza (Avtor), Máté Vizer (Avtor)

Povzetek

Najdaljše zaporedje ▫$(v_1,\ldots,v_k)$▫ vozlišč grafa ▫$G$▫ je Grundyjevo celotno dominantno zaporedje, če za vse ▫$i$▫ velja ▫$N(v_i) \setminus \bigcup_{j=1}^{i-1}N(v_j)\not=\emptyset$▫. Dolžina ▫$k$▫ takega zaporedja je Grundyjevo celotno dominantno število grafa ▫$G$▫ in se uznačuje z ▫$\gamma_{gr}^{t}(G)$▫. V tem članku je Grundyjevo celotno dominantno števijo študirano na štirih standardnih produktih grafov. Za direktni produkt je dokazano, da velja ▫$\gamma_{gr}^t(G\times H) \geq \gamma_{gr}^t(G)\gamma_{gr}^t(H)$▫. Postavljena je domneva, da vedno velja enakost. Domneva je dokazana v več posebnih primerih. Za leksikografski produkt je vrednost ▫$\gamma_{gr}^{t}(G\circ H)$▫ izražena z ustreznimi invariantami faktorjev, poiskanih je tudi nekaj eksplicitnih formul. Za krepki produkt so dokazane spodnje meja za ▫$\gamma_{gr}^{t}(G \boxtimes H)$▫ in tudi zgornje meje za produkte poti in ciklov. Za kartezični produkt pa so dokazane spodnje in zgornje meje za primer, ko so faktorji poti ali cikli.

Ključne besede

celotna dominacija;Grundyjevo celotno dominantno število;produkt grafov;total domination;Grundy total domination number;graph product;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: Technical University Press
UDK: 519.17
COBISS: 36071939 Povezava se bo odprla v novem oknu
ISSN: 1234-3099
Št. ogledov: 36
Št. prenosov: 0
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 Grundyjevem celotnem dominantnem številu produktih grafov
Sekundarni povzetek: A longest sequence ▫$(v_1,\ldots,v_k)$▫ of vertices of a graph ▫$G$▫ is a Grundy total dominating sequence of ▫$G$▫ if for all ▫$i$▫, ▫$N(v_i) \setminus \bigcup_{j=1}^{i-1}N(v_j)\not=\emptyset$▫. The length ▫$k$▫ of the sequence is called the Grundy total domination number of ▫$G$▫ and denoted ▫$\gamma_{gr}^{t}(G)$▫. In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that ▫$\gamma_{gr}^t (G\times H) \geq \gamma_{gr}^t(G)\gamma_{gr}^t(H)$▫, conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express ▫$\gamma_{gr}^{t}(G\circ H)$▫ in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on ▫$\gamma_{gr}^{t}(G \boxtimes H)$▫ are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Sekundarne ključne besede: celotna dominacija;Grundyjevo celotno dominantno število;produkt grafov;
Vrsta dela (COBISS): Znanstveno delo
Strani: str. 225-247
Letnik: ǂVol. ǂ41
Zvezek: ǂno. ǂ1
Čas izdaje: 2021
DOI: 10.7151/dmgt.2184
ID: 24676119