{"entities":{"Q2045314":{"pageid":2056056,"ns":120,"title":"Item:Q2045314","lastrevid":57283248,"modified":"2026-03-27T20:41:47Z","type":"item","id":"Q2045314","labels":{"en":{"language":"en","value":"On the \\(k\\)-component independence number of a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7381269"}},"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":"Q2045314$2FC5A038-8D44-4679-87FE-D59D74C89D6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0717b4730cce690f0f392f52cdc79fda1546df14","datavalue":{"value":{"text":"On the \\(k\\)-component independence number of a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2045314$54B937BF-AC69-413F-9B5F-5F3A2B049336","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af77f365d1c2a4677985bceb5e9c3669783c6bc2","datavalue":{"value":"1471.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045314$F1D5A53B-08C2-4F1A-84FD-5E9E46946917","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"09f2a7d00a92a304a1e4d68776b17b9fc351218b","datavalue":{"value":"10.1155/2021/5540604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045314$CB94B33B-8193-403F-BB00-84C1658A91CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c041d73a600a9d28e45cd13e21972785d5667fdc","datavalue":{"value":{"entity-type":"item","numeric-id":2045313,"id":"Q2045313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$44ADD6AA-AC0E-4D98-B9D1-BD182DAF1789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"940c27262f311e4811efa9912a7489378b803016","datavalue":{"value":{"entity-type":"item","numeric-id":244910,"id":"Q244910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$F8043CEE-14E0-45C5-804F-FADFC1AD07F5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e5ea7bc024fe2946ca15646035f056e2ab96db7a","datavalue":{"value":{"entity-type":"item","numeric-id":169945,"id":"Q169945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$1CC28856-7C84-453B-9463-A3F735D5DA14","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ead17b2dc765ff7eba703ab163949d6e600f878","datavalue":{"value":{"time":"+2021-08-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2045314$897F16E6-FA32-4361-8A86-089FD12E6D75","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8af91e74ec2b93df3c8a529f5e76c4efde49ba3","datavalue":{"value":"Summary: Let \\(G\\) be a graph and \\(k\\geq1\\) be an integer. A subset \\(S\\) of vertices in a graph \\(G\\) is called a \\(k\\)-component independent set of \\(G\\) if each component of \\(G[S]\\) has order at most \\(k\\). The \\(k\\)-component independence number, denoted by \\(\\alpha_c^k(G)\\), is the maximum order of a vertex subset that induces a subgraph with maximum component order at most \\(k\\). We prove that if a tree \\(T\\) is of order \\(n\\), then \\(\\alpha_k(T)\\geq(k/(k+1))n\\). The bound is sharp. In addition, we give a linear-time algorithm for finding a maximum \\(k\\)-component independent set of a tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2045314$67AA6108-B28A-44E0-9A6F-1556E05C9B5C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045314$9CAC2396-3AEF-4078-88E1-5D1ED084AD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045314$D514AD1F-1C85-44AB-8CBC-F20CE96413A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"172ef2f1823d81343db80a1c4a11867d1582a846","datavalue":{"value":"7381269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045314$AA0CF106-FF2D-4037-854A-CB5EA7BBE02B","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":"Q2045314$D56CF738-6AA0-421B-A23F-CAE3AF7A806C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"12a8b905c01dbf29a7c8e57c7077c8830677c64c","datavalue":{"value":"https://doi.org/10.1155/2021/5540604","type":"string"},"datatype":"url"},"type":"statement","id":"Q2045314$A375BDAB-0393-41CF-B815-C5FFD051B7AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4e856371a085dff7b95ca5db541fe7e78018117f","datavalue":{"value":"W3166777523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2045314$48FABB47-ADE3-4549-8E71-A135B7263ADC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ad2bded7390c2b0caa0df8ef68ed578fa593633","datavalue":{"value":{"entity-type":"item","numeric-id":1750660,"id":"Q1750660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$12F8188F-F2EF-4566-B9AF-8370D4D713E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb4cd0043520378950644a1497cfc0310df533c0","datavalue":{"value":{"entity-type":"item","numeric-id":1405114,"id":"Q1405114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$4DE4D934-65C8-48A5-AEB2-4D3BE10BA939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e329c49df9dc6c161a7bfc5b5299c5e3e21d0ef","datavalue":{"value":{"entity-type":"item","numeric-id":5270999,"id":"Q5270999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$FE2C1829-AE2D-4C82-BECD-F4EFDBE1FD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce000adc942b205cc6d62deb9cf54babd34b2598","datavalue":{"value":{"entity-type":"item","numeric-id":2185923,"id":"Q2185923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$CB76EBBF-2A3C-403A-AEAE-899506147B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cacc4cabbabecdcb2babaf46732fee208c4094e","datavalue":{"value":{"entity-type":"item","numeric-id":1400964,"id":"Q1400964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$A9BAEBFA-A40B-40B9-8DAD-CF2A5F003777","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef66328f98dfa41b69af37345e893e7f001c6e52","datavalue":{"value":{"entity-type":"item","numeric-id":2300163,"id":"Q2300163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$7855C367-AAAE-4879-B230-72122FAA279B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e12ddd3b671c34fe5ef68decec197612fc65b7b6","datavalue":{"value":{"entity-type":"item","numeric-id":1751289,"id":"Q1751289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$22BB560F-535F-44F2-961C-5442854EA234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e073e79a1920118d6ea3fc34eb8b07986ad1586","datavalue":{"value":{"entity-type":"item","numeric-id":4290578,"id":"Q4290578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$84D6E7DA-7D83-4C72-AE3A-2646A27E2312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f70f621a5f51517480f229079d940e5c5f1e9a3d","datavalue":{"value":{"entity-type":"item","numeric-id":1850531,"id":"Q1850531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$C71FD3C8-EE17-4BC7-8912-8F0DE75831EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76587e34cb267c1850136d5508bad492aab4fa9d","datavalue":{"value":{"entity-type":"item","numeric-id":2911581,"id":"Q2911581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$87E52B14-9F41-4795-AF05-726345BDE10C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ad2c25b4e94aa48bfbe2b6336bbe2542a9356c","datavalue":{"value":{"entity-type":"item","numeric-id":4554541,"id":"Q4554541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$B6AA3AF9-9F0C-4801-8793-386AFCFB4B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e1bdbe6e2f11d5805e74cea304e922d778565cf","datavalue":{"value":{"entity-type":"item","numeric-id":1727736,"id":"Q1727736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$41389A90-EF88-47BE-8006-B1FF5796A58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae0027f68231b35e9eed1e3b21cd32c04c3ffe2","datavalue":{"value":{"entity-type":"item","numeric-id":5109070,"id":"Q5109070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$69D37ABA-A456-4B84-A748-CA937C6AEE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49dedd1f9f583eaefa154fcb7368b8801104d180","datavalue":{"value":{"entity-type":"item","numeric-id":2283032,"id":"Q2283032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$03304795-0B3B-470D-9E90-3C44C943EFB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3eb56abc42011576013fcadd2a5a7fa2d55a36fd","datavalue":{"value":{"entity-type":"item","numeric-id":3978364,"id":"Q3978364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$7511A9A0-08FD-4BC1-9853-AC02B6CFB392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e77053eb504d083f4e60324452bf6a15b6aa2a68","datavalue":{"value":{"entity-type":"item","numeric-id":998481,"id":"Q998481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$2998EE09-FDD6-4D49-A71E-B820991A34D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800e1ec900d91df6058a1d586b21de02c03bd1d5","datavalue":{"value":{"entity-type":"item","numeric-id":5928418,"id":"Q5928418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$DBFC922D-7E21-4491-850D-92184C37361E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dfbb04c2f353220625d7d508c3dbd7eb7509907","datavalue":{"value":{"entity-type":"item","numeric-id":1756132,"id":"Q1756132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$024C15FB-9342-4ECB-9DD4-D6317E6E7F01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"358e683a0508d36018724dcd45a9c43f8b41d111","datavalue":{"value":{"entity-type":"item","numeric-id":2119697,"id":"Q2119697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23606c87814d0f00fca86b4600ad2f2ca2720a21","datavalue":{"value":{"amount":"+0.8113255500793457","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2045314$B09A02BF-9574-4627-8C59-77B5E29A3347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfed5e91f96c59a64a3a743a388837e44e101889","datavalue":{"value":{"entity-type":"item","numeric-id":2860868,"id":"Q2860868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94c456cf4080075914fbf87adf219a019d5330dc","datavalue":{"value":{"amount":"+0.8099011182785034","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2045314$E0059D0B-5DFF-4DAC-A348-12216E1BF00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99ab24578a9bdd3c17341f55dd516fed09f29e98","datavalue":{"value":{"entity-type":"item","numeric-id":1684925,"id":"Q1684925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7ed5aefea6845f51d22a54c35d838b6dab0f09a","datavalue":{"value":{"amount":"+0.8062863945960999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2045314$2289C05C-4374-446E-9CF9-9910B50F0CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d5c0a9e4f8aab12662baab82121078e40a3949b","datavalue":{"value":{"entity-type":"item","numeric-id":972329,"id":"Q972329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a34eac3e1d4d51c80963cde8f05e7c609e388f9","datavalue":{"value":{"amount":"+0.8046092391014099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2045314$46D35128-B9CC-4E9A-B45E-5FE7237575AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49998f15e6b13d13812ece1b9169e4d819a88cf2","datavalue":{"value":{"entity-type":"item","numeric-id":5463559,"id":"Q5463559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b599e017ae0fb155070c337c5875538b58c9092f","datavalue":{"value":{"amount":"+0.7890812158584595","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2045314$4738550C-F6A0-4494-8AE1-6078A6C0BC95","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2045314$FD94D94B-21A0-40E0-8D94-3E0D8FB87666","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2045314","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2045314"}}}}}