Counting Hamiltonian Cycles in the Matroid Basis Graph View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03

AUTHORS

Cristina G. Fernandes, César Hernández-Vélez, José C. de Pina, Jorge Luis Ramírez Alfonsín

ABSTRACT

We present superfactorial and exponential lower bounds on the number of Hamiltonian cycles passing through any edge of the basis graph of generalized Catalan, uniform, and graphic matroids. All lower bounds were obtained by a common general strategy based on counting appropriated cycles of length four in the corresponding matroid basis graph. More... »

PAGES

539-550

References to SciGraph publications

  • 1989-12. Paths and cycles in matroid base graphs in GRAPHS AND COMBINATORICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00373-019-02011-8

    DOI

    http://dx.doi.org/10.1007/s00373-019-02011-8

    DIMENSIONS

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


    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/1117", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Public Health and Health Services", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Medical and Health Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Sao Paulo", 
              "id": "https://www.grid.ac/institutes/grid.11899.38", 
              "name": [
                "Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo, S\u00e3o Paulo, Brazil"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fernandes", 
            "givenName": "Cristina G.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Autonomous University of San Luis Potos\u00ed", 
              "id": "https://www.grid.ac/institutes/grid.412862.b", 
              "name": [
                "Facultad de Ciencias, Universidad Aut\u00f3noma de San Luis Potos\u00ed, San Luis Potosi, M\u00e9xico"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hern\u00e1ndez-V\u00e9lez", 
            "givenName": "C\u00e9sar", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Sao Paulo", 
              "id": "https://www.grid.ac/institutes/grid.11899.38", 
              "name": [
                "Instituto de Matem\u00e1tica e Estat\u00edstica, Universidade de S\u00e3o Paulo, S\u00e3o Paulo, Brazil"
              ], 
              "type": "Organization"
            }, 
            "familyName": "de Pina", 
            "givenName": "Jos\u00e9 C.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Montpellier", 
              "id": "https://www.grid.ac/institutes/grid.121334.6", 
              "name": [
                "IMAG, Univ. Montpellier, CNRS, Montpellier, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ram\u00edrez Alfons\u00edn", 
            "givenName": "Jorge Luis", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0012-365x(88)90177-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001095368"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.aam.2010.04.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001750036"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01788672", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005265231", 
              "https://doi.org/10.1007/bf01788672"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01788672", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005265231", 
              "https://doi.org/10.1007/bf01788672"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(76)90064-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009385906"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0097-3165(03)00122-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010367309"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0097-3165(03)00122-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010367309"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(73)90005-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015323280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(88)90073-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015752657"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(77)90006-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035666361"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.aam.2013.11.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039333946"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejc.2005.01.008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048653134"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tct.1966.1082546", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061578231"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tct.1968.1082765", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061578450"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-03", 
        "datePublishedReg": "2019-03-01", 
        "description": "We present superfactorial and exponential lower bounds on the number of Hamiltonian cycles passing through any edge of the basis graph of generalized Catalan, uniform, and graphic matroids. All lower bounds were obtained by a common general strategy based on counting appropriated cycles of length four in the corresponding matroid basis graph.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00373-019-02011-8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.4482468", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.4478751", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136071", 
            "issn": [
              "0911-0119", 
              "1435-5914"
            ], 
            "name": "Graphs and Combinatorics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "35"
          }
        ], 
        "name": "Counting Hamiltonian Cycles in the Matroid Basis Graph", 
        "pagination": "539-550", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "69ca165dba27562ba325e15c0a0c37a17949d72eb7d504de556168d2f99c06af"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00373-019-02011-8"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1112039721"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00373-019-02011-8", 
          "https://app.dimensions.ai/details/publication/pub.1112039721"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:10", 
        "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/0000000338_0000000338/records_47968_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs00373-019-02011-8"
      }
    ]
     

    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-02011-8'

    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-02011-8'

    Turtle is a human-readable linked data format.

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

    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-02011-8'


     

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

    125 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00373-019-02011-8 schema:about anzsrc-for:11
    2 anzsrc-for:1117
    3 schema:author N14dea05deea5470e8d2068b3088fc887
    4 schema:citation sg:pub.10.1007/bf01788672
    5 https://doi.org/10.1016/0012-365x(88)90073-8
    6 https://doi.org/10.1016/0012-365x(88)90177-x
    7 https://doi.org/10.1016/0095-8956(73)90005-1
    8 https://doi.org/10.1016/0095-8956(76)90064-2
    9 https://doi.org/10.1016/0095-8956(77)90006-5
    10 https://doi.org/10.1016/j.aam.2010.04.005
    11 https://doi.org/10.1016/j.aam.2013.11.003
    12 https://doi.org/10.1016/j.ejc.2005.01.008
    13 https://doi.org/10.1016/s0097-3165(03)00122-5
    14 https://doi.org/10.1109/tct.1966.1082546
    15 https://doi.org/10.1109/tct.1968.1082765
    16 schema:datePublished 2019-03
    17 schema:datePublishedReg 2019-03-01
    18 schema:description We present superfactorial and exponential lower bounds on the number of Hamiltonian cycles passing through any edge of the basis graph of generalized Catalan, uniform, and graphic matroids. All lower bounds were obtained by a common general strategy based on counting appropriated cycles of length four in the corresponding matroid basis graph.
    19 schema:genre research_article
    20 schema:inLanguage en
    21 schema:isAccessibleForFree false
    22 schema:isPartOf N503796752d6f474eb7100efdb1814632
    23 N55705f48af0545bba447e231d6d1e1f3
    24 sg:journal.1136071
    25 schema:name Counting Hamiltonian Cycles in the Matroid Basis Graph
    26 schema:pagination 539-550
    27 schema:productId N4716b2ebe4e14765810819d973994ac4
    28 N53a2bc397b7b47928d3a1987f5a92294
    29 N7fd11fead99040609671b662a674b3f9
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112039721
    31 https://doi.org/10.1007/s00373-019-02011-8
    32 schema:sdDatePublished 2019-04-11T09:10
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N1e0bd80e16c2436aa70686a70a03d1ec
    35 schema:url https://link.springer.com/10.1007%2Fs00373-019-02011-8
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset articles
    38 rdf:type schema:ScholarlyArticle
    39 N04cc99d5691c418ab5b36fab7db1229c schema:affiliation https://www.grid.ac/institutes/grid.412862.b
    40 schema:familyName Hernández-Vélez
    41 schema:givenName César
    42 rdf:type schema:Person
    43 N14dea05deea5470e8d2068b3088fc887 rdf:first Nf62946e510f64da39ac8cbf9f1afd620
    44 rdf:rest Na269b28bf9d24327bcd43952b7b079bd
    45 N190e08225aab4553a05d82d14e22378a rdf:first N5784a58bca97441a83479de68126929e
    46 rdf:rest N99a3bb6c2885463abbc435049bf996bb
    47 N1e0bd80e16c2436aa70686a70a03d1ec schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N4716b2ebe4e14765810819d973994ac4 schema:name dimensions_id
    50 schema:value pub.1112039721
    51 rdf:type schema:PropertyValue
    52 N503796752d6f474eb7100efdb1814632 schema:issueNumber 2
    53 rdf:type schema:PublicationIssue
    54 N53a2bc397b7b47928d3a1987f5a92294 schema:name doi
    55 schema:value 10.1007/s00373-019-02011-8
    56 rdf:type schema:PropertyValue
    57 N55705f48af0545bba447e231d6d1e1f3 schema:volumeNumber 35
    58 rdf:type schema:PublicationVolume
    59 N5784a58bca97441a83479de68126929e schema:affiliation https://www.grid.ac/institutes/grid.11899.38
    60 schema:familyName de Pina
    61 schema:givenName José C.
    62 rdf:type schema:Person
    63 N7fd11fead99040609671b662a674b3f9 schema:name readcube_id
    64 schema:value 69ca165dba27562ba325e15c0a0c37a17949d72eb7d504de556168d2f99c06af
    65 rdf:type schema:PropertyValue
    66 N7ffa81ea2d284b05a0740739a3089481 schema:affiliation https://www.grid.ac/institutes/grid.121334.6
    67 schema:familyName Ramírez Alfonsín
    68 schema:givenName Jorge Luis
    69 rdf:type schema:Person
    70 N99a3bb6c2885463abbc435049bf996bb rdf:first N7ffa81ea2d284b05a0740739a3089481
    71 rdf:rest rdf:nil
    72 Na269b28bf9d24327bcd43952b7b079bd rdf:first N04cc99d5691c418ab5b36fab7db1229c
    73 rdf:rest N190e08225aab4553a05d82d14e22378a
    74 Nf62946e510f64da39ac8cbf9f1afd620 schema:affiliation https://www.grid.ac/institutes/grid.11899.38
    75 schema:familyName Fernandes
    76 schema:givenName Cristina G.
    77 rdf:type schema:Person
    78 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Medical and Health Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:1117 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Public Health and Health Services
    83 rdf:type schema:DefinedTerm
    84 sg:grant.4478751 http://pending.schema.org/fundedItem sg:pub.10.1007/s00373-019-02011-8
    85 rdf:type schema:MonetaryGrant
    86 sg:grant.4482468 http://pending.schema.org/fundedItem sg:pub.10.1007/s00373-019-02011-8
    87 rdf:type schema:MonetaryGrant
    88 sg:journal.1136071 schema:issn 0911-0119
    89 1435-5914
    90 schema:name Graphs and Combinatorics
    91 rdf:type schema:Periodical
    92 sg:pub.10.1007/bf01788672 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005265231
    93 https://doi.org/10.1007/bf01788672
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/0012-365x(88)90073-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015752657
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0012-365x(88)90177-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1001095368
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0095-8956(73)90005-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015323280
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0095-8956(76)90064-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009385906
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0095-8956(77)90006-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035666361
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/j.aam.2010.04.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001750036
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/j.aam.2013.11.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039333946
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/j.ejc.2005.01.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048653134
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/s0097-3165(03)00122-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010367309
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1109/tct.1966.1082546 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061578231
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1109/tct.1968.1082765 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061578450
    116 rdf:type schema:CreativeWork
    117 https://www.grid.ac/institutes/grid.11899.38 schema:alternateName University of Sao Paulo
    118 schema:name Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, Brazil
    119 rdf:type schema:Organization
    120 https://www.grid.ac/institutes/grid.121334.6 schema:alternateName University of Montpellier
    121 schema:name IMAG, Univ. Montpellier, CNRS, Montpellier, France
    122 rdf:type schema:Organization
    123 https://www.grid.ac/institutes/grid.412862.b schema:alternateName Autonomous University of San Luis Potosí
    124 schema:name Facultad de Ciencias, Universidad Autónoma de San Luis Potosí, San Luis Potosi, México
    125 rdf:type schema:Organization
     




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


    ...