On distances in generalized Sierpiński graphs

DOI10.2298/AADM160802001EzbMATH Open1488.05155arXiv1608.00769OpenAlexW2963957200MaRDI QIDQ5155698FDOQ5155698

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)

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.

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

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

zbMATH Keywords

distances in graphsSierpiński graphsgeneralized Sierpiński graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

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

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)