Weighted Domination of Independent Sets View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-14

AUTHORS

Ron Aharoni, Irina Gorelik

ABSTRACT

The independent domination numberγi(G) of a graph G is the maximum, over all independent sets I, of the minimal number of vertices needed to dominate I. It is known (Aharoni et al. in Combinatorica 22:335–343, 2002) that in chordal graphs γi is equal to γ, the ordinary domination number. The weighted version of this result is not true, but we show that it does hold for interval graphs, and for the intersection graphs of subtrees of a given tree, where each subtree is a single edge. More... »

PAGES

1-9

References to SciGraph publications

  • 2002-07. A Tree Version of Kőnig's Theorem in COMBINATORICA
  • 2001-01. The Clique Complex and Hypergraph Matching in COMBINATORICA
  • Journal

    TITLE

    Graphs and Combinatorics

    ISSUE

    N/A

    VOLUME

    N/A

    From Grant

  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00373-019-02024-3

    DOI

    http://dx.doi.org/10.1007/s00373-019-02024-3

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Technion \u2013 Israel Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Department of Mathematics, Technion, 32000, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Aharoni", 
            "givenName": "Ron", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technion \u2013 Israel Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6451.6", 
              "name": [
                "Department of Mathematics, Technion, 32000, Haifa, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gorelik", 
            "givenName": "Irina", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s004930170006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021366666", 
              "https://doi.org/10.1007/s004930170006"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s004930200016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022557354", 
              "https://doi.org/10.1007/s004930200016"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(74)90094-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031063244"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052485385"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03-14", 
        "datePublishedReg": "2019-03-14", 
        "description": "The independent domination number\u03b3i(G) of a graph G is the maximum, over all independent sets I, of the minimal number of vertices needed to dominate I. It is known (Aharoni et al. in Combinatorica 22:335\u2013343, 2002) that in chordal graphs \u03b3i is equal to \u03b3, the ordinary domination number. The weighted version of this result is not true, but we show that it does hold for interval graphs, and for the intersection graphs of subtrees of a given tree, where each subtree is a single edge.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00373-019-02024-3", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.7173940", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136071", 
            "issn": [
              "0911-0119", 
              "1435-5914"
            ], 
            "name": "Graphs and Combinatorics", 
            "type": "Periodical"
          }
        ], 
        "name": "Weighted Domination of Independent Sets", 
        "pagination": "1-9", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "31ed4839e04e37a8d34be0a171c43c8070e9d00d49663366d5daf02a9d31f7d4"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00373-019-02024-3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112760382"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00373-019-02024-3", 
          "https://app.dimensions.ai/details/publication/pub.1112760382"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:55", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29204_00000003.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00373-019-02024-3"
      }
    ]
     

    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/s00373-019-02024-3'

    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/s00373-019-02024-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02024-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02024-3'


     

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

    76 TRIPLES      21 PREDICATES      28 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00373-019-02024-3 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N5a2cf08120e949cd8767e4b4af81420d
    4 schema:citation sg:pub.10.1007/s004930170006
    5 sg:pub.10.1007/s004930200016
    6 https://doi.org/10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v
    7 https://doi.org/10.1016/0095-8956(74)90094-x
    8 schema:datePublished 2019-03-14
    9 schema:datePublishedReg 2019-03-14
    10 schema:description The independent domination numberγi(G) of a graph G is the maximum, over all independent sets I, of the minimal number of vertices needed to dominate I. It is known (Aharoni et al. in Combinatorica 22:335–343, 2002) that in chordal graphs γi is equal to γ, the ordinary domination number. The weighted version of this result is not true, but we show that it does hold for interval graphs, and for the intersection graphs of subtrees of a given tree, where each subtree is a single edge.
    11 schema:genre research_article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf sg:journal.1136071
    15 schema:name Weighted Domination of Independent Sets
    16 schema:pagination 1-9
    17 schema:productId N2c5bb84689eb4bbfac16ea34d7874fa8
    18 N489e8eb6aacf489d8786ee0acfe657dc
    19 N6a18eca34fb24a2b8bdaf5ab456b1b05
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112760382
    21 https://doi.org/10.1007/s00373-019-02024-3
    22 schema:sdDatePublished 2019-04-11T11:55
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher Nc7b1c5d7a87549fba7a715e6b212dbd0
    25 schema:url https://link.springer.com/10.1007%2Fs00373-019-02024-3
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset articles
    28 rdf:type schema:ScholarlyArticle
    29 N0ea88e2ec5cc4c039452b3713a3fa541 schema:affiliation https://www.grid.ac/institutes/grid.6451.6
    30 schema:familyName Aharoni
    31 schema:givenName Ron
    32 rdf:type schema:Person
    33 N2c5bb84689eb4bbfac16ea34d7874fa8 schema:name readcube_id
    34 schema:value 31ed4839e04e37a8d34be0a171c43c8070e9d00d49663366d5daf02a9d31f7d4
    35 rdf:type schema:PropertyValue
    36 N442ff745c0f44c549d3f6cf36549c9f5 rdf:first Nb4e3969cc2164f74b8644702e081a5fa
    37 rdf:rest rdf:nil
    38 N489e8eb6aacf489d8786ee0acfe657dc schema:name doi
    39 schema:value 10.1007/s00373-019-02024-3
    40 rdf:type schema:PropertyValue
    41 N5a2cf08120e949cd8767e4b4af81420d rdf:first N0ea88e2ec5cc4c039452b3713a3fa541
    42 rdf:rest N442ff745c0f44c549d3f6cf36549c9f5
    43 N6a18eca34fb24a2b8bdaf5ab456b1b05 schema:name dimensions_id
    44 schema:value pub.1112760382
    45 rdf:type schema:PropertyValue
    46 Nb4e3969cc2164f74b8644702e081a5fa schema:affiliation https://www.grid.ac/institutes/grid.6451.6
    47 schema:familyName Gorelik
    48 schema:givenName Irina
    49 rdf:type schema:Person
    50 Nc7b1c5d7a87549fba7a715e6b212dbd0 schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    53 schema:name Mathematical Sciences
    54 rdf:type schema:DefinedTerm
    55 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Pure Mathematics
    57 rdf:type schema:DefinedTerm
    58 sg:grant.7173940 http://pending.schema.org/fundedItem sg:pub.10.1007/s00373-019-02024-3
    59 rdf:type schema:MonetaryGrant
    60 sg:journal.1136071 schema:issn 0911-0119
    61 1435-5914
    62 schema:name Graphs and Combinatorics
    63 rdf:type schema:Periodical
    64 sg:pub.10.1007/s004930170006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021366666
    65 https://doi.org/10.1007/s004930170006
    66 rdf:type schema:CreativeWork
    67 sg:pub.10.1007/s004930200016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022557354
    68 https://doi.org/10.1007/s004930200016
    69 rdf:type schema:CreativeWork
    70 https://doi.org/10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1052485385
    71 rdf:type schema:CreativeWork
    72 https://doi.org/10.1016/0095-8956(74)90094-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1031063244
    73 rdf:type schema:CreativeWork
    74 https://www.grid.ac/institutes/grid.6451.6 schema:alternateName Technion – Israel Institute of Technology
    75 schema:name Department of Mathematics, Technion, 32000, Haifa, Israel
    76 rdf:type schema:Organization
     




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


    ...