{"entities":{"Q528993":{"pageid":530760,"ns":120,"title":"Item:Q528993","lastrevid":62516028,"modified":"2026-04-11T06:36:49Z","type":"item","id":"Q528993","labels":{"en":{"language":"en","value":"New results on \\(k\\)-independence of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6719985"}},"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":"Q528993$66C31400-B3B2-41FA-B4B2-F6626E237525","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9827c0dcbb3f479c06ef11b50480267bb2c45f70","datavalue":{"value":{"text":"New results on \\(k\\)-independence of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q528993$EC20DA09-606A-4AA6-9CCE-7E7CAFDFB574","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e594b46493cb2a45e002d8eee635e3dde7dcf53d","datavalue":{"value":"1361.05097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528993$5DBAE944-386D-4374-B1A8-6A6CA873B03F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"de5adae93860f2eb93717d679c34b293a3d1f133","datavalue":{"value":{"entity-type":"item","numeric-id":528992,"id":"Q528992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$40420AE0-96C3-4ADE-AD16-E8ED12E133A4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$FF6ED8FA-3C82-45E3-BB6D-A56B8863CF87","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"46a30028c10f94c4944c801c86f2de5dd37da0f3","datavalue":{"value":{"time":"+2017-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q528993$DA01057D-A2D5-485C-9356-1D4C86A8D6AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"183b83c304589f48c001f44ad9eff36ab4f0467e","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p15","type":"string"},"datatype":"url"},"type":"statement","id":"Q528993$6FD52883-269A-4CAA-922B-A7240DB3E586","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7454d965fd50fb268e3ea7fc18bfe9fe431220d6","datavalue":{"value":"Summary: Let \\(G = (V, E)\\) be a graph and \\(k \\geq 0\\) an integer. A \\(k\\)-independent set~\\(S \\subseteq G\\) is a set of vertices such that the maximum degree in the graph induced by \\(S\\) is at most \\(k\\). Denote by \\(\\alpha_{k}(G)\\) the maximum cardinality of a \\(k\\)-independent set of \\(G\\). For a graph \\(G\\) on \\(n\\) vertices and average degree \\(d\\), Tur\u00e1n's theorem asserts that \\(\\alpha_{0}(G) \\geq \\frac{n}{d+1}\\), where the equality holds if and only if \\(G\\) is a union of cliques of equal size. For general \\(k\\) we prove that \\(\\alpha_{k}(G) \\geq \\dfrac{(k+1)n}{d+k+1}\\), improving on the previous best bound \\(\\alpha_{k}(G) \\geq \\dfrac{(k+1)n}{ \\lceil d \\rceil+k+1}\\) of \\textit{Y. Caro} and \\textit{A. Hansberg} [Electron. J. Comb. 20, No. 1, Research Paper P33, 17 p. (2013; Zbl 1266.05110)]. For \\(1\\)-independence we prove that equality holds if and only if \\(G\\) is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a \\(1\\)-factor). For \\(2\\)-independence, we prove that equality holds~if and only if \\(G\\) is an independent set. Furthermore when \\(d>0\\) is an integer divisible by 3 we prove that \\(\\alpha_2(G) \\geq \\dfrac{3n}{d+3} \\left( 1 + \\dfrac{12}{5d^2 + 25d + 18} \\right)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q528993$4A52B521-7E6E-447B-B3F3-363C205706C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528993$5F617954-37F0-4E3B-8327-3638240964E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a17e331dad41016329d022a0b8a9ee4804ce8f97","datavalue":{"value":"6719985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528993$7FE13E68-6FA5-42CC-8506-6E3FEBD0A407","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54c8c66e7115052f7ff8e2bacfc275a305f8de4f","datavalue":{"value":"\\(k\\)-independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q528993$1C9DA598-FDEC-4D0B-AA2B-77BACC78A93E","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":"Q528993$EF4D8888-89C4-4ABC-9A57-4A6948D9A3A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2758f48b1a93e71d851a0e4b14bce521c35fc05","datavalue":{"value":{"entity-type":"item","numeric-id":3503433,"id":"Q3503433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$878C4AEF-B2E6-4647-8444-B089D36ED99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a3ba69a3b854176acba172aacf5954af110498a","datavalue":{"value":{"entity-type":"item","numeric-id":2446835,"id":"Q2446835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$57F49A10-FEF6-4E34-BEC9-90FDF849A7B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"959d9e142a4e3b69569823812156ebb1f0eaf648","datavalue":{"value":{"entity-type":"item","numeric-id":599078,"id":"Q599078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$262489F6-3D6A-48D3-90DD-4C7BF393D1D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30db6f08cc97604fc59c729f01a336b8a1624ad3","datavalue":{"value":{"entity-type":"item","numeric-id":1953418,"id":"Q1953418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$DCDC98F7-75D2-437A-B88D-EA9FE3240F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747da045d116c192c122bc4a2b3288d773df6c37","datavalue":{"value":{"entity-type":"item","numeric-id":3970967,"id":"Q3970967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$076A265D-ADFB-469A-BA6D-BD2F75A55094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f98473c40ccc816fba0735c4c435402e3a8cd7","datavalue":{"value":{"entity-type":"item","numeric-id":4381058,"id":"Q4381058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$79751A8E-5AED-4599-A918-BE5D31DABC7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd4a793fb7f7f894e2023a2f1704f50c6d34ff7a","datavalue":{"value":{"entity-type":"item","numeric-id":2446328,"id":"Q2446328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$CE6FFF45-9240-4F20-8382-04F3EB9CAA61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66ef71c8d44b4a62dd85079252feb06c4bbd0211","datavalue":{"value":{"entity-type":"item","numeric-id":4726281,"id":"Q4726281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$5CFEF8DC-2A91-4A80-930B-F4EFAF6B0887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4c8219b8b6d93b767b6db73dea150e34cbeecb7","datavalue":{"value":{"entity-type":"item","numeric-id":3141900,"id":"Q3141900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$B38C0C69-6ED2-4BD7-B2F6-6066D8E0B3A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$7B0414E0-28A1-4552-B155-BC1E1D48530C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f87354f16dd83f96953e92bced8c87a10306ac58","datavalue":{"value":{"entity-type":"item","numeric-id":4715272,"id":"Q4715272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$3E256653-5471-44A8-9D8E-11DB7A5FAE9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c964d9eed967e50d32f785c0acfaf4e2af43a12f","datavalue":{"value":{"entity-type":"item","numeric-id":839753,"id":"Q839753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$DB153BA9-04A2-4A6C-9B46-CF9080550270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528993$B973C2BA-5D70-45F5-AFC2-8618F4C3AFB8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"158c7ac90f5e6df3e60ea5127dcba592f5ade261","datavalue":{"value":"bafkreidam7wvgsjao6457b22zc543pqa6kwigzvypoy3qpcktc5bgvoez4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528993$78B15A53-6C56-4EEC-BA0F-EF46CCE5B2C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1538e7d7ec6b9e87f4438a2e51fe9040f4d195c","datavalue":{"value":{"entity-type":"item","numeric-id":2689120,"id":"Q2689120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"897afab323202528fc45288291d5ccc049006ef4","datavalue":{"value":{"amount":"+0.96982056","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":"Q528993$620E04C6-89D0-4B32-873F-42ED54F4CA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dab5b738be17111b3226e1f8ee8111b964024e37","datavalue":{"value":{"entity-type":"item","numeric-id":1953418,"id":"Q1953418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23436be8d34c565058b81d0a249635c1ed688fb4","datavalue":{"value":{"amount":"+0.966746","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":"Q528993$2A348F5C-0554-4D3C-9CCD-8995962F1FD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e7fecbe16e130cd3d161a8116d3a828f88cf7e6","datavalue":{"value":{"entity-type":"item","numeric-id":4554556,"id":"Q4554556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fad4e92aa17d961abec8117dd43e38ce0f4709c0","datavalue":{"value":{"amount":"+0.94027454","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":"Q528993$8587D6BE-FF34-4528-8359-7FF7756CC6D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c4e073b8311ed05bea62bd808a9d496fcbff59b","datavalue":{"value":{"entity-type":"item","numeric-id":2317661,"id":"Q2317661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70f690418bfbf14992a32a7714c8f5b84db09723","datavalue":{"value":{"amount":"+0.93936646","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":"Q528993$67459ADF-DE11-41A8-8DFB-4C826B0974D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b872d449c8978baeab2b8c78e69d934e558e19f2","datavalue":{"value":{"entity-type":"item","numeric-id":2876048,"id":"Q2876048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0b1e34892916bc2eb3820da1a4a592a3129d472","datavalue":{"value":{"amount":"+0.9386214","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":"Q528993$CB8DAFDF-3D08-411F-89C9-3E840A0DB5B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"822ef7b0377fb1a534419b00e82417fe4c48bdfb","datavalue":{"value":{"entity-type":"item","numeric-id":1946229,"id":"Q1946229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"223b45370845e6112861515f1f7573f986b06103","datavalue":{"value":{"amount":"+0.93506896","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":"Q528993$9F413425-F47A-4C17-9BA9-AC1773FF73AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18927901b313d9fa609bc35faed7d5b7496f7f3e","datavalue":{"value":{"entity-type":"item","numeric-id":2159731,"id":"Q2159731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc5596d43fc9500b30663e09edb7c10fcaa3ef4","datavalue":{"value":{"amount":"+0.93243027","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":"Q528993$A6A28F08-0878-4D8E-8C00-510A03D76F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9367255ca85e5b36cc3748ca86e39cfa0db4b1b4","datavalue":{"value":{"entity-type":"item","numeric-id":4374002,"id":"Q4374002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fa9fe1e409fd5fc142077a26ec05e4a3813ad7d","datavalue":{"value":{"amount":"+0.93053305","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":"Q528993$68C8413D-2E77-4400-AB7D-8676BB0BA066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"397bdea5c27feb9810b5eefe6e0ca734c306dbe1","datavalue":{"value":{"entity-type":"item","numeric-id":2995488,"id":"Q2995488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a219c58140d0c00d452b5c356366fc5f85e4968","datavalue":{"value":{"amount":"+0.92583215","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":"Q528993$CBA20AC0-0BB2-45BF-8731-52D0F73FB33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1ea797e2c2560b54cd3958923f0150fc58a1b2d","datavalue":{"value":{"entity-type":"item","numeric-id":405126,"id":"Q405126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6e37b99ce3c6fab163a0b804c78e53214f78907","datavalue":{"value":{"amount":"+0.9256028","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":"Q528993$4166092A-75E5-4EB6-9640-632E5E79BA3D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New results on \\(k\\)-independence of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/New_results_on_%5C(k%5C)-independence_of_graphs"}}}}}