The splittance of a graph View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1981-09

AUTHORS

Peter L. Hammer, Bruno Simeone

ABSTRACT

The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs). More... »

PAGES

275-284

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02579333

DOI

http://dx.doi.org/10.1007/bf02579333

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "University of Waterloo, Ont., Canada", 
            "Instituto per le Applicazioni del Calcolo, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hammer", 
        "givenName": "Peter L.", 
        "id": "sg:person.015740461177.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "University of Waterloo, Ont., Canada", 
            "Instituto per le Applicazioni del Calcolo, Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "Bruno", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0095-8956(71)90030-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027938333"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(77)90066-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037639463"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70731-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046754752"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0132048", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062839586"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0602006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848681"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109703686", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-349-03521-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109703686", 
          "https://doi.org/10.1007/978-1-349-03521-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-349-03521-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109703686", 
          "https://doi.org/10.1007/978-1-349-03521-2"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1981-09", 
    "datePublishedReg": "1981-09-01", 
    "description": "The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs).", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02579333", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "name": "The splittance of a graph", 
    "pagination": "275-284", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e1536a61ae69fd64825fb6e2e8117ed207d43f93af77716f2df0bd7c9409421f"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02579333"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047300684"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02579333", 
      "https://app.dimensions.ai/details/publication/pub.1047300684"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:34", 
    "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/0000000370_0000000370/records_46769_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02579333"
  }
]
 

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/bf02579333'

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/bf02579333'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02579333'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02579333'


 

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

90 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02579333 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9c60e9e2de6e4b9cad8abcc881f33b78
4 schema:citation sg:pub.10.1007/978-1-349-03521-2
5 https://app.dimensions.ai/details/publication/pub.1109703686
6 https://doi.org/10.1016/0012-365x(77)90066-8
7 https://doi.org/10.1016/0095-8956(71)90030-x
8 https://doi.org/10.1016/s0167-5060(08)70731-3
9 https://doi.org/10.1137/0132048
10 https://doi.org/10.1137/0602006
11 schema:datePublished 1981-09
12 schema:datePublishedReg 1981-09-01
13 schema:description The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs).
14 schema:genre research_article
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf N96cb61af9d3c4b0c9441bf6107444c6d
18 Nd80129f7479a4f55b0b6b36f603c35d6
19 sg:journal.1136493
20 schema:name The splittance of a graph
21 schema:pagination 275-284
22 schema:productId N428be432f25d4b00b6affe59ec3e1f6e
23 N558be97f0bcc483ab08efcfac59c7c72
24 Nd8e68e4c174744a3a8c74d7472768bf3
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047300684
26 https://doi.org/10.1007/bf02579333
27 schema:sdDatePublished 2019-04-11T13:34
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher Ncf5bc5582a65438cbc5ae41b6bad65a5
30 schema:url http://link.springer.com/10.1007%2FBF02579333
31 sgo:license sg:explorer/license/
32 sgo:sdDataset articles
33 rdf:type schema:ScholarlyArticle
34 N428be432f25d4b00b6affe59ec3e1f6e schema:name doi
35 schema:value 10.1007/bf02579333
36 rdf:type schema:PropertyValue
37 N558be97f0bcc483ab08efcfac59c7c72 schema:name readcube_id
38 schema:value e1536a61ae69fd64825fb6e2e8117ed207d43f93af77716f2df0bd7c9409421f
39 rdf:type schema:PropertyValue
40 N96cb61af9d3c4b0c9441bf6107444c6d schema:volumeNumber 1
41 rdf:type schema:PublicationVolume
42 N9c60e9e2de6e4b9cad8abcc881f33b78 rdf:first sg:person.015740461177.00
43 rdf:rest Nb4261e0df4cf40d38b4be68a203f1804
44 Nb4261e0df4cf40d38b4be68a203f1804 rdf:first sg:person.012600006066.78
45 rdf:rest rdf:nil
46 Ncf5bc5582a65438cbc5ae41b6bad65a5 schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 Nd80129f7479a4f55b0b6b36f603c35d6 schema:issueNumber 3
49 rdf:type schema:PublicationIssue
50 Nd8e68e4c174744a3a8c74d7472768bf3 schema:name dimensions_id
51 schema:value pub.1047300684
52 rdf:type schema:PropertyValue
53 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
54 schema:name Information and Computing Sciences
55 rdf:type schema:DefinedTerm
56 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
57 schema:name Computation Theory and Mathematics
58 rdf:type schema:DefinedTerm
59 sg:journal.1136493 schema:issn 0209-9683
60 1439-6912
61 schema:name Combinatorica
62 rdf:type schema:Periodical
63 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
64 schema:familyName Simeone
65 schema:givenName Bruno
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
67 rdf:type schema:Person
68 sg:person.015740461177.00 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
69 schema:familyName Hammer
70 schema:givenName Peter L.
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015740461177.00
72 rdf:type schema:Person
73 sg:pub.10.1007/978-1-349-03521-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109703686
74 https://doi.org/10.1007/978-1-349-03521-2
75 rdf:type schema:CreativeWork
76 https://app.dimensions.ai/details/publication/pub.1109703686 schema:CreativeWork
77 https://doi.org/10.1016/0012-365x(77)90066-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037639463
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1016/0095-8956(71)90030-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027938333
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/s0167-5060(08)70731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046754752
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1137/0132048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839586
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1137/0602006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848681
86 rdf:type schema:CreativeWork
87 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
88 schema:name Instituto per le Applicazioni del Calcolo, Rome, Italy
89 University of Waterloo, Ont., Canada
90 rdf:type schema:Organization
 




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


...