On the power of a perturbation for testing non-isomorphism of graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1984-09

AUTHORS

G. M. Prabhu, Narsingh Deo

ABSTRACT

In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic. More... »

PAGES

302-307

References to SciGraph publications

  • 1957-12. Spektren endlicher grafen in ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSIT√ĄT HAMBURG
  • Journal

    TITLE

    BIT Numerical Mathematics

    ISSUE

    3

    VOLUME

    24

    Author Affiliations

    Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "Washington State University", 
              "id": "https://www.grid.ac/institutes/grid.30064.31", 
              "name": [
                "Computer Science Department, Iowa State University, 50011, Ames, Iowa, USA", 
                "Computer Science Department, Washington State University, 99164-1210, Pullman, Washington, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Prabhu", 
            "givenName": "G. M.", 
            "id": "sg:person.016300124422.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016300124422.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Washington State University", 
              "id": "https://www.grid.ac/institutes/grid.30064.31", 
              "name": [
                "Computer Science Department, Iowa State University, 50011, Ames, Iowa, USA", 
                "Computer Science Department, Washington State University, 99164-1210, Pullman, Washington, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deo", 
            "givenName": "Narsingh", 
            "id": "sg:person.010274011142.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1002/jgt.3190010306", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004020143"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1749-6632.1979.tb17779.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006297660"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02941924", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014048771", 
              "https://doi.org/10.1007/bf02941924"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1112/blms/3.3.321", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025984649"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2140/pjm.1957.7.961", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069062606"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1984-09", 
        "datePublishedReg": "1984-09-01", 
        "description": "In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02136028", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136252", 
            "issn": [
              "0006-3835", 
              "1572-9125"
            ], 
            "name": "BIT Numerical Mathematics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "24"
          }
        ], 
        "name": "On the power of a perturbation for testing non-isomorphism of graphs", 
        "pagination": "302-307", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "87ca47a2f1e486b1cdd85411f6daa15c89b0318566cb71c00bb78ddb1576feac"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02136028"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1028505032"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02136028", 
          "https://app.dimensions.ai/details/publication/pub.1028505032"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:57", 
        "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/0000000365_0000000365/records_71680_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF02136028"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    85 TRIPLES      21 PREDICATES      32 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02136028 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Na3b0730852b34b93b6092eeab22389fd
    4 schema:citation sg:pub.10.1007/bf02941924
    5 https://doi.org/10.1002/jgt.3190010306
    6 https://doi.org/10.1111/j.1749-6632.1979.tb17779.x
    7 https://doi.org/10.1112/blms/3.3.321
    8 https://doi.org/10.2140/pjm.1957.7.961
    9 schema:datePublished 1984-09
    10 schema:datePublishedReg 1984-09-01
    11 schema:description In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.
    12 schema:genre research_article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N7606bb801361430ca32026e02ff72459
    16 N81136f6f2ea94f89964710ddfc03ca44
    17 sg:journal.1136252
    18 schema:name On the power of a perturbation for testing non-isomorphism of graphs
    19 schema:pagination 302-307
    20 schema:productId N00a793c172f84031a16863d27e8494aa
    21 Nd1edf220cd7b49dca8e8611d12f5e6ad
    22 Nfb19f24360d441849f4fec58bba357fc
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028505032
    24 https://doi.org/10.1007/bf02136028
    25 schema:sdDatePublished 2019-04-11T12:57
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher Nfd87b54213e74b7abe9961ff706d8ed1
    28 schema:url http://link.springer.com/10.1007/BF02136028
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset articles
    31 rdf:type schema:ScholarlyArticle
    32 N00a793c172f84031a16863d27e8494aa schema:name readcube_id
    33 schema:value 87ca47a2f1e486b1cdd85411f6daa15c89b0318566cb71c00bb78ddb1576feac
    34 rdf:type schema:PropertyValue
    35 N7606bb801361430ca32026e02ff72459 schema:issueNumber 3
    36 rdf:type schema:PublicationIssue
    37 N81136f6f2ea94f89964710ddfc03ca44 schema:volumeNumber 24
    38 rdf:type schema:PublicationVolume
    39 Na3b0730852b34b93b6092eeab22389fd rdf:first sg:person.016300124422.43
    40 rdf:rest Na84ee53ebb4448e48f5ae7c3ec8b97cb
    41 Na84ee53ebb4448e48f5ae7c3ec8b97cb rdf:first sg:person.010274011142.47
    42 rdf:rest rdf:nil
    43 Nd1edf220cd7b49dca8e8611d12f5e6ad schema:name dimensions_id
    44 schema:value pub.1028505032
    45 rdf:type schema:PropertyValue
    46 Nfb19f24360d441849f4fec58bba357fc schema:name doi
    47 schema:value 10.1007/bf02136028
    48 rdf:type schema:PropertyValue
    49 Nfd87b54213e74b7abe9961ff706d8ed1 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    52 schema:name Mathematical Sciences
    53 rdf:type schema:DefinedTerm
    54 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    55 schema:name Pure Mathematics
    56 rdf:type schema:DefinedTerm
    57 sg:journal.1136252 schema:issn 0006-3835
    58 1572-9125
    59 schema:name BIT Numerical Mathematics
    60 rdf:type schema:Periodical
    61 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.30064.31
    62 schema:familyName Deo
    63 schema:givenName Narsingh
    64 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    65 rdf:type schema:Person
    66 sg:person.016300124422.43 schema:affiliation https://www.grid.ac/institutes/grid.30064.31
    67 schema:familyName Prabhu
    68 schema:givenName G. M.
    69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016300124422.43
    70 rdf:type schema:Person
    71 sg:pub.10.1007/bf02941924 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014048771
    72 https://doi.org/10.1007/bf02941924
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.1002/jgt.3190010306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004020143
    75 rdf:type schema:CreativeWork
    76 https://doi.org/10.1111/j.1749-6632.1979.tb17779.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1006297660
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1112/blms/3.3.321 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025984649
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.2140/pjm.1957.7.961 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069062606
    81 rdf:type schema:CreativeWork
    82 https://www.grid.ac/institutes/grid.30064.31 schema:alternateName Washington State University
    83 schema:name Computer Science Department, Iowa State University, 50011, Ames, Iowa, USA
    84 Computer Science Department, Washington State University, 99164-1210, Pullman, Washington, USA
    85 rdf:type schema:Organization
     




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


    ...