{"entities":{"Q1301709":{"pageid":1312459,"ns":120,"title":"Item:Q1301709","lastrevid":68519265,"modified":"2026-04-13T00:15:08Z","type":"item","id":"Q1301709","labels":{"en":{"language":"en","value":"On independent domination number of regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1334522"}},"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":"Q1301709$B054DF64-87E2-4833-9C83-77CA5FCCD6B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a1fe9d1d4e31e1f890e4db8775b5b7a6aa9e7fc","datavalue":{"value":{"text":"On independent domination number of regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1301709$27FE4542-1371-4072-96ED-F4EE9DB957FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d1e399cd3b5d1c4913eec2ba8fd4e15e6ffd1a0","datavalue":{"value":"0934.05098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301709$257D902B-B6B8-4F17-A620-67E96867B1F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"120d54226d00c849a24f1e61030a020b24574bd3","datavalue":{"value":"10.1016/S0012-365X(98)00350-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301709$711618C2-0098-458B-89F8-39724D17BABA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f18871f07d7d6276ddb2f83478f385ae198a08f4","datavalue":{"value":{"entity-type":"item","numeric-id":221700,"id":"Q221700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$2D0625CA-3C6A-4E20-8CAD-DB25FA0E2A12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29ce36bdf3b0def5b13e2fa2ec92f80aa44a2edf","datavalue":{"value":{"entity-type":"item","numeric-id":273454,"id":"Q273454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$1B3C8049-9E5D-4F6F-BED8-D35CEB019F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"912c1369862ac9eb4f32c398e12f24c622ebcb0e","datavalue":{"value":{"entity-type":"item","numeric-id":221699,"id":"Q221699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$42BD295C-1E0F-42CF-8549-33ED5113C858","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":"Q1301709$D9EF1064-FA15-470A-9A82-AD16C11E0E69","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b78ba432cb77ac64be3ac5d97bd170fc19fe3117","datavalue":{"value":{"time":"+2000-04-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1301709$E417CF66-037F-4C2C-BB41-E5BD046EB88F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a78096957e4acc12f22e5911c7c97398951000d","datavalue":{"value":"A subset \\(S\\) of the vertex set of a graph \\(G\\) is called independent, if no two of its vertices are adjacent in \\(G\\). An independent set in \\(G\\) is maximal, if it is not a proper subset of another independent set of \\(G\\). The minimum number of vertices of a maximal independent set is the independent domination number \\(i(G)\\) of \\(G\\). A conjecture of J. Haviland says that a regular graph \\(G\\) of degree \\(\\delta\\leq n/2\\) (where \\(n\\) is the number of vertices of \\(G\\)) has \\(i(G)\\leq\\lceil 2n/3\\rceil \\delta/2\\). In the paper this conjecture is disproved by giving two counterexamples. Then for a connected cubic graph \\(G\\) with \\(n>3\\) vertices the inequality \\(i(G)\\leq 2n/5\\) is proved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301709$B1471DB7-A9BE-4009-961D-70264D7345BB","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":"Q1301709$5C0DDE1E-3EF2-4D64-B61E-6789B871195D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301709$BC9C2058-801C-491E-8FCB-8847C04144AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301709$51A560FC-431B-4269-9E96-D0580C7BE252","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5acb8d9191343b6410d4a07855d8c75cf0771598","datavalue":{"value":"1334522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301709$8AA5C748-CD16-4C3A-8F4B-DA1629BFB8C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301709$DD6EAF84-72FA-4B6C-BF6D-6AA8EEF5CAB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b9cb36124705ee2c1ebad747daa00eac41972d4","datavalue":{"value":"independent domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301709$83D249D7-077E-47BD-8471-8C7D822553D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301709$26A856AF-6F47-4B9E-8E9E-AD08EA3E1462","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":"Q1301709$05019AB2-7800-4C12-9618-F91F3FE408CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09ccef5d22adbb759c6c69df3c2f7da668697a40","datavalue":{"value":{"entity-type":"item","numeric-id":3208702,"id":"Q3208702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$F1AB2468-7F82-4B31-8A9E-B01697E0D596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be07bab3aaa85f46eab6318eb309abad892d183c","datavalue":{"value":{"entity-type":"item","numeric-id":1179268,"id":"Q1179268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$11057585-7025-47BF-9AE2-D7E7A15B895E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03dc55bd228ad5f447b3d39106ed210cc5daa457","datavalue":{"value":{"entity-type":"item","numeric-id":1157348,"id":"Q1157348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$3964C2A4-524F-4113-99BC-FCEB042D61D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdf2aff3fc591cb51cb4bec2282d182a8e53f89c","datavalue":{"value":{"entity-type":"item","numeric-id":1842161,"id":"Q1842161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$F9871A35-83D6-48B3-B489-4C4037327959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d90fd75a562853e17fa1faf81bf2772f8c975a1","datavalue":{"value":{"entity-type":"item","numeric-id":4060985,"id":"Q4060985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$C83D4866-064A-4015-950B-E938EE893A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b451bf358852885ca83aea699507e4f2cfd1fcc3","datavalue":{"value":{"entity-type":"item","numeric-id":1100217,"id":"Q1100217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$1C77AE9E-1258-4AAE-812E-518215B7C547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a87159a81b435c231f8c95b3b4db312e493a98c8","datavalue":{"value":{"entity-type":"item","numeric-id":1182974,"id":"Q1182974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$A9A0EBA5-CD2C-4BE3-BEAF-87C2CA9CE728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6303f6ff9f945b492e5fe2a1c1fb79e71b6fc66c","datavalue":{"value":{"entity-type":"item","numeric-id":1897445,"id":"Q1897445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$5C2610D1-A8AD-428D-9778-456D22E2300F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6886ba90c5b25f06766b8495ec24fd320596293a","datavalue":{"value":{"entity-type":"item","numeric-id":810066,"id":"Q810066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301709$74804A78-450D-4D0F-94B0-8D275FC05A76","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d025d824b0072d5760e3a01fe8319e3f642942ef","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(98)00350-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1301709$6DBC564B-44D9-4E20-9653-9E2482E13140","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"43ecebea415c129d16efb193e0879d4758e99e10","datavalue":{"value":"W2127967904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301709$0DC697A4-3511-4BCD-A95D-78732E4AB3E6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1a8d68eb8bab60fe877322ab595bf2c5a49d836","datavalue":{"value":{"entity-type":"item","numeric-id":1897445,"id":"Q1897445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df379d182842e7b1df80100a50495b3e122dcfb0","datavalue":{"value":{"amount":"+0.8713199496269226","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":"Q1301709$BF89D359-D75B-4F9D-B380-8FB8B5F0BEEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c33281ff2a5bc60b388250ffa0a47e273971327","datavalue":{"value":{"entity-type":"item","numeric-id":6047642,"id":"Q6047642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a814d13e8a50b66ebff3c564b1727218154ab4f6","datavalue":{"value":{"amount":"+0.8674106597900391","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":"Q1301709$35711615-ACA5-41C8-B59B-9F2BF4C78860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c3ce09b5912f83f73fcb24efea977c8f5c2c401","datavalue":{"value":{"entity-type":"item","numeric-id":358646,"id":"Q358646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a985cf275f45f6c72ffcc90144ae9b232c10ade6","datavalue":{"value":{"amount":"+0.85817950963974","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":"Q1301709$67E43AD9-A78B-46CF-A532-4EE04C46D1EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b673da38a49c1e257fc4057e4b5a995f3d94f6f1","datavalue":{"value":{"entity-type":"item","numeric-id":3366736,"id":"Q3366736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1127fd0bfcbc275bab00a77d1eef019731a48ab7","datavalue":{"value":{"amount":"+0.8528271913528442","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":"Q1301709$C3C9BCBC-DE4F-449D-A551-58B7DD1381E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On independent domination number of regular graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_independent_domination_number_of_regular_graphs"}}}}}