Counting peaks on graphs

MaRDI QIDQ5206920zbMATH OpenFDO

Authors Alexander Diaz-Lopez, Lucas Everham, Pamela E. Harris, Erik Insko, Vincent Marcantonio, Mohamed Omar

Publication date 19 December 2019

Full work available at URL https://arxiv.org/abs/1708.08493, http://ajc.maths.uq.edu.au/pdf/75/ajc_v75_p174.pdf

zbMATH Keywords

peak set of the graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: Given a graph $G$ with $n$ vertices and a bijective labeling of the vertices using the integers $1,2,ldots,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 an enumeration of the vertices of $G$ as $v_1,v_2,ldots,v_n$ and a fix a set $SsubsetV(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 emph{peak set of the graph} $G$, and the set of all labelings with peak set $S$ is denoted by $PSG$. This definition generalizes the study of peak sets of 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 $PSG$ for any $SsubseteqV(G)$. We also explore peak sets in certain families of graphs, including cycle graphs and joins of graphs.

Recommendations

• Permutations with given peak set
• The pinnacle set of a permutation
• Value-peaks of permutations
• Factoring peak polynomials
• Twin peaks

Cites work

• A proof of the peak polynomial positivity conjecture
• Coefficients and roots of peak polynomials
• Coloured peak algebras and Hopf algebras.
• Enriched \(P\)-partitions and peak algebras
• Enumeration of alternating permutations according to peak sets
• New results on the peak algebra.
• On meteors, earthworms and wimps
• Peak sets of classical Coxeter groups
• Permutations with given peak set
• The number of permutations with the same peak set for signed permutations
• The peak algebra and the descent algebras of types B and D
• The peak algebra of the symmetric group
• The pinnacle set of a permutation

Cited in

(3)

• Permutation Tutte polynomial
• Pinnacle sets of signed permutations
• Twin peaks

This page was built for publication: Counting peaks on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206920)