Friendly-index set

{{Short description|Set of integers in graph theory}}

[[File:Friendly index.svg|thumb|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.]]

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 {{mvar|n}}-vertex undirected graph {{math|G {{=}} (V,E)}} is defined to be an assignment of the values 0 and 1 to the vertices of {{mvar|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 {{mvar|G}}, one may also label the edges: a given edge {{mvar|uv}} is labeled with a 0 if its endpoints {{mvar|u}} and {{mvar|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 {{mvar|G}}, denoted {{math|FI(G)}}, is the set of numbers that can arise as friendly indexes of friendly labelings of {{mvar|G}}.{{cite journal|first1=Harris|last1=Kwong|first2=Sin-Min|last2=Lee|first3=Ho|last3=Ng| journal=Discrete Math.|volume=308|issue=23|year=2008|pages=5522–5532|doi=10.1016/j.disc.2007.10.018|title=On friendly index sets of 2-regular graphs|mr=2459372 |doi-access=free}}

The Dynamic Survey of Graph Labeling contains a list of papers that examines the friendly indices of various graphs.{{cite journal|first1=Joseph A|last1=Gallian|title=A dynamic survey of graph labelling|journal=El. J. Combinat| year=2009|volume=16|issue=#DS6|url=http://www.emis.de/journals/EJC/Surveys/ds6.pdf}}