Snakes

There are several different notions of snake graphs. In combinatorics snakes are finite subgraphs of the square grid formed by taking a union of cells, where a cell consists of four cyclically connected vertices of the grid and the edges that join them, and where the cells that form a snake can be ordered in a linear fashion, so that each cell is either immediately to the right of or immediately above the preceding cell.

Octopi

Keeping up with the marine theme, an octopus graph is similar to the jellyfish. This one is easier to define as it consists of a head, which is k-clique, and m tentacles of size t. The k-clique is a complete graph on k vertices and each of the tentacles is a path of length t. Note that for k=1 the octopus graph becomes a spider. These graphs occur in papers on neural networks and are of interest because of their large diameter and easy to parametrize density.

Jellyfish

Jellyfish graphs seem to be a fairly new idea. The term first appears around the turn of the century in an attempt to describe the topology of the Internet graph. The idea is that jellyfish graphs have a body (or cap) and lots of tentacles emanating from the core. In the case of the Internet, when looking at the Autonomous Systems level, the so called AS Internet graph can be thought of as a jellyfish graph. The Internet core corresponds to a clique or quasi-clique of high degree nodes. The rest of the graph can be seen as chains of lower degree nodes. Unlike other classes of graphs, jellyfish don't have a succinct definition. There is a formal definition here but it takes half a page and is not particularly pleasant.

Starfish

Starfish graphs are made of one central cycle and a bunch of tentacles. When drawn appropriately they can look like starfish. More formally, a starfish graph has k vertices of degree 4 and k vertices of degree 2, with the degree-4 vertices arranged in a cycle and the degree-2 vertices making up each tentacle. Setting k=5 yields the traditional 5-tentacled beast. Apparently, the H-cover problem is NP-Complete even for simple graphs like starfish.

Tadpoles

Tadpoles are graphs made of cycles and paths. The smallest tadpole is made of a cycle on three vertices joined with a path with just one edge. Bigger tadpoles can be obtained by making the cycle larger and/or the path longer. When the tail of the tadpole is made of just one edge, the graph is also known as a pan graph, with the tail playing the role of a pan-handle. Tadpole graphs have been mentioned in the physics literature and seem to date back to Feynman.

Snarks

Snarks are graphs with an interesting property related to graph coloring. One of the most fascinating coloring results, the four-color theorem states that every map can be colored with 4 colors so that no two neighboring countries have the same color. This is the same as saying that every planar graph can be vertex-colored with 4 colors so that no two adjacent nodes have the same color. The four-color theorem can be restated in terms of snarks as follows: no snark is planar. Informally, a snark is a graph in which every vertex has degree 3 and in which every 3-coloring of edges results in some pair of adjacent edges with the same color. Formally, a snark is a biconnected cubic graph with edge chromatic number 4. There are infinitely many snarks but Petersen's graph is the classic. Since the 70's a lot of strange-looking snarks have appeared in various papers: the Szekeres snark, the Blanusa snark, the Zemfirescu snark, Tietze's graph, etc. Tutte's conjecture that all snarks have the Petersen graph as a minor was proven by Robertson, Seymour and company and is now known as "the snark theorem." Snarks are non-planar and non-Hamiltonian. Even stronger, removing any one node from a snark leaves a Hamiltonian subgraph.

Centipedes

Centipedes are a subclass of caterpillars. A graph is a centipede if it can be obtained by appending a "leg" to each degree-2 node of a path. In reality they look like a centipede seen from the side at a moment when all its legs on one side occlude all its legs on the other side. I know they were used as far back as 1986 where they popped up in the characterization of the class of graphs that admit cylindric visibility representations.

Spiders

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.

Lobsters

Lobsters are to caterpillars what caterpillars are to paths. In SAT-style terminology, lobster : caterpillar :: caterpillar : path. That is, a graph is a lobster if removing all degree-1 vertices results in a caterpillar. The smallest lobster that is not a caterpillar has 7 vertices. Removing all degree-1 vertices from the smallest lobster results in the smallest caterpillar, which also known as "the claw". I first heard about lobster graphs when reading about the Ringel-Kotzig conjecture in 1993. The conjecture is that all trees are "graceful", or more formally, that all trees admit a graceful labeling. A labeling of an n-vertex tree is graceful if the vertices can be numbered from 1 to n, so that when all the edges are labeled with the absolute difference of the labels of their endpoints, the list of edge labels covers all the numbers from 1 to n-1. This is one of those conjectures that everybody believes are true, but which are still difficult to prove. One class of trees for which the conjecture is proven true is the class of lobsters with perfect matching.

Caterpillars

A caterpillar is simple to define: a graph in which the removal of all degree-1 vertices leaves a path. In a sense, it is the next best thing to a path. Several graph drawing algorithms that work for paths can be extended to work for caterpillars. I wonder when the first reference to caterpillar graphs occurred... The very hungry caterpillar has nice illustrations.

Graph beasts

A new graph beast every week. How many weeks can this go on?