On distances in generalized Sierpiński graphs

DOI10.2298/AADM160802001EMaRDI QIDQ5155698zbMATH OpenOpenAlexFDO

Authors Alejandro Estrada-Moreno, Erick David Rodríguez-Bazan, Juan A. Rodríguez-Velázquez

Publication date 8 October 2021

Published in Applicable Analysis and Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00769

zbMATH Keywords

distances in graphsSierpiński graphsgeneralized Sierpiński graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12)

Abstract: In this paper we propose formulas for the distance between vertices of a generalized Sierpi'{n}ski graph $S(G,t)$ in terms of the distance between vertices of the base graph $G$. In particular, we deduce a recursive formula for the distance between an arbitrary vertex and an extreme vertex of $S(G,t)$, and we obtain a recursive formula for the distance between two arbitrary vertices of $S(G,t)$ when the base graph is triangle-free. From these recursive formulas, we provide algorithms to compute the distance between vertices of $S(G,t)$. In addition, we give an explicit formula for the diameter and radius of $S(G,t)$ when the base graph is a tree.

Recommendations

• On distances in Sierpiński graphs: almost-extreme vertices and metric dimension
• Recognizing generalized Sierpiński graphs
• On generalized Sierpiński graphs
• Distances in Sierpiński graphs and on the Sierpiński gasket
• Degree sequence of the generalized Sierpiński graph

Cites work

• 1-perfect codes in Sierpiński graphs
• A survey and classification of Sierpiński-type graphs
• An efficient algorithm to determine all shortest paths in Sierpiński graphs
• Graphs S(n, k) and a Variant of the Tower of Hanoi Problem
• Hamming dimension of a graph-the case of Sierpiński graphs
• New results on variants of covering codes in Sierpiński graphs
• On distances in Sierpiński graphs: almost-extreme vertices and metric dimension
• On generalized Sierpiński graphs
• On the Randić index of polymeric networks modelled by generalized Sierpiński graphs
• Shortest paths in Sierpiński graphs
• The Tower of Hanoi -- myths and maths. With a foreword by Ian Stewart
• The average eccentricity of Sierpiński graphs
• The strong metric dimension of generalized Sierpiński graphs with pendant vertices
• Total coloring for generalized Sierpiński graphs

Cited in

(14)

• Distances in Sierpiński graphs and on the Sierpiński gasket
• The Sierpiński product of graphs
• Metric properties of generalized Sierpiński graphs over stars
• Shortest paths in Sierpiński graphs
• Resolvability and convexity properties in the Sierpiński product of graphs
• Recognizing generalized Sierpiński graphs
• The Sierpiński domination number
• The strong metric dimension of generalized Sierpiński graphs with pendant vertices
• On generalized Sierpiński graphs
• A survey and classification of Sierpiński-type graphs
• Metric properties of Sierpiński triangle graphs
• The Graovac-Pisanski index of Sierpiński graphs
• Connectivity and some other properties of generalized Sierpiński graphs
• On distances in Sierpiński graphs: almost-extreme vertices and metric dimension

This page was built for publication: On distances in generalized Sierpiński graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5155698)