Loading…
The (2k-1)-connected multigraphs with at most k-1 disjoint cycles
In 1963, Corradi and Hajnal proved that for all k ≥1 and n ≥3 k , every (simple) graph G on n vertices with minimum degree δ( G )≥2 k contains k disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (...
Saved in:
| Published in: | Combinatorica (Budapest. 1981) 2017-02, Vol.37 (1), p.77-86 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963 |
| container_end_page | 86 |
| container_issue | 1 |
| container_start_page | 77 |
| container_title | Combinatorica (Budapest. 1981) |
| container_volume | 37 |
| creator | Kierstead, Henry A. Kostochka, Alexandr V. Yeager, Elyse C. |
| description | In 1963, Corradi and Hajnal proved that for all
k
≥1 and
n
≥3
k
, every (simple) graph
G
on n vertices with minimum degree δ(
G
)≥2
k
contains
k
disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2
k
—1)-connected multigraphs do not contain
k
disjoint cycles? Recently, the authors characterized the simple graphs
G
with minimum degree δ(
G
)≥2
k
—1 that do not contain
k
disjoint cycles. We use this result to answer Dirac's question in full. |
| doi_str_mv | 10.1007/s00493-015-3291-8 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_1890804539</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1890804539</sourcerecordid><originalsourceid>FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963</originalsourceid><addsrcrecordid>eNp1kDFPwzAQRi0EEqXwA9gsscBgOPucxB6rigJSJZYyW4lzbVPapNiuUP89qcLAwnTLe99Jj7FbCY8SoHiKANqiAJkJVFYKc8ZGUqMVuZXqnI1AgRU2N3jJrmLcAIBBmY3YZLEmfq8-hXwQvmtb8olqvjtsU7MK5X4d-XeT1rxMfNfFxHuO103cdE2buD_6LcVrdrEst5Fufu-YfcyeF9NXMX9_eZtO5sKjzJOwlbeZMWpprcZcKevJmLKiyqDOau9BFQUCYeFJk0QsiDKZ175Cj9rbHMfsbtjdh-7rQDG5TXcIbf_SSWPBgM7Q9pQcKB-6GAMt3T40uzIcnQR3KuWGUq4v5U6lnOkdNTixZ9sVhT_L_0o_dfZpQQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1890804539</pqid></control><display><type>article</type><title>The (2k-1)-connected multigraphs with at most k-1 disjoint cycles</title><source>Springer Nature</source><creator>Kierstead, Henry A. ; Kostochka, Alexandr V. ; Yeager, Elyse C.</creator><creatorcontrib>Kierstead, Henry A. ; Kostochka, Alexandr V. ; Yeager, Elyse C.</creatorcontrib><description>In 1963, Corradi and Hajnal proved that for all
k
≥1 and
n
≥3
k
, every (simple) graph
G
on n vertices with minimum degree δ(
G
)≥2
k
contains
k
disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2
k
—1)-connected multigraphs do not contain
k
disjoint cycles? Recently, the authors characterized the simple graphs
G
with minimum degree δ(
G
)≥2
k
—1 that do not contain
k
disjoint cycles. We use this result to answer Dirac's question in full.</description><identifier>ISSN: 0209-9683</identifier><identifier>EISSN: 1439-6912</identifier><identifier>DOI: 10.1007/s00493-015-3291-8</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Banking industry ; Combinatorics ; Graph theory ; Mathematics ; Mathematics and Statistics ; Original Paper</subject><ispartof>Combinatorica (Budapest. 1981), 2017-02, Vol.37 (1), p.77-86</ispartof><rights>János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg 2015</rights><rights>Copyright Springer Science & Business Media 2017</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963</citedby><cites>FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Kierstead, Henry A.</creatorcontrib><creatorcontrib>Kostochka, Alexandr V.</creatorcontrib><creatorcontrib>Yeager, Elyse C.</creatorcontrib><title>The (2k-1)-connected multigraphs with at most k-1 disjoint cycles</title><title>Combinatorica (Budapest. 1981)</title><addtitle>Combinatorica</addtitle><description>In 1963, Corradi and Hajnal proved that for all
k
≥1 and
n
≥3
k
, every (simple) graph
G
on n vertices with minimum degree δ(
G
)≥2
k
contains
k
disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2
k
—1)-connected multigraphs do not contain
k
disjoint cycles? Recently, the authors characterized the simple graphs
G
with minimum degree δ(
G
)≥2
k
—1 that do not contain
k
disjoint cycles. We use this result to answer Dirac's question in full.</description><subject>Banking industry</subject><subject>Combinatorics</subject><subject>Graph theory</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Original Paper</subject><issn>0209-9683</issn><issn>1439-6912</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNp1kDFPwzAQRi0EEqXwA9gsscBgOPucxB6rigJSJZYyW4lzbVPapNiuUP89qcLAwnTLe99Jj7FbCY8SoHiKANqiAJkJVFYKc8ZGUqMVuZXqnI1AgRU2N3jJrmLcAIBBmY3YZLEmfq8-hXwQvmtb8olqvjtsU7MK5X4d-XeT1rxMfNfFxHuO103cdE2buD_6LcVrdrEst5Fufu-YfcyeF9NXMX9_eZtO5sKjzJOwlbeZMWpprcZcKevJmLKiyqDOau9BFQUCYeFJk0QsiDKZ175Cj9rbHMfsbtjdh-7rQDG5TXcIbf_SSWPBgM7Q9pQcKB-6GAMt3T40uzIcnQR3KuWGUq4v5U6lnOkdNTixZ9sVhT_L_0o_dfZpQQ</recordid><startdate>20170201</startdate><enddate>20170201</enddate><creator>Kierstead, Henry A.</creator><creator>Kostochka, Alexandr V.</creator><creator>Yeager, Elyse C.</creator><general>Springer Berlin Heidelberg</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20170201</creationdate><title>The (2k-1)-connected multigraphs with at most k-1 disjoint cycles</title><author>Kierstead, Henry A. ; Kostochka, Alexandr V. ; Yeager, Elyse C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Banking industry</topic><topic>Combinatorics</topic><topic>Graph theory</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Original Paper</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kierstead, Henry A.</creatorcontrib><creatorcontrib>Kostochka, Alexandr V.</creatorcontrib><creatorcontrib>Yeager, Elyse C.</creatorcontrib><collection>CrossRef</collection><jtitle>Combinatorica (Budapest. 1981)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kierstead, Henry A.</au><au>Kostochka, Alexandr V.</au><au>Yeager, Elyse C.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The (2k-1)-connected multigraphs with at most k-1 disjoint cycles</atitle><jtitle>Combinatorica (Budapest. 1981)</jtitle><stitle>Combinatorica</stitle><date>2017-02-01</date><risdate>2017</risdate><volume>37</volume><issue>1</issue><spage>77</spage><epage>86</epage><pages>77-86</pages><issn>0209-9683</issn><eissn>1439-6912</eissn><abstract>In 1963, Corradi and Hajnal proved that for all
k
≥1 and
n
≥3
k
, every (simple) graph
G
on n vertices with minimum degree δ(
G
)≥2
k
contains
k
disjoint cycles. The same year, Dirac described the 3-connected multigraphs not containing two disjoint cycles and asked the more general question: Which (2
k
—1)-connected multigraphs do not contain
k
disjoint cycles? Recently, the authors characterized the simple graphs
G
with minimum degree δ(
G
)≥2
k
—1 that do not contain
k
disjoint cycles. We use this result to answer Dirac's question in full.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s00493-015-3291-8</doi><tpages>10</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0209-9683 |
| ispartof | Combinatorica (Budapest. 1981), 2017-02, Vol.37 (1), p.77-86 |
| issn | 0209-9683 1439-6912 |
| language | eng |
| recordid | cdi_proquest_journals_1890804539 |
| source | Springer Nature |
| subjects | Banking industry Combinatorics Graph theory Mathematics Mathematics and Statistics Original Paper |
| title | The (2k-1)-connected multigraphs with at most k-1 disjoint cycles |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T01%3A59%3A40IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20(2k-1)-connected%20multigraphs%20with%20at%20most%20k-1%20disjoint%20cycles&rft.jtitle=Combinatorica%20(Budapest.%201981)&rft.au=Kierstead,%20Henry%20A.&rft.date=2017-02-01&rft.volume=37&rft.issue=1&rft.spage=77&rft.epage=86&rft.pages=77-86&rft.issn=0209-9683&rft.eissn=1439-6912&rft_id=info:doi/10.1007/s00493-015-3291-8&rft_dat=%3Cproquest_cross%3E1890804539%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c316t-9bc95882f99436229ce88abeb8345dcc027730e37ce4e1337ee516dcb3c34c963%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1890804539&rft_id=info:pmid/&rfr_iscdi=true |