Counting Peaks on Graphs

Given a graph G with n vertices and a bijective labeling of the vertices using the integers 1, 2, . . . , n, we say G has a peak at vertex v if the degree of v is greater than or equal to 2, and if the label on v is larger than the label of all its neighbors. Fix a set S ⊂ V (G). We want to determine the number of distinct bijective labelings of the vertices of G, such that the vertices in S are precisely the peaks of G. The set S is called the peak set of the graph G, and the set of all labelings with peak set S is denoted by P (S;G). This definition generalizes the study of peak sets of ISSN: 2202-3518 c ©The author(s). Released under the CC BY 4.0 International License A. DIAZ-LOPEZ ET AL. /AUSTRALAS. J. COMBIN. 75 (2) (2019), 174–189 175 permutations, as that work is the special case of G being the path graph on n vertices. In this paper, we present an algorithm for constructing all of the bijective labelings in P (S;G) for any S ⊆ V (G). We also use combinatorial methods to explore peak sets in certain well-studied families of graphs.