Let be an
-vertex simple graph and consider a vertex labeling
using the integers 1 to
such that each vertex receives a distinct label and
is the label of vertex
. Then a vertex is a pinnacle of the labeled graph if
for all neighbors
of
, and the pinnacle set the the labeled graph is the set of
all the pinnacles, denoted
(Bozeman et al. 2024).
Note that different labelings of a graph may have different pinnacle sets. In particular, the pinnacle sets of the graph are given by the distinct pinnacle sets over all possible
labelings
.
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 connected,
has a size-
pinnacle set iff
has an independent vertex
set of the same size (Bozeman et al. 2024).
For disconnected with
connected components, the smallest pinnacle set of
has size
(Bozeman et al. 2024).