On Upper Total Domination Versus Upper Domination in Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-06

AUTHORS

Enqiang Zhu, Chanjuan Liu, Fei Deng, Yongsheng Rao

ABSTRACT

A total dominating set of a graph G is a dominating set S of G such that the subgraph induced by S contains no isolated vertex, where a dominating set of G is a set of vertices of G such that each vertex in V(G)\S has a neighbor in S. A (total) dominating set S is said to be minimal if S\{v} is not a (total) dominating set for every v∈S. The upper total domination number Γt(G) and the upper domination number Γ(G) are the maximum cardinalities of a minimal total dominating set and a minimal dominating set of G, respectively. For every graph G without isolated vertices, it is known that Γt(G)≤2Γ(G). The case in which Γt(G)Γ(G)=2 has been studied in Cyman et al. (Graphs Comb 34:261–276, 2018), which focused on the characterization of the connected cubic graphs and proposed one problem to be solved and two questions to be answered in terms of the value of Γt(G)Γ(G). In this paper, we solve this problem, i.e., the characterization of the subcubic graphs G that satisfy Γt(G)Γ(G)=2, by constructing a class of subcubic graphs, which we call triangle-trees. Moreover, we show that the answers to the two questions are negative by constructing connected cubic graphs G that satisfy Γt(G)Γ(G)>32 and a class of regular non-complete graphs G that satisfy Γt(G)Γ(G)=2. More... »

PAGES

1-12

