{"entities":{"Q1372291":{"pageid":1383031,"ns":120,"title":"Item:Q1372291","lastrevid":68575212,"modified":"2026-04-13T00:40:01Z","type":"item","id":"Q1372291","labels":{"en":{"language":"en","value":"The e-mail gossip number and the connected domination number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1085379"}},"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":"Q1372291$28B1F1E9-4EEC-4E7C-B7C8-8B458817E5B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"944af4c4ad2416d9f2a9994a9caf09ae3c6b6c10","datavalue":{"value":{"text":"The e-mail gossip number and the connected domination number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1372291$21D635CE-0F00-4A06-94F8-1798832BB9A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"33c0b8cef50f2821e340e274b09c61876ea1e830","datavalue":{"value":"0883.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1372291$5F559536-CB04-45AD-B60D-F3F2FFBAB163","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"06c30ba45037e9eb03d87fd3f878ac235af1a915","datavalue":{"value":"10.1016/S0893-9659(97)00052-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1372291$20780F89-1806-4741-948E-C2391911BF28","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"60e92c9f06012150d8158f8bfafc8319965c5fdc","datavalue":{"value":{"entity-type":"item","numeric-id":176247,"id":"Q176247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1372291$63527FD1-2D9D-48E2-BD82-787AC4CF2F3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8141be5ff2c11eb27edb64ba8665d0c363a5621b","datavalue":{"value":{"time":"+1998-03-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1372291$089AC247-B5A8-4964-A2C2-715995C8989B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"183c0522fb08ace12a90b82e4f25f57831669746","datavalue":{"value":"A new numerical invariant of a graph, named the e-mail gossip number, is introduced. The vertices of the graph are considered as persons; each person knows an information which is not known to any other person. The edges represent direct phone connections. Each person sends e-mail messages to the others; always such a message is sent to all neighbours of the given vertex at the same time. The minimum number of such messages needed for each person to acquire all items is called the e-mail gossip number \\(\\text{eg}(G)\\) of the graph \\(G\\). In the paper it is proved that \\(\\text{eg}(G)= n-1+\\text{cd}(G)\\), where \\(n\\) is the number of vertices of \\(G\\) and \\(\\text{cd}(G)\\) is the connected domination number of \\(G\\), i.e. the minimum number of vertices of a dominating set of \\(G\\) which induces a connected subgraph. At the end, it is proved that the problem whether \\(\\text{eg}(G)\\leq k\\), for a given \\(G\\) and given integer \\(k\\), is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1372291$9E3BB1C6-9E03-471D-9D70-674098394C7F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1372291$22C42576-DDDF-4D38-9944-2F11A0D5EA9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1372291$60AB5F47-1706-47AA-A4B3-EA0C04807931","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f0d3f9da1c677debbb30638cfb69c8382b85717","datavalue":{"value":"1085379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1372291$6F8C9A0F-7344-4EF1-8033-A1842DAD2343","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf5dd3743b03236014dbcf1ef9cc6f7ca6dda2b9","datavalue":{"value":"e-mail gossip number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1372291$5C0DF84B-9A5D-4380-B2C1-1A10DCB86A45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924979e39df53c43e61bddb3e36d2617afacd37b","datavalue":{"value":"connected domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1372291$C210EA9A-0F1B-4430-839F-B72C0262515F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06d35deff844ad14009ec831196ab8a1bd18feeb","datavalue":{"value":{"entity-type":"item","numeric-id":293362,"id":"Q293362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1372291$059CC229-8D3F-45B9-80D6-712BAB563081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8dfa84db11a180db135dbd3dcd59aa7a291f852","datavalue":{"value":{"entity-type":"item","numeric-id":1026236,"id":"Q1026236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1372291$14F96AEA-E5AA-4486-B0F7-5164A6F79E81","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":"Q1372291$CB34C609-C8BE-42ED-912F-5EEE32F415BD","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":"Q1372291$4F748BB8-7599-4C24-B0DE-75268D4A7809","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f7cc95bf9ecef18985f9d57c90c0389960c41a","datavalue":{"value":{"entity-type":"item","numeric-id":3895508,"id":"Q3895508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1372291$682125B4-BD7B-4910-AB4F-62DFD3735676","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":"Q1372291$36A89514-DB86-4317-812F-1DD587512869","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":"Q1372291$73BD3DB3-089B-4A5B-971A-B77D0E251D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1372291$61FC2F77-08AD-405D-BC97-F759306781B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0a4612bfee47bbb8e88f370f4ded68db81dae8a","datavalue":{"value":{"entity-type":"item","numeric-id":804593,"id":"Q804593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1395453bb51adeb1b13b9d1dd51d5f36f8fe17f","datavalue":{"value":{"amount":"+0.7546197772026062","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":"Q1372291$B9E50C5F-3B74-4FC7-B037-439A18CB24B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afacdb4edc6b92c742cbc21c415beb7b631be6ba","datavalue":{"value":{"entity-type":"item","numeric-id":5289378,"id":"Q5289378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19856adcd877126c8e22c818bd45e4c58da4287b","datavalue":{"value":{"amount":"+0.7452758550643921","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":"Q1372291$5205A710-7E02-4E76-A40D-CAD1B2A61062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97f6d35130929836101a114f54a7039b6ff5352a","datavalue":{"value":{"entity-type":"item","numeric-id":1318840,"id":"Q1318840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b640f3dcf8bfe109ac95348dfe3aa74570cf049b","datavalue":{"value":{"amount":"+0.7360742092132568","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":"Q1372291$433E8B46-6205-440E-96B0-AFEFF3803316","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The e-mail gossip number and the connected domination number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_e-mail_gossip_number_and_the_connected_domination_number"}}}}}