{"entities":{"Q1010858":{"pageid":1012706,"ns":120,"title":"Item:Q1010858","lastrevid":66595395,"modified":"2026-04-12T11:11:11Z","type":"item","id":"Q1010858","labels":{"en":{"language":"en","value":"Global alliances and independent domination in some classes of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541028"}},"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":"Q1010858$01C656D3-68E9-40D5-B5E7-2B748EEEE729","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"501ae4b3053720988f45f7aab5a96dbe38343f19","datavalue":{"value":{"text":"Global alliances and independent domination in some classes of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010858$0A4C4FB2-A1BD-4DB7-9FD5-1B917FDA5EC6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a9fd11689a221cb43d2d49df6fad818d01181ac","datavalue":{"value":"1165.05338","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010858$3B998DC2-01EC-49E6-A78D-BB98029F7C91","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":"Q1010858$1558B985-20DD-41A4-BF3A-27B5A9193602","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010858$494E443C-20A0-42AA-A332-D19ADA8EB063","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0bfe6b941f92eee3567aafea8ed9520f97f48bd","datavalue":{"value":"https://eudml.org/doc/130291","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010858$A21B821E-092A-4DC0-A787-500A57996AE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"61a06c49ac7ab77540cea325121f24c6778d4cce","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r123.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010858$9D9AC5F4-F0E5-4D98-B411-407D91582233","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"455cd921645fab445c908a316f1ccd2a20c986b7","datavalue":{"value":"Summary: A dominating set \\(S\\) of a graph \\(G\\) is a global (strong) defensive alliance if for every vertex \\(v\\in S\\), the number of neighbors \\(v\\) has in \\(S\\) plus one is at least (greater than) the number of neighbors it has in \\(V\\setminus S\\). The dominating set \\(S\\) is a global (strong) offensive alliance if for every vertex \\(v\\in V\\setminus S\\), the number of neighbors \\(v\\) has in \\(S\\) is at least (greater than) the number of neighbors it has in \\(V\\setminus S\\) plus one. The minimum cardinality of a global defensive (strong defensive, offensive, strong offensive) alliance is denoted by \\(\\gamma_a(G) (\\gamma_{\\hat a}(G), \\gamma_o(G), \\gamma_{\\hat o}(G))\\).   We compare each of the four parameters \\(\\gamma_a, \\gamma_{\\hat a}, \\gamma_o, \\gamma_{\\hat o}\\) to the independent domination number \\(i\\). We show that \\(i(G)\\leq \\gamma ^2_a(G)-\\gamma_a(G)+1\\) and \\(i(G)\\leq \\gamma_{\\hat{a}}^2(G)-2\\gamma_{\\hat{a}}(G)+2\\) for every graph; \\(i(G)\\leq \\gamma ^2_a(G)/4 +\\gamma_a(G)\\) and \\(i(G)\\leq \\gamma_{\\hat{a}}^2(G)/4 +\\gamma_{\\hat{a}}(G)/2\\) for every bipartite graph; \\(i(G)\\leq 2\\gamma_a(G)-1\\) and \\(i(G)=3\\gamma_{\\hat{a}}(G)/2 -1\\) for every tree and describe the extremal graphs; and that \\(\\gamma_o(T)\\leq 2i(T)-1\\) and \\(i(T)\\leq \\gamma_{\\hat o}(T)-1\\) for every tree. We use a lemma stating that \\(\\beta(T)+2i(T)\\geq n+1\\) in every tree \\(T\\) of order \\(n\\) and independence number \\(\\beta(T)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$ABFA7D37-C42B-4EEC-A95C-BC657ED717F5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010858$09CD6E71-410C-4679-8F1F-F1F81D644010","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c7f73484af46d69005465066bf2771247c817dd","datavalue":{"value":"5541028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010858$3F4976D5-CFA1-4C55-8D54-45A46B250707","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$9931F3E6-F6FF-4B6C-91A2-6DE81704AA70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84ee2e64b510210b7709d6624f71953512c4c791","datavalue":{"value":"global defensive alliance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$8593D271-587F-43BD-BD84-09ED1697EB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98ff052d26f2571b15ce1b09a595574ac5b34251","datavalue":{"value":"strong defensive alliance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$F45FE8F0-B330-409C-95DB-1973CF702035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df20c3adea3710d1e76baed03bc32488ff90715c","datavalue":{"value":"global offensive alliance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$79515F9D-A804-418B-9CCB-633CCDA5AAE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2418ea2dd4d6a174b920ddc626a52a8187b3c96","datavalue":{"value":"strong offensive alliance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$C4689BCC-ABC9-4C64-B342-4F22C6529C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b9cb36124705ee2c1ebad747daa00eac41972d4","datavalue":{"value":"independent domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$6E5F5C30-2177-4769-9206-6AEA8CF536F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010858$799909D6-B809-4267-B688-3F0551B685E9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c24108deece21e1bd02c5605dc19efffc727ac45","datavalue":{"value":{"entity-type":"item","numeric-id":237422,"id":"Q237422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010858$64D1CAA2-5114-4130-9DB8-15EF8FBC8691","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":"Q1010858$B6BA0E03-3092-4B45-9333-E9DF4699BA97","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d327fff35a637816abc272c5eaa0c13f577a3676","datavalue":{"value":"bafkreihgdg3czj5czpvjcah7zblr7gmm7w6hsl6ikpjv4jjeuqdgwgl52y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010858$587F6968-41E8-472E-9F90-58FA88B6F508","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"508dcbeb0f799c96ef8892570fb9d3ab3214bb18","datavalue":{"value":{"entity-type":"item","numeric-id":5444052,"id":"Q5444052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81d30d1049d615572f343118d26a6ae41c318322","datavalue":{"value":{"amount":"+0.9237080812454224","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":"Q1010858$F2A0439C-0D00-4ECE-B312-FDEA1E261CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8df1e89f9828017e165abea600f9cafcd13d38ef","datavalue":{"value":{"entity-type":"item","numeric-id":3144633,"id":"Q3144633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bc10151ffe42590346442fff402b8cf8d887a0f","datavalue":{"value":{"amount":"+0.9137747287750244","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":"Q1010858$D18E1305-7EBB-4998-B7F3-B4BC1653C827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a7c2fa47e6abb6d8e65c7469101f3e9e77ae1f9","datavalue":{"value":{"entity-type":"item","numeric-id":2341731,"id":"Q2341731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e27402cb8c3643234dccadfbb091a7565059033","datavalue":{"value":{"amount":"+0.8810089230537415","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":"Q1010858$FD590499-0EB4-4BD5-A3E4-23E882243861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d49e8b700e5951faf5e836ff146993acd99b4617","datavalue":{"value":{"entity-type":"item","numeric-id":2446301,"id":"Q2446301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d5cd8b7a922a065d695db4f6da8281e832fd2d5","datavalue":{"value":{"amount":"+0.8789023160934448","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":"Q1010858$31DA7091-39B9-4DDA-8B42-EEA567C96D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a908490da958c948a758e2e4fe63fb308251768","datavalue":{"value":{"entity-type":"item","numeric-id":3004155,"id":"Q3004155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e8c30dad368574ffd77f6f0ded8e5d69dc10181","datavalue":{"value":{"amount":"+0.8768224120140076","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":"Q1010858$E4BB4D6C-D878-4E33-8204-60B7BED2AA87","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Global alliances and independent domination in some classes of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Global_alliances_and_independent_domination_in_some_classes_of_graphs"}}}}}