Sierpiński graphs as spanning subgraphs of Hanoi graphs

Andreas Hinz; Sandi Klavžar; Sara Zemljič

Open Mathematics (2013)

  • Volume: 11, Issue: 6, page 1153-1157
  • ISSN: 2391-5455

Abstract

top
Hanoi graphs H pn model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S pn arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S pn embeds as a spanning subgraph into H pn if and only if p is odd or, trivially, if n = 1.

How to cite

top

Andreas Hinz, Sandi Klavžar, and Sara Zemljič. "Sierpiński graphs as spanning subgraphs of Hanoi graphs." Open Mathematics 11.6 (2013): 1153-1157. <http://eudml.org/doc/269481>.

@article{AndreasHinz2013,
abstract = {Hanoi graphs H pn model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S pn arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S pn embeds as a spanning subgraph into H pn if and only if p is odd or, trivially, if n = 1.},
author = {Andreas Hinz, Sandi Klavžar, Sara Zemljič},
journal = {Open Mathematics},
keywords = {Sierpiński graph; Hanoi graph; Spanning subgraph; Hamming graph; spanning subgraph},
language = {eng},
number = {6},
pages = {1153-1157},
title = {Sierpiński graphs as spanning subgraphs of Hanoi graphs},
url = {http://eudml.org/doc/269481},
volume = {11},
year = {2013},
}

TY - JOUR
AU - Andreas Hinz
AU - Sandi Klavžar
AU - Sara Zemljič
TI - Sierpiński graphs as spanning subgraphs of Hanoi graphs
JO - Open Mathematics
PY - 2013
VL - 11
IS - 6
SP - 1153
EP - 1157
AB - Hanoi graphs H pn model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S pn arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S pn embeds as a spanning subgraph into H pn if and only if p is odd or, trivially, if n = 1.
LA - eng
KW - Sierpiński graph; Hanoi graph; Spanning subgraph; Hamming graph; spanning subgraph
UR - http://eudml.org/doc/269481
ER -

References

top
  1. [1] Arett D., Dorée S., Coloring and counting on the Tower of Hanoi graphs, Math. Mag., 2010, 83, 200–209 http://dx.doi.org/10.4169/002557010X494841[Crossref] Zbl1227.05140
  2. [2] Beaudou L., Gravier S., Klavžar S., Kovše M., Mollard M., Covering codes in Sierpinski graphs, Discrete Math. Theor. Comput. Sci., 2010, 12(3), 63–74 Zbl1280.05130
  3. [3] Chen X., Shen J., On the Frame-Stewart conjecture about the Towers of Hanoi, SIAM J. Comput., 2004, 33(3), 584–589 http://dx.doi.org/10.1137/S0097539703431019[Crossref] Zbl1055.05002
  4. [4] Fu H.-Y., Xie D., Equitable L(2, 1)-labelings of Sierpinski graphs, Australas. J. Combin., 2010, 46, 147–156 Zbl1196.05083
  5. [5] Hinz A.M., The Tower of Hanoi, Enseign. Math., 1989, 35(3–4), 289–321 Zbl0746.05035
  6. [6] Hinz A.M., Parisse D., On the planarity of Hanoi graphs, Expo. Math., 2002, 20(3), 263–268 http://dx.doi.org/10.1016/S0723-0869(02)80023-8[Crossref] Zbl1008.05045
  7. [7] Hinz A.M., Parisse D., Coloring Hanoi and Sierpinski graphs, Discrete Math., 2012, 312(9), 1521–1535 http://dx.doi.org/10.1016/j.disc.2011.08.019[Crossref] Zbl1239.05066
  8. [8] Hinz A.M., Parisse D., The average eccentricity of Sierpinski graphs, Graphs Combin., 2012, 28(5), 671–686 http://dx.doi.org/10.1007/s00373-011-1076-4[Crossref] Zbl1256.05058
  9. [9] Imrich W., Klavžar S., Rall D.F., Topics in Graph Theory, AK Peters, Wellesley, 2008 Zbl1156.05001
  10. [10] Klavžar S., Milutinovic U., Graphs S(n, k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J., 1997, 47(122)(1), 95–104 http://dx.doi.org/10.1023/A:1022444205860[Crossref] Zbl0898.05042
  11. [11] Klavžar S., Milutinovic U., Petr C., On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem, Discrete Appl. Math., 2002, 120(1–3), 141–157 http://dx.doi.org/10.1016/S0166-218X(01)00287-6[Crossref] Zbl1019.90047
  12. [12] Lin C.-H., Liu J.-J., Wang Y.-L., Yen W.C.-K., The hub number of Sierpinski-like graphs, Theory Comput. Syst., 2011, 49(3), 588–600 http://dx.doi.org/10.1007/s00224-010-9286-3[WoS][Crossref] Zbl1234.05178
  13. [13] Lipscomb S.L., Fractals and Universal Spaces in Dimension Theory, Springer Monogr. Math., Springer, New York, 2009 http://dx.doi.org/10.1007/978-0-387-85494-6[Crossref] Zbl1210.28002
  14. [14] Milutinovic U., Completeness of the Lipscomb universal space, Glas. Mat., 1992, 27(47)(2), 343–364 Zbl0797.54045
  15. [15] Parisse D., On some metric properties of the Sierpinski graphs S k n , Ars Combin., 2009, 90, 145–160 Zbl1224.05153
  16. [16] Park S.E., The group of symmetries of the Tower of Hanoi graph, Amer. Math. Monthly, 2010, 117(4), 353–360 http://dx.doi.org/10.4169/000298910X480829[Crossref] Zbl1200.05026
  17. [17] Romik D., Shortest paths in the Tower of Hanoi graph and finite automata, SIAM J. Discrete Math., 2006, 20(3), 610–622 http://dx.doi.org/10.1137/050628660[Crossref] Zbl1127.68069

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.