Hostname: page-component-8448b6f56d-wq2xx Total loading time: 0 Render date: 2024-04-16T10:57:00.469Z Has data issue: false hasContentIssue false
  • English
  • Français

1-perfect codes in Sierpiński graphs

Published online by Cambridge University Press:  17 April 2009

Sandi Klavžar ,
Uroš Milutinović  and
Ciril Petr
Sandi Klavžar
Affiliation:
Department of Mathematics, PeF, University of Maribor, Koroška 160, 2000 Maribor, Slovenia e-mail: sandi.klavzar@uni-lj.si, uros.milutinovic@uni-mb.si
Uroš Milutinović
Affiliation:
Department of Mathematics, PeF, University of Maribor, Koroška 160, 2000 Maribor, Slovenia e-mail: sandi.klavzar@uni-lj.si, uros.milutinovic@uni-mb.si
Ciril Petr
Affiliation:
Iskratel Telecommunications Systems Ltd., Tržaška 37a, 2000 Maribor, Slovenia e-mail: petr@iskratel.si
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Sierpiński graphs S (n, κ) generalise the Tower of Hanoi graphs—the graph S (n, 3) is isomorphic to the graph Hn of the Tower of Hanoi with n disks. A 1-perfect code (or an efficient dominating set) in a graph G is a vertex subset of G with the property that the closed neighbourhoods of its elements form a partition of V (G). It is proved that the graphs S (n, κ) possess unique 1-perfect codes, thus extending a previously known result for Hn. An efficient decoding algorithm is also presented. The present approach, in particular the proposed (de)coding, is intrinsically different from the approach to Hn.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 66 , Issue 3 , December 2002 , pp. 369 - 384
Copyright
Copyright © Australian Mathematical Society 2002

References

[1]Bange, D.W., Barkauskas, A.E. and Slater, P.J., ‘Efficient dominating sets in graphs’, in Applications of Discrete Mathematics, Clemson, 1986 (SIAM, Philadelphia, 1988), pp. 189–199.Google Scholar
[2]Bange, D.W., Barkauskas, A.E. and Clark, L.H., ‘The number of orientations of a tree admitting an efficient dominating set’, Ars Combin. 45 (1997), 201–207.Google Scholar
[3]Bannai, E., ‘Codes in bipartite distance-regular graphs’, J. London Math. Soc. 16 (1977), 197–202.Google Scholar
[4]Biggs, N., ‘Perfect codes in graphs’, J. Combin. Theory Ser. B 15 (1973), 289–296.CrossRefGoogle Scholar
[5]Cull, P. and Nelson, I., ‘Error-correcting codes on the Towers of Hanoi graphs’, Discrete Math. 208/209 (1999), 157–175.Google Scholar
[6]Cull, P. and Nelson, I., ‘Perfect codes, NP-completeness, and Towers of Hanoi graphs’, Bull. Inst. Combin. Appl. 26 (1999), 13–38.Google Scholar
[7]Fellows, M.R. and Hoover, M.N., ‘Perfect domination’, Australas. J. Combin. 3 (1991), 141–150.Google Scholar
[8]Hammond, P., ‘On the nonexistence of perfect and nearly perfect codes’, Discrete Math. 39 (1982), 105–109.CrossRefGoogle Scholar
[9]Haynes, T.W., Hedetniemi, S.T. and Slater, P.J., Fundamentals of domination in graphs (Marcel Dekker, New York, 1998).Google Scholar
[10]Hedetniemi, S.T., McRae, A.A. and Parks, D.A., ‘Complexity results’, in Domination in Graphs: Advanced Topics, (Haynes, T.W., Hedetniemi, S.T. and Slater, P.J., Editors) (Marcel Dekker, New York, 1998), pp. 233–269.Google Scholar
[11]Klavžar, S. and Milutinović, U., ‘Graphs S (n, kappa;) and a variant of the Tower of Hanoi problem’, Czechoslovak Math. J. 47 (1997), 95–104.Google Scholar
[12]Klostermeyer, W.F. and Eschen, E.M., ‘Perfect codes and independent dominating sets’, Congr. Numer. 142 (2000), 7–28.Google Scholar
[13]Kratochvíl, J., ‘Perfect codes over graphs’, J. Combin. Theory Ser. B 40 (1986), 224–228.CrossRefGoogle Scholar
[14]Kratochvíl, J., ‘Perfect codes and two-graphs’, Comment. Math. Univ. Carolin. 30 (1989), 755–760.Google Scholar
[15]Kratochvíl, J., Perfect codes in general graphs, Rozpravy Československé Akad. Vĕd Řada Mat. Přírod Věd 7 (Akademia, Praha, 1991).Google Scholar
[16]Kratochvíl, J., ‘Regular codes in regular graphs are difficult’, Discrete Math. 133 (1994), 191–205.CrossRefGoogle Scholar
[17]Kratochvíl, J. and Křivánek, M., ‘On the computational complexity of codes in graphs’, in Mathematical Foundations of Computer Science, Carlsbad, 1988, Lecture Notes in Comput. Sci. 324 (Springer-Verlag, Berlin, 1988), pp. 396–404.CrossRefGoogle Scholar
[18]Kratochvíl, J., Malý, J. and Matoušek, J., ‘On the existence of perfect codes in a random graph’, in Random Graphs, (Karoński, M., Jaworski, Jerzy and Ruciński, Andrzej, Editors) (J. Wiley and Sons, Chichester, 1990), pp. 141–149.Google Scholar
[19]Kratochvíl, J., Manuel, P. and Miller, M., ‘Generalized domination in chordal graphs’, Nordic J. Comput. 2 (1995), 41–50.Google Scholar
[20]Li, C.-K. and Nelson, I., ‘Perfect codes on the Towers of Hanoi graphs’, Bull. Austral. Math. Soc. 57 (1998), 367–376.CrossRefGoogle Scholar
[21]Lipscomb, S.L. and Perry, J.C., ‘Lipscomb's L (A) space fractalized in Hilbert's l 2(A) space’, Proc. Amer. Math. Soc. 115 (1992), 1157–1165.Google Scholar
[22]Milutinović, U., ‘Completeness of the Lipscomb space’, Glas. Mat. Ser. III 27 (47) (1992), 343–364.Google Scholar
[23]Smart, C.B. and Slater, P.J., ‘Complexity results for closed neighborhood order parameters’, Congr. Numer. 112 (1995), 83–96.Google Scholar
[24]Smith, D.H., ‘Perfect codes in the graphs O κand L (O kappa;)’ Glasgow Math. J. 21 (1980), 169–172.CrossRefGoogle Scholar