# New Bounds on the Number of Edges in a k-Map Graph

Ontology type: schema:Chapter

### Chapter Info

DATE

2004

AUTHORS ABSTRACT

It is known that for every integer k≥ 4, each k-map graph with n vertices has at most kn – 2k edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for k=4. We also show that this bound is not tight for large enough k; more precisely, we show that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$0 < \epsilon < \frac{3}{328}$\end{document} and for every integer \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$k\ge \frac{140}{41\epsilon}$\end{document}, each k-map graph with n vertices has at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{325}{328}+\epsilon)kn -- 2k$\end{document} edges. We further show that for every positive multiple k of 6, there are infinitely many integers n such that some k-map graph with n vertices has at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{11}{12}k+\frac{1}{3})n$\end{document} edges. More... »

PAGES

319-328

### Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-22856-1
978-3-540-27798-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_35

DOI

http://dx.doi.org/10.1007/978-3-540-27798-9_35

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1033485391

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Medical and Health Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1117",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Public Health and Health Services",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan",
"id": "http://www.grid.ac/institutes/grid.412773.4",
"name": [
"Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan"
],
"type": "Organization"
},
"familyName": "Chen",
"givenName": "Zhi-Zhong",
"id": "sg:person.015654265661.98",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
],
"type": "Person"
}
],
"datePublished": "2004",
"datePublishedReg": "2004-01-01",
"description": "It is known that for every integer k\u2265 4, each k-map graph with n vertices has at most kn \u2013 2k edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for k=4. We also show that this bound is not tight for large enough k; more precisely, we show that for every \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$0 < \\epsilon < \\frac{3}{328}$\\end{document} and for every integer \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$k\\ge \\frac{140}{41\\epsilon}$\\end{document}, each k-map graph with n vertices has at most \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$(\\frac{325}{328}+\\epsilon)kn -- 2k$\\end{document} edges. We further show that for every positive multiple k of\u00a06, there are infinitely many integers n such that some k-map graph with n vertices has at least \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$(\\frac{11}{12}k+\\frac{1}{3})n$\\end{document} edges.",
"editor": [
{
"familyName": "Chwa",
"givenName": "Kyung-Yong",
"type": "Person"
},
{
"familyName": "Munro",
"givenName": "J. Ian J.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-27798-9_35",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-22856-1",
"978-3-540-27798-9"
],
"name": "Computing and Combinatorics",
"type": "Book"
},
"keywords": [
"map graphs",
"number of edges",
"new bounds",
"graph",
"vertices",
"integer n",
"bounds",
"edge",
"integers",
"number"
],
"name": "New Bounds on the Number of Edges in a k-Map Graph",
"pagination": "319-328",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1033485391"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-27798-9_35"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-27798-9_35",
"https://app.dimensions.ai/details/publication/pub.1033485391"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:47",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_404.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-27798-9_35"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_35'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_35'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_35'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-27798-9_35'

This table displays all metadata directly associated to this object as RDF triples.

75 TRIPLES      23 PREDICATES      36 URIs      29 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1117
3 schema:author Nd81e7927d511423aba8421b154611b76
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description It is known that for every integer k≥ 4, each k-map graph with n vertices has at most kn – 2k edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for k=4. We also show that this bound is not tight for large enough k; more precisely, we show that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$0 < \epsilon < \frac{3}{328}$\end{document} and for every integer \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$k\ge \frac{140}{41\epsilon}$\end{document}, each k-map graph with n vertices has at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{325}{328}+\epsilon)kn -- 2k$\end{document} edges. We further show that for every positive multiple k of 6, there are infinitely many integers n such that some k-map graph with n vertices has at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(\frac{11}{12}k+\frac{1}{3})n$\end{document} edges.
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
12 schema:keywords bounds
13 edge
14 graph
15 integer n
16 integers
17 map graphs
18 new bounds
19 number
20 number of edges
21 vertices
22 schema:name New Bounds on the Number of Edges in a k-Map Graph
23 schema:pagination 319-328
24 schema:productId N5025ae9d13a34187b3a828df70af3f86
25 Naba92f5748e7455583de73afc194e0b8
26 schema:publisher N4f9f0581f9bd4a4cab68f00f1834295b
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033485391
28 https://doi.org/10.1007/978-3-540-27798-9_35
29 schema:sdDatePublished 2022-05-20T07:47
31 schema:sdPublisher N84cb43bd4e6b4a35be534e5865ff8f6f
32 schema:url https://doi.org/10.1007/978-3-540-27798-9_35
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
38 N3467a2d06d034acca05fda5d5c17f31d schema:familyName Chwa
39 schema:givenName Kyung-Yong
40 rdf:type schema:Person
42 978-3-540-27798-9
43 schema:name Computing and Combinatorics
44 rdf:type schema:Book
45 N4f9f0581f9bd4a4cab68f00f1834295b schema:name Springer Nature
46 rdf:type schema:Organisation
47 N5025ae9d13a34187b3a828df70af3f86 schema:name doi
48 schema:value 10.1007/978-3-540-27798-9_35
49 rdf:type schema:PropertyValue
51 schema:givenName J. Ian J.
52 rdf:type schema:Person
53 N84cb43bd4e6b4a35be534e5865ff8f6f schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Naba92f5748e7455583de73afc194e0b8 schema:name dimensions_id
56 schema:value pub.1033485391
57 rdf:type schema:PropertyValue
59 rdf:rest rdf:nil
60 Nd81e7927d511423aba8421b154611b76 rdf:first sg:person.015654265661.98
61 rdf:rest rdf:nil
62 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
63 schema:name Medical and Health Sciences
64 rdf:type schema:DefinedTerm
65 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
66 schema:name Public Health and Health Services
67 rdf:type schema:DefinedTerm
68 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
69 schema:familyName Chen
70 schema:givenName Zhi-Zhong
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
72 rdf:type schema:Person
73 grid-institutes:grid.412773.4 schema:alternateName Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
74 schema:name Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
75 rdf:type schema:Organization