Asymptotics of the Euler number of bipartite graphs

Richard Ehrenborg; Yossi Farjoun

doi:10.1016/j.aam.2009.05.002

Asymptotics of the Euler number of bipartite graphs

Richard Ehrenborg, Yossi Farjoun

Mathematics

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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

Original language	English
Pages (from-to)	155-167
Number of pages	13
Journal	Advances in Applied Mathematics
Volume	44
Issue number	2
DOIs	https://doi.org/10.1016/j.aam.2009.05.002
State	Published - 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.

Keywords

Alternating labelings
Differential eigenvalue problems
Integral operators
Numerical solutions

ASJC Scopus subject areas

Applied Mathematics

Access to Document

10.1016/j.aam.2009.05.002

Cite this

@article{f000fc5d005b47caa391abbc0c6de195,

title = "Asymptotics of the Euler number of bipartite graphs",

abstract = "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.",

keywords = "Alternating labelings, Differential eigenvalue problems, Integral operators, Numerical solutions",

author = "Richard Ehrenborg and Yossi Farjoun",

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.",

year = "2010",

month = feb,

doi = "10.1016/j.aam.2009.05.002",

language = "English",

volume = "44",

pages = "155--167",

number = "2",

}

TY - JOUR

T1 - Asymptotics of the Euler number of bipartite graphs

AU - Ehrenborg, Richard

AU - Farjoun, Yossi

N1 - 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.

PY - 2010/2

Y1 - 2010/2

N2 - 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.

AB - 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.

KW - Alternating labelings

KW - Differential eigenvalue problems

KW - Integral operators

KW - Numerical solutions

UR - http://www.scopus.com/inward/record.url?scp=72049085280&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72049085280&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2009.05.002

DO - 10.1016/j.aam.2009.05.002

M3 - Article

AN - SCOPUS:72049085280

SN - 0196-8858

VL - 44

SP - 155

EP - 167

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 2

ER -

Asymptotics of the Euler number of bipartite graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this