Asymptotics of the Euler number of bipartite graphs

作者：Ehrenborg Richard; Farjoun Yossi^*

来源：Advances in Applied Mathematics, 2010, 44(2): 155-167.

DOI：10.1016/j.aam.2009.05.002

• Alternating labelings
• Integral operators
• Differential eigenvalue problems
• Numerical solutions

We define the Euler number of a bipartite graph on n vertices to be the number of labelings of the vertices with 1...., 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 Pm 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) square P(m), we numerically solve the eigenvalue problem.

• 出版日期2010-2