Asymptotics of the Euler number of bipartite graphs
This is a theoretical contribution to enumerative combinatorics, specifically for alternating permutations on bipartite graphs, but the results are limited to specific graph classes and are incremental.
The paper defines the Euler number of a bipartite graph as the number of alternating labelings and reformulates its computation for certain subgraphs using self-adjoint operators, providing asymptotic expansions in terms of eigenvalues. Numerical eigenvalue solutions are given for comb graphs and the Cartesian product P2 □ Pm.
We define the Euler number of a bipartite graph on $n$ vertices to be the number of labelings of the vertices with $1,2,...,n$ such that the vertices alternate in being local maxima and local minima. We reformulate the problem of computing the Euler number of certain subgraphs of the Cartesian product of a graph $G$ with the path $P_m$ in terms of self adjoint operators. The asymptotic expansion of the Euler number is given in terms of the eigenvalues of the associated operator. For two classes of graphs, the comb graphs and the Cartesian product $P_2 \Box P_m$, we numerically solve the eigenvalue problem.