{"entities":{"Q1068855":{"pageid":1079607,"ns":120,"title":"Item:Q1068855","lastrevid":48882238,"modified":"2026-01-06T02:03:51Z","type":"item","id":"Q1068855","labels":{"en":{"language":"en","value":"The struction of a graph: Application to CN-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3931065"}},"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":"Q1068855$48040DE9-C445-4806-A179-EFD641F686E7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9d44f81fef8f0b8c4c2dfe0c283c8195c401e374","datavalue":{"value":{"text":"The struction of a graph: Application to CN-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1068855$46D8C3B6-D0B1-444C-ABAC-65CA572E0233","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b743fff506d5b10671270264dc46f8a17c0fc2d6","datavalue":{"value":"0582.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068855$FF7DEF87-81F3-486A-BBBC-52C8D25254A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9914960bfc16107c8697869a301d17dba083577","datavalue":{"value":"10.1007/BF02579377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068855$BB23A8D0-15DF-435E-B8CD-959CEBD4E9F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"982f5091aa6783300b33c5810a51dbd1cdf0e96b","datavalue":{"value":{"entity-type":"item","numeric-id":686489,"id":"Q686489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$2B25F5F0-6B0A-48D4-AD09-52CD9F95C6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"467bce3dcf8136ea7a4832a7c85d350a56e9a245","datavalue":{"value":{"entity-type":"item","numeric-id":224825,"id":"Q224825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$E3E6BA47-3810-426B-801E-C312A009BA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"54ae8a1f67117b1c40e7224a6ee62353a2cf60cb","datavalue":{"value":{"entity-type":"item","numeric-id":188437,"id":"Q188437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$8AFD9D7D-3CDB-4F3F-B15E-EF14ECE24665","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$D3B73E65-F2C4-44C0-AFEE-C2C8D042FB4D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1068855$67467B94-72C2-4471-BBE7-58D12F03469E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3aa1310f1ea456e1f0094d30aec5202d90227d5e","datavalue":{"value":"A graph is CN-free if it contains neither C, the claw, nor N, the net (unique graphs with degree sequences \\((3,1,1,1)\\) and \\((3,3,3,1,1,1),\\) respectively) as subgraphs. For the class of CN-free graphs, a polynomial time algorithm is described for determining the stability number a(G). The basic idea of the algorithm consists in a reduction procedure (called here struction) associating to any CN-free graph G another such a graph G' with \\(a(G')=a(G)-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068855$72C48671-59B4-4120-ACDD-D4F003171123","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068855$63FD1FE9-F0FE-4DE4-98B4-D350A847D375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068855$638852CE-1C6A-440B-9B6F-4C8F39DFD003","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"767e98d373f5ed5125544807d25b13f846a10c9d","datavalue":{"value":"3931065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068855$11A759FC-6DD5-44F0-AD77-A70267A31615","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68b4d35fcda914792f11b716ca628f90028fc21a","datavalue":{"value":"claw","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068855$B44F8C3D-D72E-4332-8810-68A031855C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aaeae3b818575ceea6c66f4ee2d0beb53c3ba244","datavalue":{"value":"net","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068855$00D053BB-2952-47E7-8B3D-A89BFE9D2804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a99b60c87837647a6d8f05011a88935d41dbf068","datavalue":{"value":"CN-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068855$5FC3EF1E-50F7-4794-BDAC-1A1FA4680BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068855$7A63C429-3619-426C-A4C2-F8918009BC9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87e0e2197df31604dd9f16334c9c805616d74d2d","datavalue":{"value":"stability number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1068855$D01CF3D7-96B7-43D7-8F61-45CEE70FAFEB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90c78b3265eaf03d2c9093f31b0f9730424156f8","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$7FBCC79A-99B0-42FF-9C19-E35AB158E745","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":"Q1068855$8B131ED0-6184-4339-B4B6-C161407650A4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$C714B18D-345C-495B-9DC3-0B2A11C66F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1520658579983937d57617c380bbcd46c2e4d2b","datavalue":{"value":{"entity-type":"item","numeric-id":762505,"id":"Q762505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$5EFBDE0E-DABD-4B6B-9577-2CEAE93A4891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$FB2769A4-6CD7-472D-9387-E8C9CCCE70D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1068855$C5D4D2C8-B1D3-4FBA-8438-A80C49B1DD62","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"379115eedbfb670ea427ab1d6468f663c2364d49","datavalue":{"value":"https://doi.org/10.1007/bf02579377","type":"string"},"datatype":"url"},"type":"statement","id":"Q1068855$C8F2DD13-4631-4535-87D4-D84DD04130DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ddf652e1e81f80dd2f184996adf35ee1216b332f","datavalue":{"value":"W2029454721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1068855$210A4178-92FE-4DD7-B7B1-E4D7E4D703EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5838b685912cb7d3c98848893303a9255b11f03c","datavalue":{"value":{"entity-type":"item","numeric-id":762505,"id":"Q762505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbca046871e49b50880a65dfd493c3bd67bd5196","datavalue":{"value":{"amount":"+0.8210427761077881","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":"Q1068855$825A1584-113C-4742-8F52-6C677928A5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59c03f08529ff40acfcffb5cd5fa6a948aa2cf2d","datavalue":{"value":{"entity-type":"item","numeric-id":1080863,"id":"Q1080863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f1ad75d39a5d95a037154d3b0e81abbdff294c","datavalue":{"value":{"amount":"+0.8121767640113831","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":"Q1068855$34354D24-62F0-4012-A8CA-EEB7D6C26E17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"724055e01bf179cbf0eed78cb81a5aa816f1644d","datavalue":{"value":{"entity-type":"item","numeric-id":4211743,"id":"Q4211743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76af754be53a11cd7de147fbec10b528357619bb","datavalue":{"value":{"amount":"+0.7826493978500366","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":"Q1068855$6D4FD747-13BB-417E-AF52-32277236E0C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1541a59fcc9083b01eacb046502e383587118ca7","datavalue":{"value":{"entity-type":"item","numeric-id":1414580,"id":"Q1414580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba8a9b501083966634e30c657aeb9f6ea2eac859","datavalue":{"value":{"amount":"+0.7791950702667236","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":"Q1068855$B32B0697-96DA-4A1A-86B6-595A6597DF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7c759f0a13c9c0cdced2ddfd0135d6fd1f5ab81","datavalue":{"value":{"entity-type":"item","numeric-id":1302154,"id":"Q1302154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33e09448953fbea886d70d968592cc28c4d69ce5","datavalue":{"value":{"amount":"+0.7756759524345398","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":"Q1068855$C895E5EB-C2E5-45A6-865B-02F9BE95ED44","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1068855","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1068855"}}}}}