Resolvability and convexity properties in the Sierpiński product of graphs

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

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2024
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	172901379
ISSN:	1660-5446
Views:	18
Downloads:	3
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Solventnost in lastnosti konveksnosti v Sierpinskijevih produktih grafov
Secondary abstract:	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.
Secondary keywords:	Sierpinskijev produkt grafov;metrična dimenzija;drevesa;konveksni podgrafi;
Type (COBISS):	Article
Pages:	17 str.
Volume:	ǂVol. ǂ21
Issue:	ǂiss. ǂ1, article no. 3
Chronology:	Jan. 2024
DOI:	10.1007/s00009-023-02544-6
ID:	21327447