graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a friendly-index set is a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. Th ...

integers An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

associated with a given

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

and generated by a type of

graph labeling In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph. Formally, given a graph , a vertex labeling is a function of to a set ...

called a friendly labeling. A friendly labeling of an -vertex undirected graph is defined to be an assignment of the values 0 and 1 to the vertices of 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 , one may also label the edges: a given edge is labeled with a 0 if its endpoints and 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 In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if x is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...

of the difference between the number of edges labeled 0 and the number of edges labeled 1. The friendly index set of , denoted , is the set of numbers that can arise as friendly indexes of friendly labelings of . The Dynamic Survey of Graph Labeling contains a list of papers that examines the friendly indices of various graphs.

References

Graph theory objects Graph invariants {{graph-stub