On the pagenumber of complete bipartite graphs

Hikoe Enomoto; Tomoki Nakamigawa; Katsuhiro Ota

doi:10.1006/jctb.1997.1773

On the pagenumber of complete bipartite graphs

Hikoe Enomoto, Tomoki Nakamigawa, Katsuhiro Ota

Department of Mathematics

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

38 Citations (Scopus)

Abstract

The pagenumberp(G) of a graphGis defined as the smallestnsuch thatGcan be embedded in a book withnpages. We give an upper bound for the page-number of the complete bipartite graphK_m,n. Among other things, we provep(K_n,n)≤⌊2n/3⌋+1 andp(K_⌊n²/4_⌋,n)≤n-1. We also give an asymptotic result: min{m:p(K_m,n)=n}=n²/4+O(n^7/4).

Original language	English
Pages (from-to)	111-120
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	71
Issue number	1
DOIs	https://doi.org/10.1006/jctb.1997.1773
Publication status	Published - 1997 Sept

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1997.1773

Cite this

@article{b602a68a6710488a8df397a5628a6cae,

title = "On the pagenumber of complete bipartite graphs",

abstract = "The pagenumberp(G) of a graphGis defined as the smallestnsuch thatGcan be embedded in a book withnpages. We give an upper bound for the page-number of the complete bipartite graphKm,n. Among other things, we provep(Kn,n)≤⌊2n/3⌋+1 andp(K⌊n2/4⌋,n)≤n-1. We also give an asymptotic result: min{m:p(Km,n)=n}=n2/4+O(n7/4).",

author = "Hikoe Enomoto and Tomoki Nakamigawa and Katsuhiro Ota",

year = "1997",

month = sep,

doi = "10.1006/jctb.1997.1773",

language = "English",

volume = "71",

pages = "111--120",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - On the pagenumber of complete bipartite graphs

AU - Enomoto, Hikoe

AU - Nakamigawa, Tomoki

AU - Ota, Katsuhiro

PY - 1997/9

Y1 - 1997/9

N2 - The pagenumberp(G) of a graphGis defined as the smallestnsuch thatGcan be embedded in a book withnpages. We give an upper bound for the page-number of the complete bipartite graphKm,n. Among other things, we provep(Kn,n)≤⌊2n/3⌋+1 andp(K⌊n2/4⌋,n)≤n-1. We also give an asymptotic result: min{m:p(Km,n)=n}=n2/4+O(n7/4).

AB - The pagenumberp(G) of a graphGis defined as the smallestnsuch thatGcan be embedded in a book withnpages. We give an upper bound for the page-number of the complete bipartite graphKm,n. Among other things, we provep(Kn,n)≤⌊2n/3⌋+1 andp(K⌊n2/4⌋,n)≤n-1. We also give an asymptotic result: min{m:p(Km,n)=n}=n2/4+O(n7/4).

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

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

U2 - 10.1006/jctb.1997.1773

DO - 10.1006/jctb.1997.1773

M3 - Article

AN - SCOPUS:0031234619

SN - 0095-8956

VL - 71

SP - 111

EP - 120

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

On the pagenumber of complete bipartite graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this