Extremal Problems on Components and Loops in Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02

AUTHORS

Sadik Delen, Ismail Naci Cangul

ABSTRACT

The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G)≤−4 are shown to be disconnected, and if Ω(G)≥−2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G)≥−2, then certainly the graph should be a tree. Similarly, it is shown that if the realization is a connected graph G and Ω(G)≥0, then certainly the graph should be cyclic. Also, when Ω(G)≥−4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G)≥0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs. We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence. More... »

PAGES

1-11

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10114-018-8086-6

DOI

http://dx.doi.org/10.1007/s10114-018-8086-6

DIMENSIONS

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


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": "Uluda\u011f University", 
          "id": "https://www.grid.ac/institutes/grid.34538.39", 
          "name": [
            "Mathematics Department, Uludag University, Gorukle 16059, Bursa, Turkey"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Delen", 
        "givenName": "Sadik", 
        "id": "sg:person.013767703334.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013767703334.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Uluda\u011f University", 
          "id": "https://www.grid.ac/institutes/grid.34538.39", 
          "name": [
            "Mathematics Department, Uludag University, Gorukle 16059, Bursa, Turkey"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cangul", 
        "givenName": "Ismail Naci", 
        "id": "sg:person.013745253026.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013745253026.73"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.disc.2009.09.023", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024042803"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01070234", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031011970", 
          "https://doi.org/10.1007/bf01070234"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01070234", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031011970", 
          "https://doi.org/10.1007/bf01070234"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(94)00104-q", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032810606"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(91)90311-o", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032990868"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(92)90152-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036668796"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0110037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062837838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2017.08.027", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091818429"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.12691/tjant-6-1-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101431519"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-02", 
    "datePublishedReg": "2019-02-01", 
    "description": "The authors recently defined a new graph invariant denoted by \u03a9(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of \u03a9. All graphs G so that \u03a9(G)\u2264\u22124 are shown to be disconnected, and if \u03a9(G)\u2265\u22122, then the graph is potentially connected. It is also shown that if the realization is a connected graph and \u03a9(G)\u2265\u22122, then certainly the graph should be a tree. Similarly, it is shown that if the realization is a connected graph G and \u03a9(G)\u22650, then certainly the graph should be cyclic. Also, when \u03a9(G)\u2265\u22124, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then \u03a9(G)\u22650. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs. We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10114-018-8086-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1040372", 
        "issn": [
          "1439-8516", 
          "1439-7617"
        ], 
        "name": "Acta Mathematica Sinica, English Series", 
        "type": "Periodical"
      }
    ], 
    "name": "Extremal Problems on Components and Loops in Graphs", 
    "pagination": "1-11", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b8a4ea1ed183e36bb57a5b4054e12443d96c2f1ce661d0f96c9d0aa3c8b3338b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10114-018-8086-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107729176"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10114-018-8086-6", 
      "https://app.dimensions.ai/details/publication/pub.1107729176"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T22:41", 
    "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_8690_00000566.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10114-018-8086-6"
  }
]
 

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/s10114-018-8086-6'

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/s10114-018-8086-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10114-018-8086-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10114-018-8086-6'


 

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

