Friendly-index set

In graph theory, a friendly-index set is a finite set of integers associated with a given undirected graph and generated by a type of graph labeling called a friendly labeling.

The number of vertices here is even, so a friendly labeling of the vertices means assigning an equal number of 1's (blue) and 0's (red) to the vertices of the graph. In a graph with an odd number of vertices, there would be exactly one more of either number than the other. Each edge is labeled 0 if the two vertices it connects are the same number, and 1 if they are different.

A friendly labeling of an n-vertex undirected graph G = (V,E) is defined to be an assignment of the values 0 and 1 to the vertices of G with the property that the number of vertices labeled 0 is as close as possible to the number of vertices labeled 1: they should either be equal (for graphs with an even number of vertices) or differ by one (for graphs with an odd number of vertices).

Given a friendly labeling of the vertices of G, one may also label the edges: a given edge uv is labeled with a 0 if its endpoints u and v have equal labels, and it is labeled with a 1 if its endpoints have different labels. The friendly index of the labeling is the absolute value of the difference between the number of edges labeled 0 and the number of edges labeled 1.

The friendly index set of G, denoted FI(G), is the set of numbers that can arise as friendly indexes of friendly labelings of G.

The Dynamic Survey of Graph Labeling contains a list of papers that examines the friendly indices of various graphs.

References

1. Kwong, Harris; Lee, Sin-Min; Ng, Ho (2008). "On friendly index sets of 2-regular graphs". Discrete Math. 308 (23): 5522–5532. doi:10.1016/j.disc.2007.10.018. MR 2459372.
2. Gallian, Joseph A (2009). "A dynamic survey of graph labelling" (PDF). El. J. Combinat. 16 (#DS6).