Graph Labeling: a brief introduction for students

 

Graphs consist of a set of vertices, some of which are connected by edges. In graph labeling, we put a label – a number – on each vertex, and doing so creates a label for each edge. We try to label graphs according to various rules, and ask questions about whether the graph can be labeled according to the rules, and if so, what the largest number needed as a label might be. 

 

In the CSU Channel Islands REU, we’ll consider one of two kinds of graph labeling:  radio labeling or k-equitable labeling. For a brief discussion of radio labeling, keep reading!

 

Radio Labeling

 

Think about the channels assigned to radio stations. The basic principle is that stations with transmitters that are close to each other (e.g. in Oxnard and Ventura) are assigned channels with a large difference (e.g. 88.3 and 91.1), but stations that are far apart (e.g. Oxnard and San Diego) can have channel assignments with a small difference (e.g. 88.3 and 88.5).

 

We extend this idea to graphs by specifying that vertices close to each other get labels that are far apart. To specify what a radio labeling for a graph is, we need a couple of definitions.

Distance: the distance between vertices v and w, d(v,w), is the length of the shortest path between the vertices.  For example, in the graph shown in Figure 1a, d(v,x) = 1, d(v,y) = 1, and d(v,z) = 2.

Diameter: the diameter of a graph G, diam(G), is the maximum distance.  In Figure 1a, the diameter of the graph is 2.

 

Graph of cycle on four vertices, with vertices labeled sequentially v, x, y, and z.

The vertices of C4 are labeled, sequentially, 0, 2, 5, 3.

Figure 1a:  C4, the cycle on 4 vertices

Figure 1b:  a radio labeling of C4

 

Now we’re ready to define radio labeling. An assignment of labels (numbers) to the vertices of a graph is a radio labeling if the distance between any two vertices plus the absolute value of the difference of the labels of the vertices exceeds the diameter of the graph. Suppose we let f(v) be the label assigned to the vertex v.  Then radio labeling satisfies the equation

d(v,w) + |f(v) – f(w)|  >  diam(G)

for every pair of vertices v and w of the graph G.

 

Examining the graph in figure 1b, which has diameter 2, we see that to radio label this graph, adjacent vertices must have label values that differ by at least 2, and vertices at distance two must have label values that differ by at least 1. 

 

The last column in the table below shows whether we have a radio labeling. The diameter of the graph is 2, so every entry in this column must be 3 or more.

 

Pair of vertices

Distance

Difference in edge labels

Sum of previous two columns

v, x

1

2

3

v , y

1

3

4

v, z

2

5

7

x, y

2

1

3

x, z

1

3

4

y, z

1

2

3

 

Is it possible to radio label the C4 graph using labels with smaller values? Can you use {0, 1, 2, 4}? 

 

We define the radio number of a graph G, rn(G), as the largest label that must be used in a proper radio labeling of G. Examine the three radio labelings of C5 in Figure 2. (This graph has diameter 2, so the difference in the vertex labels plus the distance between the vertices must be at least 3.)

 

C5 graph, labeled sequentially 1, 4, 6, 8, 3.

C5 graph, labeled sequentially 0, 2, 5, 1, 4.

C5 graph, labeled sequentially 0, 2, 5, 1, 4.

Figure 2a

Figure 2b

Figure 2c

 

The largest label in the three labelings is first 8, then 5, then 5. Some thought should convince you that it’s impossible to radio label C5 using a largest label smaller than 5. This means that the radio number of C5 is 5.

 

Not much is known about radio numbers of graphs. For instance, we might ask whether it’s possible to find a formula in terms of n that gives the radio number of Cn. We can explore connections between radio numbers and graph properties such as diameter and connectivity.  We might prefer to look at some modifications of radio labeling – for instance, a modification in which we only care about the difference in label values for vertices of distance 1 or 2 apart. There are plenty of questions to tackle! 

 

Why is graph labeling a good topic for undergraduate student research?
There are many accessible problems that don't require years of advanced study to understand. A week of reading and trying examples leaves a student ready to tackle his/her own problems. Problems seem to lend themselves to different approaches from combinatorial reasoning (often nothing more than fancy “counting”), to good old-fashioned ingenuity and creativity. There is some room for writing computer code to generate examples and check conjectures. Analysis of what can and can't be done with a computer may also be a fruitful area for student investigation.