On first-order definitions of subgraph isomorphism properties View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-09

AUTHORS

M. E. Zhukovskii

ABSTRACT

Let φ(F) be the property of containing (as a subgraph) an isomorphic copy of a graph F. It is easy to show that this property cannot be defined in a first-order language by a sentence with a quantifier depth (or variable width) strictly less than the number of vertices in F. Nevertheless, such a definition exists in some classes of graphs. Three classes of graphs are considered: connected graphs with a large number of vertices, graphs with large treewidth, and graphs with high connectivity. More... »

PAGES

454-456

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1134/s1064562417050167

DOI

http://dx.doi.org/10.1134/s1064562417050167

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhukovskii", 
        "givenName": "M. E.", 
        "id": "sg:person.011152672013.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-662-07003-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046929489", 
          "https://doi.org/10.1007/978-3-662-07003-1"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-09", 
    "datePublishedReg": "2017-09-01", 
    "description": "Let \u03c6(F) be the property of containing (as a subgraph) an isomorphic copy of a graph F. It is easy to show that this property cannot be defined in a first-order language by a sentence with a quantifier depth (or variable width) strictly less than the number of vertices in F. Nevertheless, such a definition exists in some classes of graphs. Three classes of graphs are considered: connected graphs with a large number of vertices, graphs with large treewidth, and graphs with high connectivity.", 
    "genre": "article", 
    "id": "sg:pub.10.1134/s1064562417050167", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136704", 
        "issn": [
          "1064-5624", 
          "1531-8362"
        ], 
        "name": "Doklady Mathematics", 
        "publisher": "Pleiades Publishing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "96"
      }
    ], 
    "keywords": [
      "class of graphs", 
      "first-order language", 
      "large treewidth", 
      "number of vertices", 
      "graph", 
      "first-order definition", 
      "high connectivity", 
      "large number", 
      "treewidth", 
      "vertices", 
      "language", 
      "graph F.", 
      "connectivity", 
      "definition", 
      "class", 
      "quantifier depth", 
      "sentences", 
      "isomorphism property", 
      "number", 
      "copies", 
      "isomorphic copy", 
      "properties", 
      "depth", 
      "f.", 
      "Nevertheless", 
      "subgraph isomorphism properties"
    ], 
    "name": "On first-order definitions of subgraph isomorphism properties", 
    "pagination": "454-456", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1092525323"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s1064562417050167"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s1064562417050167", 
      "https://app.dimensions.ai/details/publication/pub.1092525323"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_743.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1134/s1064562417050167"
  }
]
 

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.1134/s1064562417050167'

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.1134/s1064562417050167'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1134/s1064562417050167'

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

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


 

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

88 TRIPLES      22 PREDICATES      53 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s1064562417050167 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Na57f2f0db4f74c42b7439362c4a2dee0
4 schema:citation sg:pub.10.1007/978-3-662-07003-1
5 schema:datePublished 2017-09
6 schema:datePublishedReg 2017-09-01
7 schema:description Let φ(F) be the property of containing (as a subgraph) an isomorphic copy of a graph F. It is easy to show that this property cannot be defined in a first-order language by a sentence with a quantifier depth (or variable width) strictly less than the number of vertices in F. Nevertheless, such a definition exists in some classes of graphs. Three classes of graphs are considered: connected graphs with a large number of vertices, graphs with large treewidth, and graphs with high connectivity.
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0ca5bba853fc48d7b6cbe21e86ce917f
12 Ne7475c09c536441f8fa4b6cee594a1ed
13 sg:journal.1136704
14 schema:keywords Nevertheless
15 class
16 class of graphs
17 connectivity
18 copies
19 definition
20 depth
21 f.
22 first-order definition
23 first-order language
24 graph
25 graph F.
26 high connectivity
27 isomorphic copy
28 isomorphism property
29 language
30 large number
31 large treewidth
32 number
33 number of vertices
34 properties
35 quantifier depth
36 sentences
37 subgraph isomorphism properties
38 treewidth
39 vertices
40 schema:name On first-order definitions of subgraph isomorphism properties
41 schema:pagination 454-456
42 schema:productId N02f32dad8ef94ef1892cd6be07e3b117
43 N8dd2e9f5fd0a4a71b888a61d2f9701ec
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092525323
45 https://doi.org/10.1134/s1064562417050167
46 schema:sdDatePublished 2021-12-01T19:40
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher Nc8ef4aef0fbd430895022df1df3bdf6b
49 schema:url https://doi.org/10.1134/s1064562417050167
50 sgo:license sg:explorer/license/
51 sgo:sdDataset articles
52 rdf:type schema:ScholarlyArticle
53 N02f32dad8ef94ef1892cd6be07e3b117 schema:name doi
54 schema:value 10.1134/s1064562417050167
55 rdf:type schema:PropertyValue
56 N0ca5bba853fc48d7b6cbe21e86ce917f schema:issueNumber 2
57 rdf:type schema:PublicationIssue
58 N8dd2e9f5fd0a4a71b888a61d2f9701ec schema:name dimensions_id
59 schema:value pub.1092525323
60 rdf:type schema:PropertyValue
61 Na57f2f0db4f74c42b7439362c4a2dee0 rdf:first sg:person.011152672013.96
62 rdf:rest rdf:nil
63 Nc8ef4aef0fbd430895022df1df3bdf6b schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Ne7475c09c536441f8fa4b6cee594a1ed schema:volumeNumber 96
66 rdf:type schema:PublicationVolume
67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
68 schema:name Mathematical Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
71 schema:name Pure Mathematics
72 rdf:type schema:DefinedTerm
73 sg:journal.1136704 schema:issn 1064-5624
74 1531-8362
75 schema:name Doklady Mathematics
76 schema:publisher Pleiades Publishing
77 rdf:type schema:Periodical
78 sg:person.011152672013.96 schema:affiliation grid-institutes:grid.18763.3b
79 schema:familyName Zhukovskii
80 schema:givenName M. E.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011152672013.96
82 rdf:type schema:Person
83 sg:pub.10.1007/978-3-662-07003-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046929489
84 https://doi.org/10.1007/978-3-662-07003-1
85 rdf:type schema:CreativeWork
86 grid-institutes:grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia
87 schema:name Moscow Institute of Physics and Technology (State University), 141700, Dolgoprudnyi, Moscow oblast, Russia
88 rdf:type schema:Organization
 




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


...