Pinnacle Set

Let G be an n-vertex simple graph and consider a vertex labeling lambda using the integers 1 to n such that each vertex receives a distinct label and lambda(u) is the label of vertex u. Then a vertex is a pinnacle of the labeled graph if lambda(u)>lambda(v) for all neighbors v of u, and the pinnacle set the the labeled graph is the set of all the pinnacles, denoted Pin(G,lambda) (Bozeman et al. 2024).


Note that different labelings of a graph may have different pinnacle sets. In particular, the pinnacle sets of the graph G are given by the distinct pinnacle sets over all possible labelings lambda. For example, there are six distinct pinnacle sets (some of which are shared by multiple distinct labelings) for the graph illustrated above, namely {5}, {2, 5}, {3, 5}, {4, 5}, {2, 4, 5}, and {3, 4, 5}.

For G connected, G has a size-k pinnacle set iff G has an independent vertex set of the same size (Bozeman et al. 2024).

For G disconnected with c connected components, the smallest pinnacle set of G has size c (Bozeman et al. 2024).

See also

Labeled Graph

Explore with Wolfram|Alpha


Bozeman, C.; Cheng, C.; Harris, P. E.; Lasinis, S.; and Walker S. "The Pinnacle Sets of a Graph." 27 Jun 2024.

Cite this as:

Weisstein, Eric W. "Pinnacle Set." From MathWorld--A Wolfram Web Resource.

Subject classifications