{"entities":{"Q686272":{"pageid":688121,"ns":120,"title":"Item:Q686272","lastrevid":63608823,"modified":"2026-04-11T14:19:41Z","type":"item","id":"Q686272","labels":{"en":{"language":"en","value":"Extremal graphs domination insensitive to the removal of \\(k\\) edges"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428119"}},"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":"Q686272$086D130A-E7E2-482E-84E0-52514534357A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ea6069f5b49725067921f2af345a86c9e349445","datavalue":{"value":{"text":"Extremal graphs domination insensitive to the removal of \\(k\\) edges","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686272$AFAE2668-8A2F-4C89-833C-947FF92206C5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02577703b7b688e2232f22c12d6d99f8656e6abd","datavalue":{"value":"0783.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686272$186377E9-35AA-40A7-8D1F-984730AA2C32","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4f8f18f224fae26480e2ee65525a06c6061fa668","datavalue":{"value":"10.1016/0166-218X(93)90238-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686272$FEA3E3BE-BF56-4F8A-BDBF-51538C165CDA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c84311665c8f412f94a2d02650f3c85f19494e6b","datavalue":{"value":{"entity-type":"item","numeric-id":234392,"id":"Q234392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$7EC7327A-F800-4FB1-87F5-8D781D7D5675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"921bd66633e45c6f13e0808cd33196f803e39efd","datavalue":{"value":{"entity-type":"item","numeric-id":624136,"id":"Q624136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$30494EB0-B96E-4728-A9B2-0E49B2443BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f72fe478343b372f810333b2cf0db1d68b903856","datavalue":{"value":{"entity-type":"item","numeric-id":792342,"id":"Q792342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$4627E4ED-B82E-4614-A248-FCE89C287BE5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$66A71143-7625-4BB7-9D84-6E5E9FBBDBD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686272$6C661201-A220-4CCD-AE0F-F072ABC717DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c6d2355b6d7a1c589f275fe4a533c5c0a203557","datavalue":{"value":"The domination number \\(\\gamma(G)\\) of a graph \\(G\\) is the minimum number of vertices of a dominating set in \\(G\\), i.e. a subset \\(D\\) of the vertex set \\(V(G)\\) of \\(G\\) such that for each \\(x \\in V(G)-D\\) there exists \\(y \\in D\\) adjacent to \\(x\\). A graph \\(G\\) is called \\(\\gamma_ k\\)-insensitive, if \\(\\gamma(G)\\) remains the same after removing arbitrary \\(k\\) edges from \\(G\\). The minimum number of edges of a \\(\\gamma_ k\\)-insensitive graph with \\(p\\) vertices and the domatic number \\(\\gamma\\) is denoted by \\(E^ k(p,\\gamma)\\). For \\(k=1\\) this number was determined in a previous paper of two of the authors of this paper.   In the present paper the exact value is determined for \\(E^ k(p,1)\\) and lower and upper bounds are given for \\(E^ k(p,\\gamma)\\) in general. In the case \\(k+1\\leq \\gamma \\leq 2k\\) the value of \\(E^ k(p,\\gamma)\\) is proved to be asymptotically equal to \\((k+3)p/2\\). Some properties of \\(\\gamma_ k\\)-insensitive graphs are described.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686272$7479EAD0-0075-4679-BDCA-CC91B7357D01","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686272$1DC41C72-FBD9-4A6D-A35A-FD025397EAC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18cf44d510536f9dde9e96a7343be6c8ecda5bf3","datavalue":{"value":"428119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686272$0020AFCA-EE39-4B57-94A9-1FDD7B1E14B3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q686272$34B7B2F9-A7BF-46C6-A18C-0C70077195B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ffe3ec92bee413dfe42bc11a8db91896e244319","datavalue":{"value":"insensitive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q686272$7B02EB92-7C09-4DCF-AFAB-E8BDADDD6450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q686272$7FF4F875-59DA-4085-B59D-EFE7E16ED662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q686272$70E0D7A1-AA53-4E26-BE91-E7262791E64F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b77b431fc86a92792dc6a21fc772bba2088fb678","datavalue":{"value":"bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q686272$7EF7887D-B68D-4E0C-B7B6-03CD3730B319","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$1D148F4B-6F71-435A-B8CA-1EE89BC62C00","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":"Q686272$9228C798-1515-4436-A60C-871CCD281119","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"682d6c7552197299d8caef727039a36b74670a49","datavalue":{"value":{"entity-type":"item","numeric-id":585222,"id":"Q585222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$33748D85-210B-4358-8698-8C64F3619BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acbb45de9d5a6f63ec383a18059038df8673aa6c","datavalue":{"value":{"entity-type":"item","numeric-id":3807242,"id":"Q3807242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$259B18D9-61EF-4C9C-9DD2-A11682E985A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30cab697c640a17f371de08dad340cb3832f1d33","datavalue":{"value":{"entity-type":"item","numeric-id":3472129,"id":"Q3472129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$9CD54AC4-84C0-467C-A11B-7600C3572127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2599b2af244fe6f48a2ed139b9e8da16b7f0c725","datavalue":{"value":{"entity-type":"item","numeric-id":3983241,"id":"Q3983241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$8E092A45-EE7D-4AF0-9441-751775F91430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f7dd8f2f46f1945c247832502213cf8a0db629c","datavalue":{"value":{"entity-type":"item","numeric-id":1099185,"id":"Q1099185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$98D7178C-EE9D-494A-AA2F-0B52E2FD1205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79ea1a04bb6217c38dcb9e038ffe038761637779","datavalue":{"value":{"entity-type":"item","numeric-id":1096642,"id":"Q1096642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$DE61FB33-DD26-4034-902D-C553144D52DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f76bfad58d0a922c968f1c25d730d571303e5ca","datavalue":{"value":{"entity-type":"item","numeric-id":4346786,"id":"Q4346786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$18A7DEFC-105E-429D-9E21-78D063A2D51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f4bf0bfd443ecf4b5ee50808d44f03c77b92c38","datavalue":{"value":{"entity-type":"item","numeric-id":689974,"id":"Q689974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$CB52599C-92AD-412E-92B5-67412C0DF708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$2488B455-FCC3-4239-89CB-270BDFEE6C89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4871604459f96d584328d9afcf6ee90fd534348f","datavalue":{"value":{"entity-type":"item","numeric-id":4750666,"id":"Q4750666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$786292A8-9F67-4CB2-BC02-7BFB7AE07EBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40ad4a18b1f9f5030e5b463bead064c735ffc704","datavalue":{"value":{"entity-type":"item","numeric-id":3728935,"id":"Q3728935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$D978CEC6-B408-4F72-BC42-F3DE9A83BB0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bb55bcb1962b7390aec2d3fb5c3b0cfbf4132a4","datavalue":{"value":{"entity-type":"item","numeric-id":4014294,"id":"Q4014294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$42FBFD16-2BAE-434A-ADF9-BA193A763468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4787f2f55a27b888d73e01e50105631808ea4a96","datavalue":{"value":{"entity-type":"item","numeric-id":4009711,"id":"Q4009711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$13960863-0694-4940-89F0-A035AEBEE0A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11aca352f7cdec2f7e7ee9f19570cc539e3485d9","datavalue":{"value":{"entity-type":"item","numeric-id":3472128,"id":"Q3472128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$80587426-7606-479F-B218-2A76D4393567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8d67a289ac846c9072b1e9abcdd568db6b78f8f","datavalue":{"value":{"entity-type":"item","numeric-id":5284032,"id":"Q5284032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$444F9E2D-CF03-457D-BA0F-00170AB5F17C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f0cdafb1c9a76f7276d6252de4d9ce331e787aa","datavalue":{"value":{"entity-type":"item","numeric-id":4024335,"id":"Q4024335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$223BC31D-CCD5-4B16-B1CE-6902160FA9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfe75583a89a0422552a553ee6885a9a2d3fdcaf","datavalue":{"value":{"entity-type":"item","numeric-id":4729819,"id":"Q4729819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$9351D527-DC65-4F4E-A7B8-0CC57C440528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1b93646b7344e2978a1adf3a26b2e1bf6b9cd37","datavalue":{"value":{"entity-type":"item","numeric-id":4206379,"id":"Q4206379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$02A88EAF-01ED-4C2C-AF27-53D1BDB325CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4cac13ed2587d1edaf32d5c0bd2d1e04e46a93","datavalue":{"value":{"entity-type":"item","numeric-id":5917319,"id":"Q5917319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$1CF3ABEB-B68E-4D0F-BA2F-7E5C6E492902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5ce00aa76e592e23bfa94ec2ea229c78ed7c12a","datavalue":{"value":{"entity-type":"item","numeric-id":5906153,"id":"Q5906153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686272$FE5BF992-EF55-4A57-A168-91B1DA7CB8F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b7bd46d5ad90bef138d54c129e5213d245150ca6","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90238-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q686272$5FF57062-B058-4823-A450-BC5703F6CE5E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"84dd41443aacd78d69aa24f0390b0d1305232443","datavalue":{"value":"W2006026530","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686272$BAB9CD65-C686-4D63-BDB2-BF85040A51A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9508824314c3acbd00508138a19a015727b43222","datavalue":{"value":{"entity-type":"item","numeric-id":4943518,"id":"Q4943518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ea2243fb296ac5158a33b899411a773f266b26e","datavalue":{"value":{"amount":"+0.9402495622634888","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":"Q686272$557BF765-7673-4202-8527-90E29619DF3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ade9370bb2498734798f12d539a226b7bbce2097","datavalue":{"value":{"entity-type":"item","numeric-id":4729819,"id":"Q4729819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc8da658ca0b9587db94d41ae99dbd1bae9a6c13","datavalue":{"value":{"amount":"+0.914775013923645","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":"Q686272$4630CD4C-ED55-47FC-9CDF-604A0866666E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"717bdd5f5f901cd1ba809fac11372e865e99b993","datavalue":{"value":{"entity-type":"item","numeric-id":1099185,"id":"Q1099185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e3d6276358a2dd18cfd4ca00069fd8da14e3964","datavalue":{"value":{"amount":"+0.896647572517395","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":"Q686272$3F8F0F67-D8DC-493E-B64F-FEAC79C27334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc827a3db41b67f24a495d1065e170222476ae42","datavalue":{"value":{"entity-type":"item","numeric-id":2804776,"id":"Q2804776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd2de655df3c4e1379bdd811739ff67711c9f5b7","datavalue":{"value":{"amount":"+0.8199002146720886","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":"Q686272$578165F8-DEBB-4425-B894-5B6FEAAD51D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7c6f811b807ab3a788e5ee88296dc52859bb48f","datavalue":{"value":{"entity-type":"item","numeric-id":5316258,"id":"Q5316258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aed4628cc34a588bdef58b027827bd7dcdfc1da3","datavalue":{"value":{"amount":"+0.7980321645736694","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":"Q686272$157CEC73-D952-4534-BDF7-077D30FA1D60","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extremal graphs domination insensitive to the removal of \\(k\\) edges","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extremal_graphs_domination_insensitive_to_the_removal_of_%5C(k%5C)_edges"}}}}}