Competition Numbers and Phylogeny Numbers: Uniform Complete Multipartite Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-08

AUTHORS

Yaokun Wu, Yanzhen Xiong, Soesoe Zaw

ABSTRACT

Let D be a digraph. The competition graph of D is the graph sharing the same vertex set with D such that two different vertices are adjacent if and only if they have a common out-neighbor in D; the phylogeny graph of D is the competition graph of the digraph obtained from D by adding a loop at every vertex. For any graph G with n vertices, its competition number κ(G) is the least nonnegative integer k such that G is an induced subgraph of the competition graph of an acyclic digraph with n+k vertices, while its phylogeny number ϕ(G) is the least nonnegative integer p such that G is an induced subgraph of the phylogeny graph of an acyclic digraph with n+p vertices. This paper provides new estimates of the competition numbers and phylogeny numbers of complete multipartite graphs with uniform part sizes. Accordingly, we can show that the range of the function ϕ-κ+1 is the set of all nonnegative integers. We also report results about a hypergraph version of competition number and phylogeny number. More... »

PAGES

1-15

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00373-019-02023-4

DOI

http://dx.doi.org/10.1007/s00373-019-02023-4

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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": "Shanghai Jiao Tong University", 
          "id": "https://www.grid.ac/institutes/grid.16821.3c", 
          "name": [
            "School of Mathematical Sciences and MOE-LSC, Shanghai Jiao Tong University, 200240, Shanghai, People\u2019s Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Yaokun", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Shanghai Jiao Tong University", 
          "id": "https://www.grid.ac/institutes/grid.16821.3c", 
          "name": [
            "School of Mathematical Sciences, Shanghai Jiao Tong University, 200240, Shanghai, People\u2019s Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xiong", 
        "givenName": "Yanzhen", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Shanghai Jiao Tong University", 
          "id": "https://www.grid.ac/institutes/grid.16821.3c", 
          "name": [
            "School of Mathematical Sciences, Shanghai Jiao Tong University, 200240, Shanghai, People\u2019s Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zaw", 
        "givenName": "Soesoe", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.dam.2004.02.010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009372262"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0166-218x(98)00058-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013495819"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2008.04.009", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018931869"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2012.05.005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019034349"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2009.06.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022402193"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0070404", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035145686", 
          "https://doi.org/10.1007/bfb0070404"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2009.12.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044704580"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2011.12.017", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048153114"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0603043", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848768"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.7151/dmgt.1893", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1073621218"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.dam.2017.07.018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091212772"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-03-08", 
    "datePublishedReg": "2019-03-08", 
    "description": "Let D be a digraph. The competition graph of D is the graph sharing the same vertex set with D such that two different vertices are adjacent if and only if they have a common out-neighbor in D; the phylogeny graph of D is the competition graph of the digraph obtained from D by adding a loop at every vertex. For any graph G with n vertices, its competition number \u03ba(G) is the least nonnegative integer k such that G is an induced subgraph of the competition graph of an acyclic digraph with n+k vertices, while its phylogeny number \u03d5(G) is the least nonnegative integer p such that G is an induced subgraph of the phylogeny graph of an acyclic digraph with n+p vertices. This paper provides new estimates of the competition numbers and phylogeny numbers of complete multipartite graphs with uniform part sizes. Accordingly, we can show that the range of the function \u03d5-\u03ba+1 is the set of all nonnegative integers. We also report results about a hypergraph version of competition number and phylogeny number.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00373-019-02023-4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136071", 
        "issn": [
          "0911-0119", 
          "1435-5914"
        ], 
        "name": "Graphs and Combinatorics", 
        "type": "Periodical"
      }
    ], 
    "name": "Competition Numbers and Phylogeny Numbers: Uniform Complete Multipartite Graphs", 
    "pagination": "1-15", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0045893b91da79770936e85a15c15fb57e5c8f710a7f7ead800017295162fa72"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00373-019-02023-4"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112634043"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00373-019-02023-4", 
      "https://app.dimensions.ai/details/publication/pub.1112634043"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:18", 
    "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/0000000354_0000000354/records_11704_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00373-019-02023-4"
  }
]
 

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-019-02023-4'

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-019-02023-4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02023-4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00373-019-02023-4'


 

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

