Download Poster (427 KB)

Publication Date


Document Type


Presentation Type


Degree Type





Songling Shan

Mentor Department



An antimagic labeling of a graph G with p edges is a function f: E(G) → {1,…,p} such that distinct edges receive distinct numbers and any two vertex sums are distinct, where a vertex sum is the sum of the labels of all edges incident to that vertex. A graph is antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured every connected graph with at least three vertices is antimagic. The conjecture was confirmed for trees with at most one vertex of degree 2 and other classes of graphs including caterpillars and spiders. However, the conjecture is open for lobsters, where a lobster is a tree with a central path such that all vertices are within distance two from the central path. We study the antimagic labeling of lobsters and show that three classes of lobsters are antimagic.

The first class of lobsters that we studied was one with an arbitrary amount of edges along the central path, and legs extending from each inner vertex on the path. The legs consist of arms, which are edges connecting the arbitrary number of claws to the central path. This is the basic type of lobster, with variations on uniformity of claws, as well as adding arbitrary amounts of degree two vertices to the central path (see Figure 1).

The second class we review allowed for m vertices along a central path, then off each central path vertex there is at least one leg and then as many more legs and leaves as possible (See Figure 2). There are x + y + ...+ z = q stumps, where x, y, ..., z ≥ 0. Additionally, there are a + b+ ... + c = n legs, where a, b, ..., c ≥ 1.

The third class of lobster that we study is a patterned-based graph (see Figure 3). It sets constants as follows:

  • With a clearly defined central path, the two endpoints of that path are vertices of degree 1
  • Every packet of legs consists of exactly twice as many edges as there are legs, that is; each leg is comprised of two edges
  • Every packet of legs is the same for the entire span of the graph, and each are separated by buffer vertices of degree 2

With each of these graphs, we define a class of lobster graphs and work through examples of each class to learn more. Our research is not limited to these classes of graphs, and we will continue to add to our report to reflect all that we have learned.


Authors: Joie Green, Brett Kleptich, Ian Samsami

This project has not received IRB approval.

On Antimagic Labeling of Lobsters

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.