Michael A. Henning (Avtor), Sandi Klavžar (Avtor), Ismael G. Yero (Avtor)

Povzetek

Naj bosta podana grafa ▫$G$▫ in ▫$H$▫ in funkcija ▫$f \colon V(G)\rightarrow V(H)$▫. Sierpinskijev produkt ▫$G$▫ in ▫$H$▫ glede na ▫$f$▫, označen z ▫$G \otimes _f H$▫, je definiran kot graf na množici vozlišč ▫$V(G)\times V(H)$▫, sestavljen iz ▫$|V(G)|$▫ kopij ▫$H$▫; za vsako povezavo ▫$gg'$▫ v ▫$G$▫ obstaja povezava med kopijama ▫$gH$▫ in ▫$g'H$▫ v ▫$H$▫, povezanima z vozliščema ▫$g$▫ in ▫$g'$▫ v ▫$G$▫, v obliki ▫$(g,f(g'))(g',f(g))$▫. Določeni sta Sierpinskijeva metrična dimenzija zgornja Sierpinskijeva metrična dimenzija dveh grafov. Določene so zaprte formule za Sierpinskijeve produkte dreves in za Sierpinskijeve produkte dveh ciklov, kjer je drugi faktor trikotnik. Dokažemo tudi, da so sloji glede na drugi faktor v grafu Sierpinskijevega produkta konveksne.

Ključne besede

Sierpinskijev produkt grafov;metrična dimenzija;drevesa;konveksni podgrafi;Sierpiński product of graphs;metric dimension;trees;convex subgraph;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
UDK: 519.17
COBISS: 172901379 Povezava se bo odprla v novem oknu
ISSN: 1660-5446
Št. ogledov: 18
Št. prenosov: 3
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: Solventnost in lastnosti konveksnosti v Sierpinskijevih produktih grafov
Sekundarni povzetek: Let ▫$G$▫ and ▫$H$▫ be graphs and let ▫$f \colon V(G)\rightarrow V(H)$▫ be a function. The Sierpiński product of ▫$G$▫ and ▫$H$▫ with respect to ▫$f$▫, denoted by ▫$G \otimes _f H$▫, is defined as the graph on the vertex set ▫$V(G)\times V(H)$▫, consisting of ▫$|V(G)|$▫ copies of ▫$H$▫; for every edge ▫$gg'$▫ of ▫$G$▫ there is an edge between copies ▫$gH$▫ and ▫$g'H$▫ of ▫$H$▫ associated with the vertices ▫$g$▫ and ▫$g'$▫ of ▫$G$▫, respectively, of the form ▫$(g,f(g'))(g',f(g))$▫. The Sierpiński metric dimension and the upper Sierpiński metric dimension of two graphs are determined. Closed formulas are determined for Sierpiński products of trees, and for Sierpiński products of two cycles where the second factor is a triangle. We also prove that the layers with respect to the second factor in a Sierpiński product graph are convex.
Sekundarne ključne besede: Sierpinskijev produkt grafov;metrična dimenzija;drevesa;konveksni podgrafi;
Vrsta dela (COBISS): Članek v reviji
Strani: 17 str.
Letnik: ǂVol. ǂ21
Zvezek: ǂiss. ǂ1, article no. 3
Čas izdaje: Jan. 2024
DOI: 10.1007/s00009-023-02544-6
ID: 21327447