References to SciGraph publications

  • 2018-01. Total Domination Versus Domination in Cubic Graphs in GRAPHS AND COMBINATORICS
  • 2013-12. Minimum Dominating Sets in Scale-Free Network Ensembles in SCIENTIFIC REPORTS
  • 2008-07. On the upper total domination number of Cartesian products of graphs in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00373-019-02029-y

    DOI

    http://dx.doi.org/10.1007/s00373-019-02029-y

    DIMENSIONS

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


    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": "Guangzhou University", 
              "id": "https://www.grid.ac/institutes/grid.411863.9", 
              "name": [
                "Institute of Computing Science and Technology, Guangzhou University, 510006, Guangzhou, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhu", 
            "givenName": "Enqiang", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Dalian University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.30055.33", 
              "name": [
                "School of Computer Science and Technology, Dalian University of Technology, 116024, Dalian, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Liu", 
            "givenName": "Chanjuan", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Chengdu University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.411288.6", 
              "name": [
                "College of Network Security, Chengdu University of Technology, 610059, Chengdu, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deng", 
            "givenName": "Fei", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Guangzhou University", 
              "id": "https://www.grid.ac/institutes/grid.411863.9", 
              "name": [
                "Institute of Computing Science and Technology, Guangzhou University, 510006, Guangzhou, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rao", 
            "givenName": "Yongsheng", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1073/pnas.1311231111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003100867"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/srep01736", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003253871", 
              "https://doi.org/10.1038/srep01736"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.3230100304", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010938726"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2016.01.017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024244689"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2014.03.013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025836848"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-007-9099-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032433762", 
              "https://doi.org/10.1007/s10878-007-9099-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2007.12.044", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044594902"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.21725", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051153362"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2013.303", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061754442"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898719796", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557270"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00373-017-1865-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1099721177", 
              "https://doi.org/10.1007/s00373-017-1865-5"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03-06", 
        "datePublishedReg": "2019-03-06", 
        "description": "A total dominating set of a graph G is a dominating set S of G such that the subgraph induced by S contains no isolated vertex, where a dominating set of G is a set of vertices of G such that each vertex in V(G)\\S has a neighbor in S. A (total) dominating set S is said to be minimal if S\\{v} is not a (total) dominating set for every v\u2208S. The upper total domination number \u0393t(G) and the upper domination number \u0393(G) are the maximum cardinalities of a minimal total dominating set and a minimal dominating set of G, respectively. For every graph G without isolated vertices, it is known that \u0393t(G)\u22642\u0393(G). The case in which \u0393t(G)\u0393(G)=2 has been studied in Cyman et al. (Graphs Comb 34:261\u2013276, 2018), which focused on the characterization of the connected cubic graphs and proposed one problem to be solved and two questions to be answered in terms of the value of \u0393t(G)\u0393(G). In this paper, we solve this problem, i.e., the characterization of the subcubic graphs G that satisfy \u0393t(G)\u0393(G)=2, by constructing a class of subcubic graphs, which we call triangle-trees. Moreover, we show that the answers to the two questions are negative by constructing connected cubic graphs G that satisfy \u0393t(G)\u0393(G)>32 and a class of regular non-complete graphs G that satisfy \u0393t(G)\u0393(G)=2.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00373-019-02029-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136071", 
            "issn": [
              "0911-0119", 
              "1435-5914"
            ], 
            "name": "Graphs and Combinatorics", 
            "type": "Periodical"
          }
        ], 
        "name": "On Upper Total Domination Versus Upper Domination in Graphs", 
        "pagination": "1-12", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "ce16d4faa8c9bda170480deb83af08b163bbf35183e77bb911e9cfcc996103c7"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00373-019-02029-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112540586"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00373-019-02029-y", 
          "https://app.dimensions.ai/details/publication/pub.1112540586"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:14", 
        "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/0000000353_0000000353/records_45374_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00373-019-02029-y"
      }
    ]
     

    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-02029-y'

    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-02029-y'

    Turtle is a human-readable linked data format.

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

    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-02029-y'


     

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

    114 TRIPLES      21 PREDICATES      35 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00373-019-02029-y schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nd33e523baf1d4229b91d4544f9953bda
    4 schema:citation sg:pub.10.1007/s00373-017-1865-5
    5 sg:pub.10.1007/s10878-007-9099-8
    6 sg:pub.10.1038/srep01736
    7 https://doi.org/10.1002/jgt.21725
    8 https://doi.org/10.1002/net.3230100304
    9 https://doi.org/10.1016/j.dam.2014.03.013
    10 https://doi.org/10.1016/j.disc.2007.12.044
    11 https://doi.org/10.1016/j.disc.2016.01.017
    12 https://doi.org/10.1073/pnas.1311231111
    13 https://doi.org/10.1109/tpds.2013.303
    14 https://doi.org/10.1137/1.9780898719796
    15 schema:datePublished 2019-03-06
    16 schema:datePublishedReg 2019-03-06
    17 schema:description A total dominating set of a graph G is a dominating set S of G such that the subgraph induced by S contains no isolated vertex, where a dominating set of G is a set of vertices of G such that each vertex in V(G)\S has a neighbor in S. A (total) dominating set S is said to be minimal if S\{v} is not a (total) dominating set for every v∈S. The upper total domination number Γt(G) and the upper domination number Γ(G) are the maximum cardinalities of a minimal total dominating set and a minimal dominating set of G, respectively. For every graph G without isolated vertices, it is known that Γt(G)≤2Γ(G). The case in which Γt(G)Γ(G)=2 has been studied in Cyman et al. (Graphs Comb 34:261–276, 2018), which focused on the characterization of the connected cubic graphs and proposed one problem to be solved and two questions to be answered in terms of the value of Γt(G)Γ(G). In this paper, we solve this problem, i.e., the characterization of the subcubic graphs G that satisfy Γt(G)Γ(G)=2, by constructing a class of subcubic graphs, which we call triangle-trees. Moreover, we show that the answers to the two questions are negative by constructing connected cubic graphs G that satisfy Γt(G)Γ(G)>32 and a class of regular non-complete graphs G that satisfy Γt(G)Γ(G)=2.
    18 schema:genre research_article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf sg:journal.1136071
    22 schema:name On Upper Total Domination Versus Upper Domination in Graphs
    23 schema:pagination 1-12
    24 schema:productId N1a54ea57245647b6b15855ff2113678b
    25 N33f8417f05ec45379bfeab5d6529df24
    26 Nfaa1e0803d2d4732a377e00565fed179
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112540586
    28 https://doi.org/10.1007/s00373-019-02029-y
    29 schema:sdDatePublished 2019-04-11T11:14
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N1c2faaf356dc4a3aa1212abf10d857d4
    32 schema:url https://link.springer.com/10.1007%2Fs00373-019-02029-y
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset articles
    35 rdf:type schema:ScholarlyArticle
    36 N02d025d5e3064118b11898fffc44ee30 schema:affiliation https://www.grid.ac/institutes/grid.411863.9
    37 schema:familyName Zhu
    38 schema:givenName Enqiang
    39 rdf:type schema:Person
    40 N1a54ea57245647b6b15855ff2113678b schema:name doi
    41 schema:value 10.1007/s00373-019-02029-y
    42 rdf:type schema:PropertyValue
    43 N1c2faaf356dc4a3aa1212abf10d857d4 schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N33f8417f05ec45379bfeab5d6529df24 schema:name dimensions_id
    46 schema:value pub.1112540586
    47 rdf:type schema:PropertyValue
    48 N547c563617504c6da3d0bf31e614e75d schema:affiliation https://www.grid.ac/institutes/grid.411288.6
    49 schema:familyName Deng
    50 schema:givenName Fei
    51 rdf:type schema:Person
    52 N551cc1fb61f14417b085b192da62ce9d rdf:first N924db178c51e407f89fa4d515f15a45a
    53 rdf:rest Nbb8ebf7f9c2d43938e9a9535c4d2e114
    54 N840272dce77944cf87b15ba628b8c3b7 schema:affiliation https://www.grid.ac/institutes/grid.411863.9
    55 schema:familyName Rao
    56 schema:givenName Yongsheng
    57 rdf:type schema:Person
    58 N924db178c51e407f89fa4d515f15a45a schema:affiliation https://www.grid.ac/institutes/grid.30055.33
    59 schema:familyName Liu
    60 schema:givenName Chanjuan
    61 rdf:type schema:Person
    62 Nbb8ebf7f9c2d43938e9a9535c4d2e114 rdf:first N547c563617504c6da3d0bf31e614e75d
    63 rdf:rest Nfed2b512eb7249798a4adfe9a23cd5ef
    64 Nd33e523baf1d4229b91d4544f9953bda rdf:first N02d025d5e3064118b11898fffc44ee30
    65 rdf:rest N551cc1fb61f14417b085b192da62ce9d
    66 Nfaa1e0803d2d4732a377e00565fed179 schema:name readcube_id
    67 schema:value ce16d4faa8c9bda170480deb83af08b163bbf35183e77bb911e9cfcc996103c7
    68 rdf:type schema:PropertyValue
    69 Nfed2b512eb7249798a4adfe9a23cd5ef rdf:first N840272dce77944cf87b15ba628b8c3b7
    70 rdf:rest rdf:nil
    71 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Mathematical Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Pure Mathematics
    76 rdf:type schema:DefinedTerm
    77 sg:journal.1136071 schema:issn 0911-0119
    78 1435-5914
    79 schema:name Graphs and Combinatorics
    80 rdf:type schema:Periodical
    81 sg:pub.10.1007/s00373-017-1865-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099721177
    82 https://doi.org/10.1007/s00373-017-1865-5
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/s10878-007-9099-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032433762
    85 https://doi.org/10.1007/s10878-007-9099-8
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1038/srep01736 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003253871
    88 https://doi.org/10.1038/srep01736
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1002/jgt.21725 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051153362
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1002/net.3230100304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010938726
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/j.dam.2014.03.013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025836848
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/j.disc.2007.12.044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044594902
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/j.disc.2016.01.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024244689
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1073/pnas.1311231111 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003100867
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1109/tpds.2013.303 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061754442
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1137/1.9780898719796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557270
    105 rdf:type schema:CreativeWork
    106 https://www.grid.ac/institutes/grid.30055.33 schema:alternateName Dalian University of Technology
    107 schema:name School of Computer Science and Technology, Dalian University of Technology, 116024, Dalian, China
    108 rdf:type schema:Organization
    109 https://www.grid.ac/institutes/grid.411288.6 schema:alternateName Chengdu University of Technology
    110 schema:name College of Network Security, Chengdu University of Technology, 610059, Chengdu, China
    111 rdf:type schema:Organization
    112 https://www.grid.ac/institutes/grid.411863.9 schema:alternateName Guangzhou University
    113 schema:name Institute of Computing Science and Technology, Guangzhou University, 510006, Guangzhou, China
    114 rdf:type schema:Organization
     




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


    ...