Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2013-05

AUTHORS

Gyula Y. Katona, Nándor Sieben

ABSTRACT

A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices v and w adjacent to a vertex u, and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of n-vertex, diameter d graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter. More... »

PAGES

535-551

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00373-012-1146-2

DOI

http://dx.doi.org/10.1007/s00373-012-1146-2

DIMENSIONS

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


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": "Budapest University of Technology and Economics", 
          "id": "https://www.grid.ac/institutes/grid.6759.d", 
          "name": [
            "Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar Tud\u00f3sok krt. 2, 1117, Budapest, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Katona", 
        "givenName": "Gyula Y.", 
        "id": "sg:person.015007677675.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015007677675.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Northern Arizona University", 
          "id": "https://www.grid.ac/institutes/grid.261120.6", 
          "name": [
            "Department of Mathematics and Statistics, Northern Arizona University, 86011-5717, Flagstaff, AZ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sieben", 
        "givenName": "N\u00e1ndor", 
        "id": "sg:person.0705654574.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0705654574.72"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1002/(sici)1097-0118(199706)25:2<119::aid-jgt3>3.0.co;2-p", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005731236"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.20278", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008043383"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9904-1948-09098-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015112749"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2006.11.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023672484"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2006.06.032", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025013806"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2008.09.035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028708212"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.20187", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030736005"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/050636218", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062846396"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.7155/jgaa.00205", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1073626491"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013-05", 
    "datePublishedReg": "2013-05-01", 
    "description": "A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices v and w adjacent to a vertex u, and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of n-vertex, diameter d graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00373-012-1146-2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136071", 
        "issn": [
          "0911-0119", 
          "1435-5914"
        ], 
        "name": "Graphs and Combinatorics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "29"
      }
    ], 
    "name": "Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs", 
    "pagination": "535-551", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "fe74b62754419a53739c480e8cf2240852c494a48e09e2f3fc483b571468d90b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00373-012-1146-2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053422119"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00373-012-1146-2", 
      "https://app.dimensions.ai/details/publication/pub.1053422119"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T14:04", 
    "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/0000000001_0000000264/records_8660_00000492.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00373-012-1146-2"
  }
]
 

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-012-1146-2'

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-012-1146-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00373-012-1146-2'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00373-012-1146-2'


 

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

98 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00373-012-1146-2 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nb107c33ffe3e4230bb15871f9b1b5077
4 schema:citation https://doi.org/10.1002/(sici)1097-0118(199706)25:2<119::aid-jgt3>3.0.co;2-p
5 https://doi.org/10.1002/jgt.20187
6 https://doi.org/10.1002/jgt.20278
7 https://doi.org/10.1016/j.disc.2006.06.032
8 https://doi.org/10.1016/j.disc.2006.11.005
9 https://doi.org/10.1016/j.disc.2008.09.035
10 https://doi.org/10.1090/s0002-9904-1948-09098-x
11 https://doi.org/10.1137/050636218
12 https://doi.org/10.7155/jgaa.00205
13 schema:datePublished 2013-05
14 schema:datePublishedReg 2013-05-01
15 schema:description A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices v and w adjacent to a vertex u, and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of n-vertex, diameter d graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter.
16 schema:genre research_article
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N366aaee62a0f400b9210d14603333eb8
20 Ned044883e6824847a58b17fbb12c2a2b
21 sg:journal.1136071
22 schema:name Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs
23 schema:pagination 535-551
24 schema:productId N433e3196b23649fda21582b3de1bd94e
25 N505076ec1c70418eb47c98a22da870d9
26 Ndb918d87574949f681f0fb0dcc6fe05c
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053422119
28 https://doi.org/10.1007/s00373-012-1146-2
29 schema:sdDatePublished 2019-04-10T14:04
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher Ncfa829896d2a474e858f312d9d08cf28
32 schema:url http://link.springer.com/10.1007/s00373-012-1146-2
33 sgo:license sg:explorer/license/
34 sgo:sdDataset articles
35 rdf:type schema:ScholarlyArticle
36 N366aaee62a0f400b9210d14603333eb8 schema:issueNumber 3
37 rdf:type schema:PublicationIssue
38 N433e3196b23649fda21582b3de1bd94e schema:name doi
39 schema:value 10.1007/s00373-012-1146-2
40 rdf:type schema:PropertyValue
41 N4cebe24af8a949238e90e84b694d654a rdf:first sg:person.0705654574.72
42 rdf:rest rdf:nil
43 N505076ec1c70418eb47c98a22da870d9 schema:name dimensions_id
44 schema:value pub.1053422119
45 rdf:type schema:PropertyValue
46 Nb107c33ffe3e4230bb15871f9b1b5077 rdf:first sg:person.015007677675.29
47 rdf:rest N4cebe24af8a949238e90e84b694d654a
48 Ncfa829896d2a474e858f312d9d08cf28 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 Ndb918d87574949f681f0fb0dcc6fe05c schema:name readcube_id
51 schema:value fe74b62754419a53739c480e8cf2240852c494a48e09e2f3fc483b571468d90b
52 rdf:type schema:PropertyValue
53 Ned044883e6824847a58b17fbb12c2a2b schema:volumeNumber 29
54 rdf:type schema:PublicationVolume
55 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
56 schema:name Mathematical Sciences
57 rdf:type schema:DefinedTerm
58 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
59 schema:name Pure Mathematics
60 rdf:type schema:DefinedTerm
61 sg:journal.1136071 schema:issn 0911-0119
62 1435-5914
63 schema:name Graphs and Combinatorics
64 rdf:type schema:Periodical
65 sg:person.015007677675.29 schema:affiliation https://www.grid.ac/institutes/grid.6759.d
66 schema:familyName Katona
67 schema:givenName Gyula Y.
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015007677675.29
69 rdf:type schema:Person
70 sg:person.0705654574.72 schema:affiliation https://www.grid.ac/institutes/grid.261120.6
71 schema:familyName Sieben
72 schema:givenName Nándor
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0705654574.72
74 rdf:type schema:Person
75 https://doi.org/10.1002/(sici)1097-0118(199706)25:2<119::aid-jgt3>3.0.co;2-p schema:sameAs https://app.dimensions.ai/details/publication/pub.1005731236
76 rdf:type schema:CreativeWork
77 https://doi.org/10.1002/jgt.20187 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030736005
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1002/jgt.20278 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008043383
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/j.disc.2006.06.032 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025013806
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/j.disc.2006.11.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023672484
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/j.disc.2008.09.035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028708212
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1090/s0002-9904-1948-09098-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1015112749
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1137/050636218 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062846396
90 rdf:type schema:CreativeWork
91 https://doi.org/10.7155/jgaa.00205 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073626491
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.261120.6 schema:alternateName Northern Arizona University
94 schema:name Department of Mathematics and Statistics, Northern Arizona University, 86011-5717, Flagstaff, AZ, USA
95 rdf:type schema:Organization
96 https://www.grid.ac/institutes/grid.6759.d schema:alternateName Budapest University of Technology and Economics
97 schema:name Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar Tudósok krt. 2, 1117, Budapest, Hungary
98 rdf:type schema:Organization
 




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


...