Fault-tolerant Christmas Trees (not the live kind)

It's an interconnected Christmas scene, but that's not a Christmas Tree! (?) COURTESY: Andrew P. Wheeler.

This year's holiday season post brings a bit of graph-theoretic cheer. That's right, there is a type of network called a Christmas tree [1,2]! It is a class of fault-tolerant Hamiltonian graph [2,3]. So far, Christmas trees have been applied to computer and communications networks, but may be found to have a wider range of applications, particularly as we move into the New Year.

An example of a Christmas Tree directed graph as shown in [2]. The top two graphs are slim trees of order 3 (left) and 4 (right). A Christmas tree (bottom) includes selected long-range connections (longer than the immediate connection to mother, daughter, or sister nodes).

This tree could have used a bit more fault-tolerance!

NOTES:
[1] Hsu, L-H and Lin, C-K (2008). Graph Theory and Interconnection Networks. CRC Press, New York.

[2] Hung, C-N, Hsu, L-H, and Sung, T-Y (1999). Christmas tree: A versatile 1-fault-tolerant design for token rings. Information Processing Letters, 72(1–2), 55-63.

[3] Wang, J-J, Hung, C-N, Tan, J.J-N, Hsu, L-H, and Sung, T-Y (2000). Construction schemes for fault-tolerant Hamiltonian graphs. Networks, 35(3), 233-245.