Asymptotics of the Euler number of bipartite graphs

Richard Ehrenborg, Yossi Farjoun

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 P2 □ Pm, we numerically solve the eigenvalue problem.

Original languageEnglish
Pages (from-to)155-167
Number of pages13
JournalAdvances in Applied Mathematics
Issue number2
StatePublished - Feb 2010

Bibliographical note

Funding Information:
The authors thank Eric Clark, Bob Strichartz and the referee. Moreover they thank the Department of Mathematics at MIT where this paper was completed. The first author was partially supported by National Security Agency grant H98230-06-1-0072.


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

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Asymptotics of the Euler number of bipartite graphs'. Together they form a unique fingerprint.

Cite this