Counting peaks on graphs

zbMATH Open1429.05103arXiv1708.08493MaRDI QIDQ5206920FDOQ5206920

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

Publication date: 19 December 2019

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.

Full work available at URL: https://arxiv.org/abs/1708.08493

Recommendations

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

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)

Cites Work

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

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)