101 TRIPLES      21 PREDICATES      35 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00373-019-02023-4 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N0e5f2110b6d743fa8fa07fa870833849
4 schema:citation sg:pub.10.1007/bfb0070404
5 https://doi.org/10.1016/j.dam.2004.02.010
6 https://doi.org/10.1016/j.dam.2008.04.009
7 https://doi.org/10.1016/j.dam.2009.12.001
8 https://doi.org/10.1016/j.dam.2011.12.017
9 https://doi.org/10.1016/j.dam.2012.05.005
10 https://doi.org/10.1016/j.dam.2017.07.018
11 https://doi.org/10.1016/j.disc.2009.06.016
12 https://doi.org/10.1016/s0166-218x(98)00058-4
13 https://doi.org/10.1137/0603043
14 https://doi.org/10.7151/dmgt.1893
15 schema:datePublished 2019-03-08
16 schema:datePublishedReg 2019-03-08
17 schema:description Let D be a digraph. The competition graph of D is the graph sharing the same vertex set with D such that two different vertices are adjacent if and only if they have a common out-neighbor in D; the phylogeny graph of D is the competition graph of the digraph obtained from D by adding a loop at every vertex. For any graph G with n vertices, its competition number κ(G) is the least nonnegative integer k such that G is an induced subgraph of the competition graph of an acyclic digraph with n+k vertices, while its phylogeny number ϕ(G) is the least nonnegative integer p such that G is an induced subgraph of the phylogeny graph of an acyclic digraph with n+p vertices. This paper provides new estimates of the competition numbers and phylogeny numbers of complete multipartite graphs with uniform part sizes. Accordingly, we can show that the range of the function ϕ-κ+1 is the set of all nonnegative integers. We also report results about a hypergraph version of competition number and phylogeny number.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf sg:journal.1136071
22 schema:name Competition Numbers and Phylogeny Numbers: Uniform Complete Multipartite Graphs
23 schema:pagination 1-15
24 schema:productId N2efb1cd6c5844087a1aaeb233fcd7bea
25 N38797b4a6a2043e685e504445703d165
26 N7207d254769c474291a91786195e27ab
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112634043
28 https://doi.org/10.1007/s00373-019-02023-4
29 schema:sdDatePublished 2019-04-11T11:18
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N4ca83b10a78c4053a49d68b3c145b94e
32 schema:url https://link.springer.com/10.1007%2Fs00373-019-02023-4
33 sgo:license sg:explorer/license/
34 sgo:sdDataset articles
35 rdf:type schema:ScholarlyArticle
36 N0e5f2110b6d743fa8fa07fa870833849 rdf:first N6babb51ee5474f22a08d7af3cc89f870
37 rdf:rest Ne3bef6d3fe4e4f608d5d51d59eb2f2fd
38 N2efb1cd6c5844087a1aaeb233fcd7bea schema:name doi
39 schema:value 10.1007/s00373-019-02023-4
40 rdf:type schema:PropertyValue
41 N38797b4a6a2043e685e504445703d165 schema:name readcube_id
42 schema:value 0045893b91da79770936e85a15c15fb57e5c8f710a7f7ead800017295162fa72
43 rdf:type schema:PropertyValue
44 N4ca83b10a78c4053a49d68b3c145b94e schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N6babb51ee5474f22a08d7af3cc89f870 schema:affiliation https://www.grid.ac/institutes/grid.16821.3c
47 schema:familyName Wu
48 schema:givenName Yaokun
49 rdf:type schema:Person
50 N7207d254769c474291a91786195e27ab schema:name dimensions_id
51 schema:value pub.1112634043
52 rdf:type schema:PropertyValue
53 N90b92750f2aa47c18f4e1b4c30045667 schema:affiliation https://www.grid.ac/institutes/grid.16821.3c
54 schema:familyName Zaw
55 schema:givenName Soesoe
56 rdf:type schema:Person
57 Nb2430443ff544328a27e1db9b701a7ab rdf:first N90b92750f2aa47c18f4e1b4c30045667
58 rdf:rest rdf:nil
59 Ne2542657f92348a99e713cdc6f3fe2c4 schema:affiliation https://www.grid.ac/institutes/grid.16821.3c
60 schema:familyName Xiong
61 schema:givenName Yanzhen
62 rdf:type schema:Person
63 Ne3bef6d3fe4e4f608d5d51d59eb2f2fd rdf:first Ne2542657f92348a99e713cdc6f3fe2c4
64 rdf:rest Nb2430443ff544328a27e1db9b701a7ab
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information Systems
70 rdf:type schema:DefinedTerm
71 sg:journal.1136071 schema:issn 0911-0119
72 1435-5914
73 schema:name Graphs and Combinatorics
74 rdf:type schema:Periodical
75 sg:pub.10.1007/bfb0070404 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035145686
76 https://doi.org/10.1007/bfb0070404
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1016/j.dam.2004.02.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009372262
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1016/j.dam.2008.04.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018931869
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1016/j.dam.2009.12.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044704580
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1016/j.dam.2011.12.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048153114
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1016/j.dam.2012.05.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019034349
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1016/j.dam.2017.07.018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091212772
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/j.disc.2009.06.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022402193
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/s0166-218x(98)00058-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013495819
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1137/0603043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848768
95 rdf:type schema:CreativeWork
96 https://doi.org/10.7151/dmgt.1893 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073621218
97 rdf:type schema:CreativeWork
98 https://www.grid.ac/institutes/grid.16821.3c schema:alternateName Shanghai Jiao Tong University
99 schema:name School of Mathematical Sciences and MOE-LSC, Shanghai Jiao Tong University, 200240, Shanghai, People’s Republic of China
100 School of Mathematical Sciences, Shanghai Jiao Tong University, 200240, Shanghai, People’s Republic of China
101 rdf:type schema:Organization
 




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


...