Christmas tree networks

Greetings for the season.

Mathematicians live in a world of their own — individually, as well as collectively. Therefore, it is inevitable that among all of the graphs with names like pancake graphs, butterfly networks, star graphs, spider web networks, and brother trees, there should be a thing called a Christmas tree.

It was introduced by Chun-Nan Hung, Lih-Hsing Hsu and Ting-Yi Sung (1999) Christmas tree: a versatile 1-fault-tolerant design for token rings. Information Processing Letters 72: 55-63.

As you can see, it is a network, as well as a tree. The authors describe it as "a 3-regular, planar, [optimal] 1-Hamiltonian, and Hamiltonian-connected graph." The Hamiltonian characteristic refers to the existence of a path through the network that connects all of the nodes and ends up back at the start node (ie. a cycle). The Christmas tree is created by joining two Slim trees together, believe it or not. (The Fat tree is a Slim tree with an extra edge connecting the left and right nodes.)

The authors' particular interest was in communications networks (eg. computer networks); but to me it looks like a (historical) phylogenetic tree at the top with an extra network added at the bottom showing (contemporary) ecological connections. It could thus summarize all of the biology in one diagram!

You can read about all of the above-mentioned graph types in the book by Lih-Hsing Hsu and Cheng-Kuan Lin (2009) Graph Theory and Interconnection Networks; CRC Press. You need to be a mathematician to make sense of it, though.

Thanks to Bradly Alicea for alerting me to this graph type.

PS. The above diagram is actually take from: Jeng-Jung Wang, Chun-Nan Hung, Jimmy JM Tan, Lih-Hsing Hsu, Ting-Yi Sung (2000) Construction schemes for fault-tolerant Hamiltonian graphs. Networks 35: 233-245.