{"entities":{"Q1892839":{"pageid":1903581,"ns":120,"title":"Item:Q1892839","lastrevid":43400396,"modified":"2025-07-25T11:44:03Z","type":"item","id":"Q1892839","labels":{"en":{"language":"en","value":"Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \\(K_{1,d}\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 767688"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892839$D224C9A7-557D-4275-967C-C3662BF6D209","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9464a8aaa2fd56f5b2b359d43ab50092e98065e7","datavalue":{"value":{"text":"Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \\(K_{1,d}\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1892839$C301B841-8166-4F9E-B226-C468E5CEF20E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"39689651da166189ec575fe0a345bdea384cd152","datavalue":{"value":"0821.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892839$A1DB2F13-48C5-46FA-9D10-2B2BDFCAF874","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c84290e2aa59f5e72197dc6c42e23718498784e5","datavalue":{"value":{"entity-type":"item","numeric-id":704840,"id":"Q704840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892839$CB69A995-B995-46CF-ADDF-7D5F308F0A95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6933def1f445e21685d50fc13bd3cfacda780e57","datavalue":{"value":{"entity-type":"item","numeric-id":273170,"id":"Q273170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892839$040DEA39-3BD8-485C-9858-143A06A1389A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892839$F760D5F4-F2B5-482B-89F2-C8C07733514C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89939404571a8a457f4efe42bf31156c65cd7105","datavalue":{"value":{"time":"+1995-07-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1892839$53AE9F9A-A78C-4186-8902-3026A1768783","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6aa691936e05b2abdd90b47fb86836b15d88025c","datavalue":{"value":"Let \\(f_{k, d}(n)\\) denote the largest integer \\(m\\) such that every \\(k\\)- connected graph on \\(n\\) vertices with maximum degree \\(d\\) contains a cycle of length at least \\(m\\), and \\(g_{k, d}(n)\\) denote the largest integer \\(m\\) such that every \\(k\\)-connected \\(K_{1,d+ 1}\\)-free graph on \\(n\\) vertices contains a cycle of length at least \\(m\\). Then \\(f_{k, d}(n)\\geq g_{k,d}(n)\\). \\textit{J. A. Bondy} and the reviewer [Can. J. Math. 32, 1325-1332 (1980; Zbl 0409.05037)] showed \\(f_{2, d}\\sim 4\\log_{d- 1} n\\) and the authors in [Longest cycles in 3-connected graphs of bounded maximum degree, Lect. Notes Pure Appl. Math. 139, 237-254 (1992; Zbl 0790.05048)] proved \\(c_ 1 n^{c_ 2}\\geq f_{3, d}(n)\\geq n^{c_ 3}/2\\) for specified constants \\(c_ 1\\), \\(c_ 2\\) and \\(c_ 3\\). \\textit{J. A. Bondy} [Basic graph theory: paths and circuits, in ``Handbook of combinatorics'' (R. L. Graham, M. Gr\u00f6tschel and L. Lovasz, eds.), North Holland, Amsterdam, 1995, to appear] asked if analogous results hold for \\(g_{2, 2}(n)\\) and \\(g_{3, 2}(n)\\). \\textit{H. J. Broersma}, \\textit{J. van den Heuvel}, \\textit{H. A. Jung} and \\textit{H. J. Veldman} [Graphs Comb. 9, No. 1, 3-17 (1993; Zbl 0778.05047)] showed \\(g_{2, d}(n)\\geq c_ 4+ 4\\log_ d n\\) for a constant \\(c_ 4\\) and for all \\(d\\geq 2\\). Here the authors prove \\(g_{3, d}(n)\\geq n^{c_ 5}/2\\), where \\(c_ 5= 1/(\\log_ 2 6+ 2\\log_ 2(2d+ 1))\\), for all \\(d\\geq 1\\). The arguments of Broersma et al. and the present authors depend on the following conjecture: There exists a function \\(h(d, k)\\) such that every \\(k\\)- connected \\(K_{1, d}\\)-free graph has a \\(k\\)-connected spanning subgraph with maximum degree at most \\(h(d, k)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892839$A8EE0C38-EDF8-4FC3-A6C0-A16271B71194","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892839$5D95C9A2-3655-423B-9116-A655CCB6B2FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892839$157A5CBA-365A-4351-88BF-E766C92BF78F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"882bb58f9a79e7554ebd714913d965e3e0d85125","datavalue":{"value":"767688","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892839$9A575B03-4250-47FA-8AA3-64F61BE9F0B3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8d5f3b694f8f66eb4b53fd7e78857c6731e3b3b","datavalue":{"value":"long cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892839$99A2BEF1-2ACE-4A51-A121-3DD86F122D58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ad842ad959da83378064b3e3e21d1fa80e76ac0","datavalue":{"value":"bounded degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892839$EB26DB28-8790-48A0-9CCC-A91381F40D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61f00c95720f5313d1677b58b42c24752ec77eb1","datavalue":{"value":"\\(k\\)-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892839$C7AA666E-30C0-4C8A-B6C0-92639F496CDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892839$9BB855F0-2DA7-4604-A2B2-88C6BB12FFC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bcb88e4835cfef6b70b1d60481bd40424864103","datavalue":{"value":"spanning subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892839$2EB94AF7-120B-4B62-A244-45CDE499B0C3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892839$F96DDAAF-8331-4602-82F5-31F8F585D75F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892839$3DC45271-D023-457C-B0E5-1CA6D290D2BE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"85aa7327a0ab271961e271448ff5208284b0dfbf","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1013","type":"string"},"datatype":"url"},"type":"statement","id":"Q1892839$998C7C21-3F72-4AC7-B105-68B292D311CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"583ed5b6776f291ecab5c121ac82904c09ed9858","datavalue":{"value":"W2036217110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892839$7C82AC04-A909-4627-96A1-F713C72176BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79b4ff0fcb5bc154325ddc86c8e71285aec15f00","datavalue":{"value":"10.1006/JCTB.1995.1013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892839$E067FFC5-CDE5-462B-A033-53234B09C3E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bff4850e4676542c07bee36b285f1dd60863352","datavalue":{"value":{"entity-type":"item","numeric-id":4388360,"id":"Q4388360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fe6db538a1e3049955aa07d2218b82e26b1cd65","datavalue":{"value":{"amount":"+0.910681","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$44669AA1-637E-45F9-AAC6-9A26A2F83215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccfa4866094e7021f566ced7e2ab57ea63391ba6","datavalue":{"value":{"entity-type":"item","numeric-id":1122589,"id":"Q1122589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74851331fb6cf8f369a90ec019abb12f3d4e7093","datavalue":{"value":{"amount":"+0.90904105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$8F5E18A2-5AEA-40D4-A57C-E5226FA82E7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3a2323daf562c3281010eb0a58eafc340ca7d7b","datavalue":{"value":{"entity-type":"item","numeric-id":1850624,"id":"Q1850624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c067d236a81a5e7d4c2476b537688224f0415926","datavalue":{"value":{"amount":"+0.90398484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$AD8D88A6-BAC7-44CE-BBB6-8C57A8994622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"974ea7bdb8ce635740d0e30feee8d331791fc0fc","datavalue":{"value":{"entity-type":"item","numeric-id":4294581,"id":"Q4294581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc74cbcc4a6acc1c44610376d714892f94f29ec1","datavalue":{"value":{"amount":"+0.9026866","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$D3526D60-9306-4BDB-9F44-35620E6652B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4c11977cc178cee0cae18dcb99aeec326bc3011","datavalue":{"value":{"entity-type":"item","numeric-id":3136994,"id":"Q3136994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58e4ccc0c80899209c4e4068b5135af683bd1f14","datavalue":{"value":{"amount":"+0.9024794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$1DD520CC-02E7-444B-9B8B-BF78E2DEC2D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4a5c2c883b2b62b37161ceb06f24efe46e16a5d","datavalue":{"value":{"entity-type":"item","numeric-id":1978141,"id":"Q1978141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a38d2cfdbf569711e2d333905a84046d3026ed60","datavalue":{"value":{"amount":"+0.89540255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$9202B544-33E3-4CF0-B8A4-2CAC19782C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"520a27acf25205a8ee358af9fe0402d8a2f127e8","datavalue":{"value":{"entity-type":"item","numeric-id":749554,"id":"Q749554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da3919d37bb90756c5d9d826fa5c337da6edd04","datavalue":{"value":{"amount":"+0.89432883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$0C314D4A-4A21-4B50-A5CC-34D994F5B73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82f23d24a33ed66be599c099c7633f7ee6e3bd80","datavalue":{"value":{"entity-type":"item","numeric-id":3718746,"id":"Q3718746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b11eae0ba349d847b82672d6aa01dcd57c74d8b2","datavalue":{"value":{"amount":"+0.88974637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$2BD17662-F850-4B4B-B3A7-E81D6C3D46FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82aaddd1e810b7cc0b1daf94b52c9f6c505ff068","datavalue":{"value":{"entity-type":"item","numeric-id":1826952,"id":"Q1826952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26ffcd8c2a6bfd869bc1d3ca257f9fefc99e5e07","datavalue":{"value":{"amount":"+0.8888102","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$F954BED9-A4C7-4A1F-8D64-8191F0F81AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421662f821f3aee5aa33ffc26f9bef5c9aefb7f2","datavalue":{"value":{"entity-type":"item","numeric-id":4542177,"id":"Q4542177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8a639af37e19d6955f34806058dd76d4edfe6ad","datavalue":{"value":{"amount":"+0.886873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1892839$107B086F-9938-4334-B227-C698DA0BF039","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1892839","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1892839"}}}}}