scientific article; zbMATH DE number 139914

Publication date 28 March 1993

expandable networks finite graphs fractals graph action labeling

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph theory (05C99)

Review text

[For the entire collecton see Zbl 0747.00035.] Fractals and self-similar objects would seem to be inherently continuous objects, and so, saddly, forever beyond the purview of graph theorists in the practice of discrete mathematics. This paper, however, brings graph theory and fractals together, and in so doing, reverses the ``calculus- class order and relationship between the discrete and the continuous in which the first may seem merely a means for reaching the latter. Each section progresses further away from the continuous and the infinite, moving gradually towards the discrete. Furthermore, each section after Section 1 can be read independently of the others, with the expection that Section 5 draws heavily upon Section 4. Section 1 gives an elementary introduction to the basic definitions for the infinite case. Section 2 shows that relation between continuous fractals and ``discrete fractals and provides the motivation and philosophy behind our definitions. Section 3 uses Section 1 to explore two families of infinite graphs which have fractional dimensions which model ways of linking computers into expandable networks, and which show the surprising difference that a few edges can make. Section 4 introduces the more finite structure of a ``graph action (upon a group \(S)\): \(G[S]\) is a labeling of the oriented edges of \(G\) with group elements. Dimensions for these actions are given, and we prove that \(\dim_ 1(G[S])\) is always an integer whenever \(S\) is abelian. Finally, in Section 5 we show how to find \(\dim_ b\) and \(\dim_ *\) as well as \(\dim_ 1\) for finite graphs \(G\). For the entire collection see [Zbl 0747.00035].

Recommendations

Cited in

(18)

This page was built for publication:

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