Bull Graph Labels – Prime and Graceful

I haven’t seen any articles or papers where the labeling types for Bull Graphs have been discussed, and therefore will demonstrate that Bull Graphs can be gracefully labeled and prime labeled.

There is three variants of Bull Graphs, the name being derived from the fact, that the structure of the graph is meant to represent the face of a Bull (with a little imagination).

Bull Graphs

Bull Graphs

Graceful Labeling is a popular problem and type of labeling for graphs. The most famous conjecture related to Graceful Labeling is the Graceful Tree Conjecture, which states that all trees can be gracefully labeled. There has been progress toward a complete proof for the conjecture, however, there is some problems which still remain. The main techniques I’ve seen used are induction and proof by example and exhaustion.

My conjecture will be shown by the method of example. Although, firstly it’s best to define what is a Graceful Label for a graph.

Definition: A Graceful Labeling of a graph G with n edges, is an injective mapping from V(G) to {0, 1, 2, 3, …, n}, whereby there exists a surjective mapping from E(G) to {1, 2, 3, …, n}, with the condition that f(e) = |f(u)-f(v)|.

The definition is much easier to understand in natural language; given a graph G, label each vertex a subset of integers, with the restriction that the absolute difference between the weights of the edges between two adjacent vertices runs in chronological order from 1 to n. For instance, if my greatest vertex label was 6, then I must find a labeling of the graph such that the absolute difference between all adjacent vertices within the graph runs from 1 to 6.

Graceful Graphs

Graceful Graphs

Proof: Since the variants of the Bull Graphs are all isomorphic to each other, we only need to find one configuration of graceful labeling to show that all Bull Graphs can be labelled in such a manner.

Graceful Bull Graphs

Graceful Bull Graphs

The second labeling which I would like to discuss, and then apply to Bull Graphs, is called Prime Labeling.

Definition: A prime labeling of a graph G, is a binjective mapping from G(V) to {1, 2, 3, |V|}, with the condition that each edge (e =uv), the GCD (f(u), f(v)) = 1. The adjacent vertices are all coprime or relatively prime.


As stated before, since all variants of the Bull Graph are isomorphic, then we only need to find one configuration of labels which are prime to prove it for all other variants.

Prime Bull Graph

Prime Bull Graph


A Dynamic Survey of Graph Labeling – Gallian (2013)

Guide to Graph Labeling Zoo – Gallian (1991)

On Prime Labeling of some Classes of Graphs – Ramya, Rangarajan, Sattanathan (2012)


About 0x14c

I'm currently a Software Developer. My primary interests are Graph Theory, Number Theory, Programming Language Theory, Logic and Windows Debugging.
This entry was posted in Computer Science, Graph Theory, Mathematics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s