{"entities":{"Q1331985":{"pageid":1342735,"ns":120,"title":"Item:Q1331985","lastrevid":43033782,"modified":"2025-07-17T02:17:20Z","type":"item","id":"Q1331985","labels":{"en":{"language":"en","value":"On unique independent sets in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 626323"}},"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":"Q1331985$9AC89789-E996-40B5-BF50-847CED58B698","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e07bd20fa4b419df59442056ff32fcc9d6622b77","datavalue":{"value":{"text":"On unique independent sets in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1331985$37108C37-64B9-4E29-BFDF-9EFB23CD4764","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f180fa4f979fb179fc5e3d4abf5a9bb694521be","datavalue":{"value":"0812.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$287FEFB5-5200-43BC-9263-FECC33D8B335","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"de1e8dde0db6676780e674d8f5c670b757a609df","datavalue":{"value":"10.1016/0012-365X(94)90389-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$390E941A-27CC-4557-AD7C-21CBBB7140B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d71e5c317fa8044a8e6d1e4b41b9cac60652c7c3","datavalue":{"value":{"entity-type":"item","numeric-id":1331984,"id":"Q1331984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$FECF18C8-51F1-4398-ADF1-65EDE2D9D868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6e39983c1ad70f8fb55166da3f8e64fbaf954eb","datavalue":{"value":{"entity-type":"item","numeric-id":685553,"id":"Q685553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$E7889AEA-0E6D-4322-B4C6-A4444B1809C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b4422e37ea985f640d4cbfe3c8456c60e8e83e9","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$29AFADDF-98A9-46EE-B156-0ACDC6945B71","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":"Q1331985$EFD0FE95-A5C5-4F8D-90CD-BEF6CB714283","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5c9e4c93221b65868a4d2090be3649841672715","datavalue":{"value":{"time":"+1994-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1331985$7415FB84-78F2-4CFF-840F-67721A61B711","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21c8c824c82d2541cfc6f258333b2c121e65cad8","datavalue":{"value":"For a nonnegative integer \\(k\\), a subset \\(I\\) of the vertex set \\(V(G)\\) of a simple graph \\(G\\) is said to be \\(k\\)-independent if \\(I\\) is independent and every independent subset \\(I'\\) of \\(G\\) with \\(| I'| \\geq | I|- (k- 1)\\) is a subset of \\(I\\).   A \\(k\\)-independent set \\(I\\) is strong \\(k\\)-independent if \\(V(G)- I\\) is independent in \\(G\\). For \\(0\\leq \\ell \\leq k\\), \\(k\\)-independence implies \\(\\ell\\)-independence. A set is 0-independent iff it is an independent set of maximum size; a set is 1-independent iff it is a unique independent set, a concept investigated in [\\textit{G. Hopkins} and \\textit{W. Staton}, Graphs with unique maximum independent set, Discrete Math. 57, 245-251 (1985; Zbl 0583.05034)].   The authors characterize \\(k\\)-independent sets for (a) graphs in which every even cycle has a chord, (b) graphs in which every block is a complete graph or an odd cycle, and (c) bipartite graphs. They then generalize results of Hopkins and Staton, and of \\textit{F. Harary} and \\textit{M. D. Plummer} [On the core of a graph, Proc. Lond. Math. Soc., III. Ser. 17, 305-314 (1967; Zbl 0152.412)] in Theorem 8: For a positive integer \\(k\\) a tree \\(T\\) has a strong \\(k\\)-independent set iff the distance between any two vertices of degree at most \\(k\\) is even.   Finally, they prove a ``Tur\u00e1n-type'' extremeal theorem for graphs containing a \\(k\\)-independent set, and provide examples of extremal graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331985$FC801BEC-6541-4AF1-8C8E-204AD245BC63","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$CBEDD569-286A-45BF-9366-B2F92F934F72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$3C951E7C-F3E8-4081-8AA8-2A998D540DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$12638B44-7DCF-4F24-BE43-6D9DF0DD1369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$DDB84B42-B615-48C3-945D-C74EDC5ED4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$B1500B24-3C86-47F2-9590-DE0B0E5F446D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"33fb57f535d089d082f5750e1f493b0ce70d1e00","datavalue":{"value":"626323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331985$E56F015D-7B86-4C12-82C0-2D3465C3D078","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54c8c66e7115052f7ff8e2bacfc275a305f8de4f","datavalue":{"value":"\\(k\\)-independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331985$63385D25-2DAE-4C38-B3E3-63CAC966485C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e64b13bbfc22dead1e4f3d63ab660bac041223c4","datavalue":{"value":"\\(k\\)-independence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331985$2B061557-6F44-4977-BAF2-61A8EA3163C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcdf25b016410f2df78338e678a1b0e1264ac62f","datavalue":{"value":"unique independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331985$0D9FF884-818D-40DF-A70E-987EAE5EA30F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331985$93A0DCA7-B5EF-4053-B90D-C1D3EE27FE6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331985$D5E20113-1D60-435B-B830-A6DA70BC02AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$387901B0-692C-489A-A6A0-3ED917483DC2","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":"Q1331985$26CA19CC-E7F6-41B3-9DB8-A0A43051A370","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09b06ada4a02303c79d7ffc00581d47956a243d6","datavalue":{"value":{"entity-type":"item","numeric-id":4099676,"id":"Q4099676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$2ADFB437-188F-4A9A-931A-863333566001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d541230efa3fda1538f5bc0cd3dd8ded7436b793","datavalue":{"value":{"entity-type":"item","numeric-id":5532263,"id":"Q5532263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$42351A8D-A7B3-430A-B16E-F52EC11BF184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad9773435bfa0a884f393ac627a195318cd85ab6","datavalue":{"value":{"entity-type":"item","numeric-id":1069954,"id":"Q1069954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331985$CE0112F8-30C1-4309-9C95-68038846ACB3","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":"Q1331985$0597C592-A46D-4C68-BCDC-025BD8E5F9F6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cfb63197703cc779a36962f4f79ff976c922e5","datavalue":{"value":{"entity-type":"item","numeric-id":2643314,"id":"Q2643314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f44ddac3555b8e9a25ea38257ffdbab208fc3ce","datavalue":{"value":{"amount":"+0.855327","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":"Q1331985$26F07BF5-A216-437F-B17D-228551BABA7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ff23b0c2a35b24e79926b5c0dc959aa89f78087","datavalue":{"value":{"entity-type":"item","numeric-id":1069954,"id":"Q1069954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d45932223abef5dfeb4286e1c69666bd26a23da","datavalue":{"value":{"amount":"+0.85446477","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":"Q1331985$E5DCDB38-5023-4CCA-8533-2245CD8070C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"753b9b9c7d5dcd94f581d30a42a6c85df99050ba","datavalue":{"value":{"entity-type":"item","numeric-id":2828876,"id":"Q2828876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59882cc1709660add771e484c81e718a6d617a24","datavalue":{"value":{"amount":"+0.84185076","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":"Q1331985$FF4B4428-1000-463D-801C-36CAFC9BA61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"465c9fa052e7dbaf6b8147e73b54f57ddb53f0eb","datavalue":{"value":{"entity-type":"item","numeric-id":736194,"id":"Q736194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"931064ae2b8d6d80306ccff66560b4999fb7008a","datavalue":{"value":{"amount":"+0.8403685","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":"Q1331985$63A62DAE-1D2C-4215-B1C1-01A8D2D7D8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f5a87cf996cbad4107be2096ea8cd0847004634","datavalue":{"value":{"entity-type":"item","numeric-id":2376089,"id":"Q2376089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd8d84c7117f69b71c8566786c0ae92bcbec7ed4","datavalue":{"value":{"amount":"+0.8365419","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":"Q1331985$5D1D54E6-EF2A-41B0-ADCA-9D9C47FBC750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26bc7bb3cf6e516baddeaf4cc43220063c2d8ba4","datavalue":{"value":{"entity-type":"item","numeric-id":2464160,"id":"Q2464160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"614d43797fa9ab912f93f0fa8f969de2048fa685","datavalue":{"value":{"amount":"+0.83401453","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":"Q1331985$3B29C823-3764-404F-9951-88A090A9BA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46ecb1c65ea20ce9b5e975f03fd4d5cf38486dd6","datavalue":{"value":{"entity-type":"item","numeric-id":3527533,"id":"Q3527533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf1ddc529fe68e24b07ab6cc90cce5c9e157e4b8","datavalue":{"value":{"amount":"+0.8328276","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":"Q1331985$B675EB43-C6B7-4883-9823-0A4A8AA25315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6337f92b0c88e30b743bc232755aade36c755b24","datavalue":{"value":{"entity-type":"item","numeric-id":5928418,"id":"Q5928418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80e2b1b12dac05748aa14e205b671cd69e0b61c9","datavalue":{"value":{"amount":"+0.8328215","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":"Q1331985$6C9FACCD-B77F-4F58-A230-42D7CD6B66EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"099029809b03ae74a528a8efb40c6471fde2f8fe","datavalue":{"value":{"entity-type":"item","numeric-id":4486258,"id":"Q4486258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe2ecf39e36f6063fd6ec832c6b42cedd8756e11","datavalue":{"value":{"amount":"+0.8319856","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":"Q1331985$A627B3C1-0F61-436F-BE3F-34940365317F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc9638e008b3ab42149aec15b5b64493a6774c2e","datavalue":{"value":{"entity-type":"item","numeric-id":2563420,"id":"Q2563420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac24d1161606717dced5ba29f42115211f4e4579","datavalue":{"value":{"amount":"+0.83007723","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":"Q1331985$96C3DFBB-1EFA-4CE8-8406-26693312EDED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1331985","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1331985"}}}}}