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.

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.[1]

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

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).


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.