Spiders are graphs with one central vertex and arbitrary many legs. Each leg is a path made of arbitrary many vertices. If the number of paths connecting to the central vertex can be fixed at say, X, we get degree-X spiders. If the length of each leg can also be fixed at say, Y, we get radius-Y spiders. With this notation real-world spiders, with two joints in each leg, are degree-8, radius 3 spiders, and 7-jointed daddy long-legs are degree-8, radius-8 spiders.
Technically, depending on which one you are referring to, a daddy-long leg (aka harvestman) is not a spider but a very close relative, both are arachnids. :-)
ReplyDeleteI didn't realize they had that many joints.
Thanks for the fun blog by the way. (Not sure how many more beasts the Graph community has named but I'm sure you'll dig them up.)
Question though for this graph and others. Are there any special properties that a spider graph has over the close relative graphs like trees, paths, caterpillars, etc?
Indeed, daddy long-legs don't have the "pinch" in the body that spiders do, and have more knees per leg than them too.
ReplyDeleteWhile caterpillars and lobsters pop up often in graph theory, I have only seen spiders in the characterization of ulabeled level planar graphs. It is very likely that they have been defined before under a different name and in a different context.