Abstract
A set Q⊆V is a hub set of a graph G=(V,E) if, for every pair of vertices u,v∈V∖Q, there exists a path from u to v such that all intermediate vertices are in Q. The hub number of G is the minimum size of a hub set in G. This paper derives the hub numbers of Sierpiński-like graphs including: Sierpiński graphs, extended Sierpiński graphs, and Sierpiński gasket graphs. Meanwhile, the corresponding minimum hub sets are also obtained.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Grauman, T., Hartke, S.G., Jobson, A., Kinnersley, B., West, D.B., Wiglesworth, L., Worah, P., Wu, H.: The hub number of a graph. Inf. Process. Lett. 108, 226–228 (2008)
Hinz, A.M.: Pascal’s triangle and the Tower of Hanoi. Am. Math. Mon. 99, 538–544 (1992)
Hinz, A.M., Schief, A.: The average distance on the Sierpiński gasket. Probab. Theory Relat. Fields 87, 129–138 (1990)
Hinz, A.M., Klavžar, S., Milutinović, U., Parisse, D., Petr, C.: Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence. Eur. J. Combin. 26, 693–708 (2005)
Jakovac, M., Klavžar, S.: Vertex-, edge- and total-colorings of Sierpiński-like graphs. Discrete Math. 309, 1548–1556 (2009)
Kaimanovich, V.A.: Random walks on Sierpiński graphs: Hyperbolicity and stochastic homogenization. In: Grabner, P., Woess, W. (eds.): Fractals in Graz 2001, pp. 145–183. Birkhäuser, Basel (2003)
Klavžar, S.: Coloring Sierpiński graphs and Sierpiński gasket graphs. Taiwan. J. Math. 12, 513–522 (2008)
Klavžar, S., Milutinović, U.: Graphs S(n,k) and a variant of the Tower of Hanoi problem. Czechoslovak Math. J. 47, 95–104 (1997)
Klavžar, S., Mohar, B.: Crossing numbers of Sierpiński-like graphs. J. Graph Theory 50, 186–198 (2005)
Klavžar, S., Milutinović, U., Petr, C.: 1-perfect codes in Sierpiński graphs. Bull. Aust. Math. Soc. 66, 369–384 (2002)
Klix, F., Rautenstrauch-Goede, K.: Struktur-und Komponentenanalyse von Problemlösungsprozessen. Z. Psychol. 174, 167–193 (1967)
Parisse, D.: On some metric properties of the Sierpiński graphs S(n,k). Ars Comb. 90, 145–160 (2009)
Romik, D.: Shortest paths in the Tower of Hanoi graph and finite automata. SIAM J. Discrete Math. 20, 610–622 (2006)
Sydow, H.: Zur metrischen Erfasung von subjektiven Problemzuständen und zu deren Veränderung im Denkprozes. Z. Psychol. 177, 145–198 (1970)
Teguia, A.M., Godbole, A.P.: Sierpiński gasket graphs and some of their properties. Australasian J. Combin. 35, 181–192 (2006)
Walsh, M.: The hub number of a graph. Int. J. Math. Comput. Sci. 1, 117–124 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported in part by the National Science Council of the Republic of China under contracts NSC 98-2221-E-128-003- and NSC 97-2221-E-011-158-MY3.
Rights and permissions
About this article
Cite this article
Lin, CH., Liu, JJ., Wang, YL. et al. The Hub Number of Sierpiński-Like Graphs. Theory Comput Syst 49, 588–600 (2011). https://doi.org/10.1007/s00224-010-9286-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9286-3