{"entities":{"Q4393345":{"pageid":6422944,"ns":120,"title":"Item:Q4393345","lastrevid":108350585,"modified":"2026-11-06T01:40:53Z","type":"item","id":"Q4393345","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1161346"}},"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":"Q4393345$3FDFA321-5AF6-4007-A1A7-33ACDB2083B0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b087b039c292c2b48c77e98867bc32493184d2f","datavalue":{"value":"0901.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4393345$0130FCDD-D8A3-43C1-BEE5-036EEF87EAB5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"67a3b32ce23d643b75c3ac5e86ed1ffe82868638","datavalue":{"value":{"entity-type":"item","numeric-id":186199,"id":"Q186199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4393345$86867F57-16CB-42E9-A14D-02DDCFA783C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ef3efb47b5163e35efff4dde79a3bbdd3dc566b","datavalue":{"value":{"entity-type":"item","numeric-id":186200,"id":"Q186200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4393345$35DB55A6-CBB6-41FD-BBE1-6AC28DF38A66","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3582025f16a6b7ba569a61673d5fcbf2288a9f39","datavalue":{"value":{"time":"+1998-11-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4393345$E88EBCF2-C894-4411-BE71-6E37A200D5F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4393345$5AD791D9-A415-42E7-AD43-D2ED546FAD18","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45f9ce6ac1101cb5b67079125e7a187aee20fe0f","datavalue":{"value":"1161346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4393345$2B0F8557-72C0-4176-859C-8B2AC74E956F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q4393345$D617FAB6-2613-4B95-B6FB-419066EBE0A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q4393345$2761FCEB-9EA6-4DE3-8550-C0152DC90C87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q4393345$8120D53A-7519-4CA5-BC47-1E6B858218BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a03b29c3c3bd12122efbd3925879333e3db42e5","datavalue":{"value":"Gallai-type results","type":"string"},"datatype":"string"},"type":"statement","id":"Q4393345$1A174918-F962-4878-B4FF-E50A5EF1F7F5","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":"Q4393345$D7BFA367-2D1F-4681-AC85-B0BFE59F3C1E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b028539874778ef969e3c6452ebd73195e328e2a","datavalue":{"value":{"entity-type":"item","numeric-id":4814435,"id":"Q4814435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eefa2699c219f74937b2cdf0ec2ebcb7744ec62","datavalue":{"value":{"amount":"+0.8366754651069641","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":"Q4393345$017C6402-3116-4AD2-B38B-B454A4F98E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d85222025c67d38feb7c0b4f894de56bf8abd305","datavalue":{"value":{"entity-type":"item","numeric-id":4368817,"id":"Q4368817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3515324e63f8464d781e502c86560cc2cbf08c9","datavalue":{"value":{"amount":"+0.8180165886878967","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":"Q4393345$8F9F6A37-DAFC-48A7-A295-602F80FA2390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11121be9d745e30af38a7c3061da3fd82f2ea9f3","datavalue":{"value":{"entity-type":"item","numeric-id":4390650,"id":"Q4390650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22c0858617d1ab1f9e0e98c99092b643322e2282","datavalue":{"value":{"amount":"+0.8039735555648804","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":"Q4393345$9B6C09F3-5A1A-44B2-A070-35DBCF85F7D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13b2eefc4c45d5110ba994c3157817ec091e75a6","datavalue":{"value":{"entity-type":"item","numeric-id":1584435,"id":"Q1584435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffedab523c7b89459565c81e8a59105d1bf687ef","datavalue":{"value":{"amount":"+0.8037762641906738","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":"Q4393345$0926A0C2-7008-49C9-B278-2B68183E6121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a5a3c42f1532b1396b47ba4eb79927373efcfba","datavalue":{"value":{"entity-type":"item","numeric-id":2968688,"id":"Q2968688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57fabe53a160d839bb783a602abc2450074c92a3","datavalue":{"value":{"amount":"+0.800771951675415","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":"Q4393345$04678C6F-A61B-4A59-BBEB-CACE33A5BD88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07f6291552ff68ab4dfa7f6eaaadb6ee6270a8cc","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph and let \\(S\\subseteq V\\). For \\(v\\in V\\) denote \\(N(v)=\\{u\\in V\\mid uv\\in E\\}\\) and \\(N[v]=N(v)\\cup\\{v\\}\\). Extend these definitions on \\(S\\) by setting \\(N(S)=\\bigcup_{v\\in S} N(v)\\) and \\(N[S]=N(S)\\cup S\\). The authors generalize such notions as domination number, independence number and others by introducing the function \\[ f(S;i,a,d,z)=i\\cdot | I(S)| + a\\cdot | A(S)| + d\\cdot | \\partial(S)| + z\\cdot | Z(S)|. \\] Here \\(I(S)=S-N(S)\\), \\(A(S)=S\\cap N(S)\\), \\(\\partial(S)=N[S]-S\\) and \\(Z(S)=V-N[S]\\). Denote \\(f(G;i,a,d,z)=\\max_{S\\subseteq V} f(S;i,a,d,z)\\). The paper is devoted to properties of this function. It is shown that \\(-f(G;-1,-1,0,-\\infty)\\) is the independence number of \\(G\\), \\(-f(G;-1,-\\infty,0,-\\infty)\\) is the independent domination number, \\(f(G;1,-\\infty,0,z)\\) is the independence number for any \\(z\\leq 0\\). Similar equalities which involve some other graph parameters are established as well. Moreover, the function in question is in a sense monotone, i.e. if \\(a\\geq i\\), \\(d\\geq z\\) and \\(e\\) is an edge of the complement of \\(G\\) then \\(f(G+e;i,a,d,z)\\geq f(G;i,a,d,z)\\) and conversely if \\(a\\leq i\\) and \\(d\\leq z\\). As further results some Gallai-type equalities are derived. Furthermore, it turns out that for any tree \\(T\\) and fixed \\(i,a,d,z\\) the number \\(f(T;i,a,d,z)\\) can be computed in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4393345$68275CE9-2961-4143-9B62-E1D42E2D3260","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4393345","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4393345"}}}}}