New Bounds on the Number of Edges in a k-Map Graph View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Zhi-Zhong Chen

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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "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"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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'

Turtle is a human-readable linked data format.

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
1 sg:pub.10.1007/978-3-540-27798-9_35 schema:about anzsrc-for:11
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.
7 schema:editor N33fa898d3abd4b10adfc296fa53f4362
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3e519aad538d450bad87bd25d3cd2707
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
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N84cb43bd4e6b4a35be534e5865ff8f6f
32 schema:url https://doi.org/10.1007/978-3-540-27798-9_35
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N33fa898d3abd4b10adfc296fa53f4362 rdf:first N3467a2d06d034acca05fda5d5c17f31d
37 rdf:rest Nbb47452a504f431bbd7e9898ead55b0e
38 N3467a2d06d034acca05fda5d5c17f31d schema:familyName Chwa
39 schema:givenName Kyung-Yong
40 rdf:type schema:Person
41 N3e519aad538d450bad87bd25d3cd2707 schema:isbn 978-3-540-22856-1
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
50 N7713e657b3464ea3ac3e2ac648ad8853 schema:familyName Munro
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
58 Nbb47452a504f431bbd7e9898ead55b0e rdf:first N7713e657b3464ea3ac3e2ac648ad8853
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
 




Preview window. Press ESC to close (or click here)


...