TOPICS

# Pinnacle Set

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

Labeled Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Bozeman, C.; Cheng, C.; Harris, P. E.; Lasinis, S.; and Walker S. "The Pinnacle Sets of a Graph." 27 Jun 2024. https://arxiv.org/pdf/2406.19562.

## Cite this as:

Weisstein, Eric W. "Pinnacle Set." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PinnacleSet.html