{"entities":{"Q1910587":{"pageid":1921329,"ns":120,"title":"Item:Q1910587","lastrevid":71138043,"modified":"2026-04-13T19:44:09Z","type":"item","id":"Q1910587","labels":{"en":{"language":"en","value":"On independent cycles and edges in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 858119"}},"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":"Q1910587$8145875E-0214-4758-B44A-FC81A47E9448","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82d6077f6179079440d2ff3fc24c3cef3cb17794","datavalue":{"value":{"text":"On independent cycles and edges in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1910587$384BC0FF-7F4E-455F-9265-06AB6A4F204A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"080e42b7064841bb89b64e6c906acb279ddad92e","datavalue":{"value":"0844.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910587$75F01D7C-721F-480F-AE15-601234A99455","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f00bbf273907ef77768aed6216016647becc865b","datavalue":{"value":"10.1016/0012-365X(94)00275-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910587$63129773-85FC-4A8F-BDA7-DA4A44364BF8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$7BE273CC-23E6-4592-BFA5-EF6D3028A7EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a92f509af93037a96d254cb773843378ccf92fff","datavalue":{"value":{"time":"+1996-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1910587$979BC55E-A578-421F-8874-DA4C87EB536B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92f1c2bfcdae3d92c3673cdb1b9e69a4318c24d3","datavalue":{"value":"Denote by \\(\\langle n\\rangle\\) the complete graph \\(K_n\\), by \\(\\langle p, q\\rangle\\) the complete bipartite graph \\(K_{pq}\\), and by \\(\\langle\\langle p\\rangle, q\\rangle\\) the graph obtained from \\(\\langle p, q\\rangle\\) by converting the \\(p\\)-vertex set to \\(K_p\\). For positive integers \\(n\\) and \\(k\\), let \\(f(n, k)\\) be the number of edges of the graph \\(\\langle\\langle 2k- 1\\rangle, n- 2k+ 1\\rangle\\) and \\(g(n, k)\\) the number of edges of the graph obtained from \\(\\langle 3k- 1\\rangle\\) by attaching \\(n- 3k+ 1\\) pendant edges.   \\textit{P. Justesen} [Ann. Discrete Math. 41, 299-305 (1989; Zbl 0673.05065)] proved that, for any integer \\(k\\geq 2\\), if \\(G\\) is a graph on \\(n\\) vertices such that \\(n\\geq k\\) and  \\[ e(G)\\geq \\max\\{f(n, k), g(n, k)+ 1\\}, \\]  then \\(G\\) contains \\(k\\) vertex-disjoint (``independent'') cycles or \\(G\\simeq \\langle\\langle 2k- 1\\rangle, n- 2k+ 1\\rangle\\). Using Justesen's argument, the author extends his result by determining the corresponding extremal graphs, i.e., the graphs \\(G\\) with \\(e(G)= \\max\\{f(n, k), g(n, k)\\}\\), which do not contain \\(k\\) independent cycles. A modification of the same proof leads to the solution of the following problem: For integers \\(k\\), \\(s\\) with \\(0\\leq s\\leq k\\) and \\(k\\geq 2\\), let \\({\\mathcal G}(n, k, s)\\) be the class of graphs on \\(n\\) vertices not containing \\(k\\) independent subgraphs of which \\(k- 2\\) are cycles and the rest \\(K_2\\)'s. Determine those graphs in \\({\\mathcal G}(n, k, s)\\) with the maximum number of edges for \\(n\\geq 3k- s\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910587$7FAE1D25-50D6-4E41-AEB3-A6BCB23E822A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$1489273A-B4AA-4850-8CF2-E6B99D371723","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910587$3C3FAE37-C432-481B-B2D1-920F36798CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910587$2DF991EE-6208-4E0E-83C3-EA0D7F5EFC70","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3297c5d8c40ef98bd8a034ed072620c37ce81ac2","datavalue":{"value":"858119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1910587$1E85D389-9C26-4341-86EC-68B3CAC2D9BC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910587$BF6B206C-EE2E-458F-849F-8AFACAADF93F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcf5c6fbb0a6501cca12c8204b4d5b7cc6fd5323","datavalue":{"value":"independent cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1910587$010D7CBF-8016-40B4-86EF-08639B29B8B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ea6c9e988b1a5ccaf11509582e9469b2e708609","datavalue":{"value":{"entity-type":"item","numeric-id":689954,"id":"Q689954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$5B5142DE-63AD-4EED-85FA-E74B63DC4A46","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":"Q1910587$A35FD87C-177A-4C78-B77E-EA93BB45F75F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$AED23DB1-1EEA-4C54-AF28-93C1AE0966DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5955caa91359ba578c004a79981e6b39abcfdaa2","datavalue":{"value":{"entity-type":"item","numeric-id":5728985,"id":"Q5728985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$D4BF36AF-38AE-4010-B3B6-E5547E3DCB72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14dcc9c96f6c72fbc9a4feb8a83dc5eacad8748","datavalue":{"value":{"entity-type":"item","numeric-id":3265306,"id":"Q3265306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$79BE4D86-EDF3-4871-9B79-178C39C9082B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"063b268fbbe2172df3c2899cea0bcb36718a4486","datavalue":{"value":{"entity-type":"item","numeric-id":5342984,"id":"Q5342984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$37E2A64D-71C7-4D45-A727-B24BB183ADE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b703a7e0e90395fff5f324db0695df95a439639f","datavalue":{"value":{"entity-type":"item","numeric-id":3826605,"id":"Q3826605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$651ECBEE-73EC-4703-A77D-25B2DC7BC555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9186d2c19740f40654f830facd61d9d49a450028","datavalue":{"value":{"entity-type":"item","numeric-id":4775880,"id":"Q4775880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1910587$7ABF22D0-2A95-4846-8019-AF3CA1E03AB6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69b7f571dedcac893de662c5695d8ef0947b3017","datavalue":{"value":{"entity-type":"item","numeric-id":3855211,"id":"Q3855211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18fdb883e2f43a9dcd338bb494cde607e0e72a47","datavalue":{"value":{"amount":"+0.8542958","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$2487E094-0971-47D4-8EB3-617D5418CF25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"489103d7f4a3de2d6ae608e99b73d4218307947c","datavalue":{"value":{"entity-type":"item","numeric-id":1405126,"id":"Q1405126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8b777e372e5eba6b9782af41f444b9ff8f79b86","datavalue":{"value":{"amount":"+0.85070777","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$3406496B-DA68-43BB-B08F-3546FE59E96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"082f2df45673e0f1cba325132df4b60d303a59e6","datavalue":{"value":{"entity-type":"item","numeric-id":3418195,"id":"Q3418195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c0515386cd2cb195eee59f05950b4dbca93b2f1","datavalue":{"value":{"amount":"+0.84208155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$6CB39AB8-1736-4B0D-B132-451FC6B4F512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4400cd43b242d6892f96c398b6283cd39c47173a","datavalue":{"value":{"entity-type":"item","numeric-id":4030535,"id":"Q4030535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cd497099f6f36ff45542379a66dafd7a8c0d06e","datavalue":{"value":{"amount":"+0.8389295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$3F583A4B-C601-4919-94F6-D47CC2912A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc834e0c826fb1e939f100dc4f2912758f590d3d","datavalue":{"value":{"entity-type":"item","numeric-id":3105531,"id":"Q3105531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dee7ee61f5cfe2334d895b01d6b479acdd5428d","datavalue":{"value":{"amount":"+0.8347113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$12E90817-5847-47CA-A3B7-967DBBE366B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13cc5e32b8a6c7301b88c0a0d100195cd533882c","datavalue":{"value":{"entity-type":"item","numeric-id":3714106,"id":"Q3714106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"018d358ee7b2de8c5dea8c84ca5022b3c72dceaa","datavalue":{"value":{"amount":"+0.8282796","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$33301FDE-3B49-42DE-A1DC-5D301B467FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9a250ff755be26a605b181ce1aa83d728712df4","datavalue":{"value":{"entity-type":"item","numeric-id":1106856,"id":"Q1106856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e95a4499c5397f9c90e05acca7d6a906bdc6b1f9","datavalue":{"value":{"amount":"+0.82304865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$E8461DE0-B816-472B-BB54-6B3A1F56333E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e10317e5208da222f2769c9ece3c81e44e49e883","datavalue":{"value":{"entity-type":"item","numeric-id":1039521,"id":"Q1039521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d59a4c1611572cf2edeb1b4ec56286510f87268","datavalue":{"value":{"amount":"+0.8220525","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$5AE75603-9424-4D58-98BA-1C09E17CCA56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed42e105b8f3690bc3252a047594b8d0233acd19","datavalue":{"value":{"entity-type":"item","numeric-id":2784504,"id":"Q2784504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4270124d7a6e8655a8a3b4506e1b8bbaa6156590","datavalue":{"value":{"amount":"+0.82057816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$8AD7F66D-5FDE-4456-A7B7-CCE9598AF138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48a549f7b2e978d8924455931c52c84bae71fbd0","datavalue":{"value":{"entity-type":"item","numeric-id":1924141,"id":"Q1924141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cb95f59a5c1c2024103e86141b2eda6347ff616","datavalue":{"value":{"amount":"+0.81991535","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1910587$F9954052-B778-4479-9284-7F5DEF92F907","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On independent cycles and edges in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_independent_cycles_and_edges_in_graphs"}}}}}