{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:34:56Z","timestamp":1740123296033,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T00:00:00Z","timestamp":1692057600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T00:00:00Z","timestamp":1692057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Rheinland-Pf\u00e4lzische Technische Universit\u00e4t Kaiserslautern-Landau"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The conjecture of Beineke and Harary states that for any two vertices which can be separated by <jats:italic>k<\/jats:italic> vertices and <jats:italic>l<\/jats:italic> edges for <jats:inline-formula><jats:alternatives><jats:tex-math>$$l\\ge 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> but neither by\u00a0<jats:italic>k<\/jats:italic> vertices and <jats:inline-formula><jats:alternatives><jats:tex-math>$$l-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges nor <jats:inline-formula><jats:alternatives><jats:tex-math>$$k-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices and <jats:italic>l<\/jats:italic> edges there are\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$k+l$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>l<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edge-disjoint paths connecting these two vertices of which <jats:inline-formula><jats:alternatives><jats:tex-math>$$k+1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are internally disjoint.In this paper we prove this conjecture for\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$l=2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and every <jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\in \\mathbb {N}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>N<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.We utilize this result to prove that the conjecture holds for all graphs of treewidth at most 3 and all <jats:italic>k<\/jats:italic> and <jats:italic>l<\/jats:italic>.\n<\/jats:p>","DOI":"10.1007\/s10479-023-05527-8","type":"journal-article","created":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T14:02:43Z","timestamp":1692108163000},"page":"107-124","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the mixed connectivity conjecture of Beineke and Harary"],"prefix":"10.1007","volume":"332","author":[{"given":"Sebastian S.","family":"Johann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven O.","family":"Krumke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5605-7637","authenticated-orcid":false,"given":"Manuel","family":"Streicher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,15]]},"reference":[{"issue":"1","key":"5527_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00222-008-0157-3","volume":"176","author":"R Aharoni","year":"2008","unstructured":"Aharoni, R., & Berger, E. (2008). Mengers theorem for infinite graphs. Inventiones Mathematicae, 176(1), 1\u201362.","journal-title":"Inventiones Mathematicae"},{"key":"5527_CR2","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300003806","author":"LW Beineke","year":"1967","unstructured":"Beineke, L. W., & Harary, F. (1967). The connectivity function of a graph. Mathematika. https:\/\/doi.org\/10.1112\/S0025579300003806","journal-title":"Mathematika"},{"key":"5527_CR3","first-page":"21","volume":"2091","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H. L. (1998). A partial k-Arboretum of graphs with bounded treewidth. Theoretical Computer Science, 2091, 21\u201345.","journal-title":"Theoretical Computer Science"},{"key":"5527_CR4","first-page":"35","volume":"30725","author":"\u00c8 Bonnet","year":"2021","unstructured":"Bonnet, \u00c8., & Cabello, S. (2021). The complexity of mixed-connectivity. Annals of Operations Research, 30725, 35.","journal-title":"Annals of Operations Research"},{"key":"5527_CR5","unstructured":"Bornd\u00f6rfer, R., & Karbstein, M. (2012). A Note on Menger\u2019s Theorem for Hypergraphs 12-03. BerlinZIB."},{"key":"5527_CR6","volume-title":"Graph Theory","author":"R Diestel","year":"2000","unstructured":"Diestel, R. (2000). Graph Theory. Springer."},{"key":"5527_CR7","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/bf01375475","volume":"1171","author":"Y Egawa","year":"1991","unstructured":"Egawa, Y., Kaneko, A., & Matsumoto, M. (1991). A mixed version of Menger\u2019s theorem. Combinatorica, 1171, 74. https:\/\/doi.org\/10.1007\/bf01375475","journal-title":"Combinatorica"},{"key":"5527_CR8","doi-asserted-by":"publisher","first-page":"357","DOI":"10.3836\/tjm\/1270127958","volume":"172355","author":"H Enomoto","year":"1994","unstructured":"Enomoto, H., & Kaneko, A. (1994). The condition of Beineke and Harary on edge-disjoint paths some of which are openly disjoint. Tokyo Journal of Mathematics, 172355, 357. https:\/\/doi.org\/10.3836\/tjm\/1270127958","journal-title":"Tokyo Journal of Mathematics"},{"key":"5527_CR9","unstructured":"Erves, R., & Zerovnik, J. (2016). Mixed connectivity of Cartesian graph products and bundles. arXiv:1002.2508"},{"key":"5527_CR10","unstructured":"Johann, S. (2021). On Simultaneous Domination and Mixed Connectivity in Graphs Verlag Dr. Hut. https:\/\/books.google.de\/books?id=NQJ5zgEACAAJ"},{"key":"5527_CR11","doi-asserted-by":"publisher","unstructured":"Mader, W. (1979).Connectivity and Edge-connectivity in Finite Graphs.Surveys in Combinatorics (Proceedings of the Seventh British Combinatorial Conference), London Mathematical Society Lecture Note Series Surveys in combinatorics (proceedings of the seventh british combinatorial conference), london mathematical society lecture note series (\u00a038, 66\u201395). https:\/\/doi.org\/10.1017\/cbo9780511662133.005","DOI":"10.1017\/cbo9780511662133.005"},{"key":"5527_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-019-03175-5","author":"E Sadeghi","year":"2019","unstructured":"Sadeghi, E., & Fan, N. (2019). On the survivable network design problem with mixed connectivity requirements. Annals of Operations Research. https:\/\/doi.org\/10.1007\/s10479-019-03175-5","journal-title":"Annals of Operations Research"},{"key":"5527_CR13","doi-asserted-by":"publisher","unstructured":"Streicher, M. (2021). Uncertainty in Discrete Optimization: Connectivity and Covering PhD ThesisTechnische Universit\u00e4t\u00e4t Kaiserslautern. https:\/\/doi.org\/10.26204\/KLUEDO\/6555","DOI":"10.26204\/KLUEDO\/6555"},{"key":"5527_CR14","volume-title":"Introduction to Graph Theory (2)","author":"DB West","year":"2001","unstructured":"West, D. B. (2001). Introduction to Graph Theory (2). Prentice-Hall."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-023-05527-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-023-05527-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-023-05527-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,27]],"date-time":"2024-02-27T17:19:06Z","timestamp":1709054346000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-023-05527-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,15]]},"references-count":14,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["5527"],"URL":"https:\/\/doi.org\/10.1007\/s10479-023-05527-8","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2023,8,15]]},"assertion":[{"value":"20 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}