{"entities":{"Q276201":{"pageid":277968,"ns":120,"title":"Item:Q276201","lastrevid":60625920,"modified":"2026-04-10T18:08:22Z","type":"item","id":"Q276201","labels":{"en":{"language":"en","value":"Graphs with induced-saturation number zero"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6576600"}},"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":"Q276201$A0F1A5A3-84AD-4DD6-86A6-8DE88B234D35","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2da1942ae1ac2f80daeb5925b5abb516b8fac0b2","datavalue":{"value":{"text":"Graphs with induced-saturation number zero","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q276201$CA81C95E-6124-47A6-AAA0-3E4093D76182","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"868fddc5467326ec0d061f677a2c095326593359","datavalue":{"value":"1338.05129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276201$4D3FBA64-BAE2-4D54-95EE-FDE21DBE05F4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3d3d323d5f1be0499da10a72886218322f76181","datavalue":{"value":{"entity-type":"item","numeric-id":276197,"id":"Q276197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$70ED5B76-BDEA-40D7-81B2-6B9017D29BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c634abb8b0471df479a786656ba7aef86e686127","datavalue":{"value":{"entity-type":"item","numeric-id":276198,"id":"Q276198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$4D9B7730-805A-4744-B39A-04C83F7FAD9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"db8db596498fd0cfd08b985a869d92b46341e6b8","datavalue":{"value":{"entity-type":"item","numeric-id":276199,"id":"Q276199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$45F4F097-1B76-4C66-B6F9-D3A0F75B1ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"63e99339289fc2e7c23df3bd959eace7c33ce1b0","datavalue":{"value":{"entity-type":"item","numeric-id":276200,"id":"Q276200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$0B76D5BB-3514-4F25-8D34-0452CD4D2B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4d2818fb05ff660244a999da9900f1da149d76b","datavalue":{"value":{"entity-type":"item","numeric-id":251904,"id":"Q251904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$D289A059-A258-45AE-A49A-60A4F0EAC0A4","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":"Q276201$E2BDE913-C74B-44C0-B703-4A2B8AC66D4F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e14340917da0b560f1aa784255616bd78a4a4ba6","datavalue":{"value":{"time":"+2016-05-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q276201$04D65456-C820-4770-B70A-617216E945C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6a1be5d0b787a8b139d9e6ad9d9b0b73005e59e","datavalue":{"value":"https://arxiv.org/abs/1503.02105","type":"string"},"datatype":"url"},"type":"statement","id":"Q276201$A3A6AA7F-63FD-49C3-9EA2-CD2775FC96AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa1f4be47825723c425daa5381c927d32c81c837","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p54","type":"string"},"datatype":"url"},"type":"statement","id":"Q276201$31DDED95-BC78-46C8-B750-D9B79A50ABAD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"71ec78c221ce2da2bc1658a8ed1ab27f1b42acf0","datavalue":{"value":"Summary: Given graphs \\(G\\) and \\(H\\), \\(G\\) is \\(H\\)-saturated if \\(H\\) is not a subgraph of \\(G\\), but for all \\(e \\notin E(G)\\), \\(H\\) appears as a subgraph of \\(G + e\\). While for every \\(n \\geqslant |V(H)|\\), there exists an \\(n\\)-vertex graph that is \\(H\\)-saturated, the same does not hold for induced subgraphs. That is, there exist graphs \\(H\\) and values of \\(n \\geqslant |V(H)|\\), for which every \\(n\\)-vertex graph \\(G\\) either contains \\(H\\) as an induced subgraph, or there exists \\(e \\notin E(G)\\) such that \\(G + e\\) does not contain \\(H\\) as an induced subgraph. To circumvent this Martin and Smith make use of a generalized notion of ``graph'' when introducing the concept of induced saturation and the induced saturation number of graphs. This allows for edges that can be included or excluded when searching for an induced copy of \\(H\\), and the induced saturation number is the minimum number of such edges that are required.{  }In this paper, we show that the induced saturation number of many common graphs is zero. This yields graphs that are \\(H\\)-induced-saturated. That is, graphs such that no induced copy of \\(H\\) exists, but adding or deleting any edge creates an induced copy of \\(H\\). We introduce a new parameter for such graphs, indsat\\(^\\ast\\)(\\(n,H\\)), which is the minimum number of edges in an \\(H\\)-induced-saturated graph. We provide bounds on indsat\\(^\\ast\\)(\\(n,H\\)) for many graphs. In particular, we determine indsat\\(^\\ast\\)(\\(n,H\\)) completely when \\(H\\) is the paw graph \\(K_{1,3}+e\\), and we determine indsat\\(^\\ast\\)(\\(n,K_{1,3}\\)) within an additive constant of four.","type":"string"},"datatype":"string"},"type":"statement","id":"Q276201$269E2E83-283D-4CBC-9ACD-4539F3A59D73","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276201$AD92F161-D27C-4793-914C-5322D9C30989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276201$00FA2FF9-7350-43BD-8D93-B24803A0A2A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c63e7b3543396b2f856a92aeadf50aa3d2766c99","datavalue":{"value":"6576600","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q276201$601EB3E0-74BB-4CBA-BD62-D54EDE154AC2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"597aff73b947d8f0c76cf71bb8e3687db75daae3","datavalue":{"value":"graph saturation","type":"string"},"datatype":"string"},"type":"statement","id":"Q276201$380DB576-01AA-4B6F-8A28-A93AACF0E4C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4dbee0d48d17c0702756f23f68f3af28651233","datavalue":{"value":"induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q276201$EE7F72B7-0AD2-4383-84A2-E8EC176E7122","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":"Q276201$C06EB038-E919-4C89-8CD0-06C0F0E58C9B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f63e38e4851ca0e3a13042d4f415c0b9fe4f5434","datavalue":{"value":{"entity-type":"item","numeric-id":5601346,"id":"Q5601346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$E7D00C4F-444F-4A2D-95F8-F21C2CE9E0BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$4C6F0DBB-9B42-428E-A566-9E08E6B43ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c40f5e287ce342e31e29db5c0eab02e99343e0","datavalue":{"value":{"entity-type":"item","numeric-id":3416248,"id":"Q3416248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$8A82B0C1-FDF2-4185-B78F-D7B8BC172E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f3be34444b87e94060eeddaad78e0c69a90fd2","datavalue":{"value":{"entity-type":"item","numeric-id":4165164,"id":"Q4165164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$858F9B17-3D21-4D1B-9D8F-8B3A7B4F723D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6003b20622a76e9dda63a260950197adafe9dcb8","datavalue":{"value":{"entity-type":"item","numeric-id":5331782,"id":"Q5331782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$CA0A4B20-895B-4354-A831-A1EA4A0EC7D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"339bc7dd3da3eb4fe8ed7a5486c77b5908e8a4ce","datavalue":{"value":{"entity-type":"item","numeric-id":554011,"id":"Q554011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$BDB6D946-2032-498F-9D88-FA2DB6C7B092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"299ea99d3654d477f14b5d7e0d6a202ca9146486","datavalue":{"value":{"entity-type":"item","numeric-id":1248531,"id":"Q1248531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$B2DDDB43-AE02-439A-85C8-A3A9B0823FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb44fa19ef432ebe70a929dc7ab6c3c9375a250","datavalue":{"value":{"entity-type":"item","numeric-id":3722536,"id":"Q3722536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$D9EE8919-D32E-43F1-A002-929B9D13AE5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31ffcb65b5d111490042d472d548c61b4cfc45f0","datavalue":{"value":{"entity-type":"item","numeric-id":1375060,"id":"Q1375060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$120AB97C-F3F4-48DE-93A0-D3262732BBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$D1D0A6D5-C16B-40FB-A9B4-AA1C5FF6B83B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50163700542893ad1d001504324115b472bed03","datavalue":{"value":{"entity-type":"item","numeric-id":456647,"id":"Q456647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$2F87592B-3B5D-4F43-A819-4A3BD6F7B849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5163a190d3b3bcaf278fa611cf7e0004d711bc9","datavalue":{"value":{"entity-type":"item","numeric-id":3845886,"id":"Q3845886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q276201$3EBF90C4-1F9E-4FA9-B07A-F12F08609E2E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97b1347ade68ad3f93c3c71098f903669993717b","datavalue":{"value":{"entity-type":"item","numeric-id":5225526,"id":"Q5225526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d731242b6e56fcb4f366c0d9505a78f9e9ef0a0a","datavalue":{"value":{"amount":"+0.8646478056907654","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":"Q276201$F2EF63C4-3FE5-44BC-A8DA-3A8649A3F1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9898c17213bb4a8ed8bfb5603fa728fa6058ece","datavalue":{"value":{"entity-type":"item","numeric-id":1727803,"id":"Q1727803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e717ad33f8e05301c8a36a427efd7c9788939792","datavalue":{"value":{"amount":"+0.8602721691131592","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":"Q276201$A780D669-901C-4F6E-A2A3-A3AB76AE509E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ae52ef6d33aee0d4f3949786b7427bad8f528da","datavalue":{"value":{"entity-type":"item","numeric-id":2279288,"id":"Q2279288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c4139ac6a968c4930722b64dd71c8b2aeef0dc9","datavalue":{"value":{"amount":"+0.8431116342544556","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":"Q276201$F804218C-2FC0-47B4-A784-2EE684EB1C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6a5f3ee4fae65cf8f89ec5375ee3a4d04cadd0d","datavalue":{"value":{"entity-type":"item","numeric-id":2225408,"id":"Q2225408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"545376c82a1b66085ba5ae7bc79684ab9dc7b68b","datavalue":{"value":{"amount":"+0.8333595395088196","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":"Q276201$CE53B99F-A151-4C6F-BF6C-A499DE2B4D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaa845e28988b4ec0064809f2ffc7db212be0e1b","datavalue":{"value":{"entity-type":"item","numeric-id":456647,"id":"Q456647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f39070e078073d8ae7f1ac447952c122a9a70866","datavalue":{"value":{"amount":"+0.8294593095779419","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":"Q276201$8F4CDDFD-18F8-4FD4-A734-4B914D2F2D60","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs with induced-saturation number zero","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_with_induced-saturation_number_zero"}}}}}