{"entities":{"Q804593":{"pageid":806441,"ns":120,"title":"Item:Q804593","lastrevid":49504417,"modified":"2026-01-07T09:05:49Z","type":"item","id":"Q804593","labels":{"en":{"language":"en","value":"Label-connected graphs and the gossip problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4202297"}},"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":"Q804593$CD6DC8FC-0D74-4700-A059-2C6FF4AD1BB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40f0ea3b6bbd3405659cdf46e5c70ac834c2f194","datavalue":{"value":{"text":"Label-connected graphs and the gossip problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804593$F1947EBB-EF5E-4BFB-8F3B-C8F4F43A1EFD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"543b81557f30eb0bcd3c519a9fae3870ab8da7e8","datavalue":{"value":"0728.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804593$488ECD2F-12EA-463A-BF34-3DEE61A3199B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"61a0e707e8b1ca83dd93eb35ade0b69c4272ebd3","datavalue":{"value":"10.1016/0012-365X(91)90068-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804593$D180421C-FBD0-4200-8F5A-AA69AE01D0C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$87331263-5FD5-4203-821B-B184C4455CB8","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":"Q804593$5485C3AC-A480-4AFA-96DB-34523F9458A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q804593$A6EE0212-5C02-469C-9EC1-F5A3C9970E32","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"883cc837eaf48727bbd5b9d57281a12eb25a4d45","datavalue":{"value":"A graph G is called label-connected if the edges of G can be labeled by real numbers so that for every pair (u,v) of vertices of G there is an (u,v)-path with ascending labels.    It is shown (using the gossip problem) that the minimum number of edges of a label-connected graph on n vertices is 2n-4. A necessary and sufficient condition for a graph to be label-connected is given. It is proved that recognizing label-connected graphs is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q804593$3D1348DC-173D-4888-AFA7-D7552AE4AFAB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804593$67B15AB2-B450-40FA-A040-1141BD7DA8E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804593$7EBBCBE7-2C38-4EC1-A2A6-F4EC27D877BA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5af9620015f4a9372bc888c313d25b8b4990c6d3","datavalue":{"value":"4202297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804593$D3440639-90E0-45A1-A039-88C6AEA03B4F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3946528c6d53dd2fc4671d007426f3675a119939","datavalue":{"value":"label-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q804593$0865CCA3-B63E-484F-8DE1-D9C1FE16850E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ef22b67971c907f35c542e2435922e6c49358d32","datavalue":{"value":{"entity-type":"item","numeric-id":215558,"id":"Q215558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$D7583961-C6E0-4A32-A980-F049D177FABE","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":"Q804593$8BB5CBB9-F06C-4366-80F7-045C47A0FB5F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$F05BD35D-D6BF-4480-AEEB-195BCC107E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57aa445ce93c961a27ea171e6b5d4df9eca8d93d","datavalue":{"value":{"entity-type":"item","numeric-id":3964600,"id":"Q3964600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$0E13B7B5-B6EE-44FE-A242-C8EFF10584A8","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":"Q804593$E431A305-0E65-4475-966D-676DE78428FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f99a7365a988929af4354623873832605945d6d","datavalue":{"value":{"entity-type":"item","numeric-id":1217715,"id":"Q1217715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$BCA260A1-D3E2-4558-B92A-96248610EABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbf25094a358003b024272470efe42a5072f8154","datavalue":{"value":{"entity-type":"item","numeric-id":1144577,"id":"Q1144577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$B5644B33-B6B7-48BA-BBD3-E73E19767882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$DC55F2BF-EBC1-43D3-AB18-7A730310C0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"711cb68a3f23253ea3bfc5d62858e204e53a49ca","datavalue":{"value":{"entity-type":"item","numeric-id":3286077,"id":"Q3286077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$99040DBF-7822-42B6-8B7C-072586F54B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdb68a6c93b064efcfd440472a9055852b0c2ec","datavalue":{"value":{"entity-type":"item","numeric-id":3275433,"id":"Q3275433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804593$EF6BBAF8-95F3-4C35-A7D3-A20D21641526","rank":"normal"}],"P1643":[{"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":"7c359cc59ad655381d677943a675d177f6c1b528","datavalue":{"value":{"amount":"+0.7865524291992188","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":"Q804593$E204BB7F-F260-45AE-99F1-66BF8F7C9F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"842e3ad8f1460effcf31245c9ffa3ca1ccd73c61","datavalue":{"value":{"entity-type":"item","numeric-id":1372291,"id":"Q1372291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"476b888c7fb0cd16c7ddbf2e5a83141885401eed","datavalue":{"value":{"amount":"+0.7804703712463379","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":"Q804593$5E4C2A00-CC0A-458E-B786-5655AD706E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d624333ecc0fd94ad3a09eb944b2406d96583e2","datavalue":{"value":{"entity-type":"item","numeric-id":1342244,"id":"Q1342244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bea9e67f61fc6caefc1e4fde4818c52ee8669d6d","datavalue":{"value":{"amount":"+0.774533748626709","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":"Q804593$1B24CA4E-0645-4D4B-8F45-E6CB72D803B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"252352d986272834192d58efbd1d8bd354dfce4f","datavalue":{"value":{"entity-type":"item","numeric-id":1382273,"id":"Q1382273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4d4ee3b180a7794793582fb915db95bab8f6d75","datavalue":{"value":{"amount":"+0.7715118527412415","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":"Q804593$7743F429-AFEE-4166-B718-4BA06D0F6E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15960a3ad930362961765098bb7326e5fb94a5e1","datavalue":{"value":{"entity-type":"item","numeric-id":3686395,"id":"Q3686395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5578f2e9d381161e4b26efe2bd6cf02a56cf8073","datavalue":{"value":{"amount":"+0.7624561786651611","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":"Q804593$4704FCD7-D0D8-42F1-8289-27FADEBDEE97","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:804593","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:804593"}}}}}