87 TRIPLES      21 PREDICATES      33 URIs      17 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10114-018-8086-6 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N59e43693e5f84dfc897399ba392fb685
4 schema:citation sg:pub.10.1007/bf01070234
5 https://doi.org/10.1016/0012-365x(91)90311-o
6 https://doi.org/10.1016/0012-365x(92)90152-6
7 https://doi.org/10.1016/0012-365x(94)00104-q
8 https://doi.org/10.1016/j.disc.2009.09.023
9 https://doi.org/10.1016/j.disc.2017.08.027
10 https://doi.org/10.1137/0110037
11 https://doi.org/10.12691/tjant-6-1-4
12 schema:datePublished 2019-02
13 schema:datePublishedReg 2019-02-01
14 schema:description The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G)≤−4 are shown to be disconnected, and if Ω(G)≥−2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G)≥−2, then certainly the graph should be a tree. Similarly, it is shown that if the realization is a connected graph G and Ω(G)≥0, then certainly the graph should be cyclic. Also, when Ω(G)≥−4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G)≥0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs. We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.
15 schema:genre research_article
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf sg:journal.1040372
19 schema:name Extremal Problems on Components and Loops in Graphs
20 schema:pagination 1-11
21 schema:productId N602a68d3796d44a3bb4c07a1bc27e9c3
22 N64150da76bd0414f89e82b10ebdffd28
23 Nbf5e4ffa53e944c695660c8b291e2dd6
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107729176
25 https://doi.org/10.1007/s10114-018-8086-6
26 schema:sdDatePublished 2019-04-10T22:41
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher Na0cde80b379a4de7b1d8655cd39a04e5
29 schema:url https://link.springer.com/10.1007%2Fs10114-018-8086-6
30 sgo:license sg:explorer/license/
31 sgo:sdDataset articles
32 rdf:type schema:ScholarlyArticle
33 N3dfca1f9a54a4cf483aac4965661f93c rdf:first sg:person.013745253026.73
34 rdf:rest rdf:nil
35 N59e43693e5f84dfc897399ba392fb685 rdf:first sg:person.013767703334.10
36 rdf:rest N3dfca1f9a54a4cf483aac4965661f93c
37 N602a68d3796d44a3bb4c07a1bc27e9c3 schema:name dimensions_id
38 schema:value pub.1107729176
39 rdf:type schema:PropertyValue
40 N64150da76bd0414f89e82b10ebdffd28 schema:name readcube_id
41 schema:value b8a4ea1ed183e36bb57a5b4054e12443d96c2f1ce661d0f96c9d0aa3c8b3338b
42 rdf:type schema:PropertyValue
43 Na0cde80b379a4de7b1d8655cd39a04e5 schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 Nbf5e4ffa53e944c695660c8b291e2dd6 schema:name doi
46 schema:value 10.1007/s10114-018-8086-6
47 rdf:type schema:PropertyValue
48 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
49 schema:name Mathematical Sciences
50 rdf:type schema:DefinedTerm
51 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
52 schema:name Pure Mathematics
53 rdf:type schema:DefinedTerm
54 sg:journal.1040372 schema:issn 1439-7617
55 1439-8516
56 schema:name Acta Mathematica Sinica, English Series
57 rdf:type schema:Periodical
58 sg:person.013745253026.73 schema:affiliation https://www.grid.ac/institutes/grid.34538.39
59 schema:familyName Cangul
60 schema:givenName Ismail Naci
61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013745253026.73
62 rdf:type schema:Person
63 sg:person.013767703334.10 schema:affiliation https://www.grid.ac/institutes/grid.34538.39
64 schema:familyName Delen
65 schema:givenName Sadik
66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013767703334.10
67 rdf:type schema:Person
68 sg:pub.10.1007/bf01070234 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031011970
69 https://doi.org/10.1007/bf01070234
70 rdf:type schema:CreativeWork
71 https://doi.org/10.1016/0012-365x(91)90311-o schema:sameAs https://app.dimensions.ai/details/publication/pub.1032990868
72 rdf:type schema:CreativeWork
73 https://doi.org/10.1016/0012-365x(92)90152-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036668796
74 rdf:type schema:CreativeWork
75 https://doi.org/10.1016/0012-365x(94)00104-q schema:sameAs https://app.dimensions.ai/details/publication/pub.1032810606
76 rdf:type schema:CreativeWork
77 https://doi.org/10.1016/j.disc.2009.09.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024042803
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1016/j.disc.2017.08.027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091818429
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1137/0110037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062837838
82 rdf:type schema:CreativeWork
83 https://doi.org/10.12691/tjant-6-1-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101431519
84 rdf:type schema:CreativeWork
85 https://www.grid.ac/institutes/grid.34538.39 schema:alternateName Uludağ University
86 schema:name Mathematics Department, Uludag University, Gorukle 16059, Bursa, Turkey
87 rdf:type schema:Organization
 




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


...