{"entities":{"Q1010776":{"pageid":1012624,"ns":120,"title":"Item:Q1010776","lastrevid":50626382,"modified":"2026-01-14T14:56:26Z","type":"item","id":"Q1010776","labels":{"en":{"language":"en","value":"On rainbow connection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540962"}},"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":"Q1010776$8CF38495-1347-45DC-9382-67FED01F53ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"948b069218c489ff82c51b7e0f9749bf0db36aef","datavalue":{"value":{"text":"On rainbow connection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010776$537477BA-A339-43D2-BDDD-6D188E52FD77","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"470815e412e4e80710d6446bb841f612fb5b98c5","datavalue":{"value":"1181.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010776$4BF55032-AAE2-4C77-960C-2EEDBCE4EA64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ed6f21f55f5293ad80f20217ff98c9b7054441c","datavalue":{"value":{"entity-type":"item","numeric-id":168472,"id":"Q168472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010776$50E828D7-C104-4DD7-AD9E-B4DEE9E68530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"218f7dc4b63685dca32c01e904fc698ab2233c31","datavalue":{"value":{"entity-type":"item","numeric-id":590620,"id":"Q590620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010776$94D7C3C7-C311-4C9C-AE83-4A7CB0E2D1DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010776$FF567C84-86BA-426C-BB35-02FF50F61FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58695e9da83c43913be67e6d6be310d1075b58c8","datavalue":{"value":{"entity-type":"item","numeric-id":222643,"id":"Q222643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010776$B353E4EA-1CC8-410E-A009-35C3246066D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25a32996527fb9f7f92377ce267da4c66375a6da","datavalue":{"value":{"entity-type":"item","numeric-id":222514,"id":"Q222514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010776$767A45E9-F2B7-4555-96AA-38368C7DF9E3","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":"Q1010776$CB4906F6-7807-45D7-9D9F-825677167EAA","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":"Q1010776$43103CD4-ECEA-4A6C-8FFA-78946530B6D0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b218a12d142eb2c0bc65736879b8db87032c7eca","datavalue":{"value":"https://eudml.org/doc/117241","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010776$79C0972F-87A1-452A-B2E4-775CB394BB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a2c6538d99890f2b58e794e29d38a38fcb8bbc44","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r57.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010776$1023EBBD-2EBC-4DE6-8A9F-E98976123E77","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3ba7260e0c4506f935d937188ada098568e931d9","datavalue":{"value":"Summary: An edge-colored graph \\(G\\) is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph \\(G\\), denoted \\(rc(G)\\), is the smallest number of colors that are needed in order to make \\(G\\) rainbow connected. In this paper we prove several non-trivial upper bounds for \\(rc(G)\\), as well as determine sufficient conditions that guarantee \\(rc(G)=2\\). Among our results we prove that if \\(G\\) is a connected graph with \\(n\\) vertices and with minimum degree 3 then \\(rc(G) < 5n/6\\), and if the minimum degree is \\(\\delta\\) then \\(rc(G) \\leq \\frac{\\ln \\delta}{\\delta}n(1+o_\\delta(1))\\). We also determine the threshold function for a random graph to have \\(rc(G)=2\\) and make several conjectures concerning the computational complexity of rainbow connection.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010776$BD3E70DF-BB2E-4DF6-AF77-2E880AD3F510","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010776$C61EF860-E97D-40D0-B3BD-7EC07ADF2378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010776$CF299877-94C0-4AA3-BB44-0D4DEED56FD3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b8db794afec6d40b938d8acb3af7383a1ae95a3","datavalue":{"value":"5540962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010776$3A09E6E9-C7CC-4438-A485-5937CD9521FC","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":"Q1010776$14C573FF-9A01-479E-AC30-D5DFED5EBE62","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2a0df668af113cb3ef5bd2adf23656f6c4664ea6","datavalue":{"value":"bafkreia4g7pgb5l4mkhjzlc4ifaloe2en2x23uzmp4dmawctwwyyv2he3q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010776$AFDFF6B3-5D11-4F1F-8573-020A5FAA3D81","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"899946cadbb0ea1fc0429bc3ed91c9f559e912f6","datavalue":{"value":{"entity-type":"item","numeric-id":2446307,"id":"Q2446307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a8a649b57e3f15f91be168a534b6a222ce44288","datavalue":{"value":{"amount":"+0.928444802761078","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":"Q1010776$B43DCE16-535D-44AA-83FF-65DE0E7082F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"798a7c87db8e79bf356d83d85cf10febf55e5439","datavalue":{"value":{"entity-type":"item","numeric-id":3089362,"id":"Q3089362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61694461fab14413394eabe3da2bd39ab87cb3a4","datavalue":{"value":{"amount":"+0.9226384162902832","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":"Q1010776$340686FA-80C8-41A8-AE40-374CD220E5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abbe898983c5803efb43cf7ef15677c738a8aafe","datavalue":{"value":{"entity-type":"item","numeric-id":3134374,"id":"Q3134374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25b492ecc1b6ea4807aff032786b06871d435180","datavalue":{"value":{"amount":"+0.920839786529541","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":"Q1010776$4578BD64-15E6-4159-99A8-304CC05CB685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cafac1d4d72b0e90c15476f7f748adeb327c521","datavalue":{"value":{"entity-type":"item","numeric-id":426778,"id":"Q426778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35349d96f28bd35a7a096c9a65e140f97a6e1ab5","datavalue":{"value":{"amount":"+0.9203771352767944","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":"Q1010776$C1567EED-BCD5-4A27-A532-023968558234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c580c070629bb0ea563cd8cc9eb29e404acc6f4e","datavalue":{"value":{"entity-type":"item","numeric-id":2857035,"id":"Q2857035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5602d26d3623a8b8b1836f694ec9a5f0e25ad6d2","datavalue":{"value":{"amount":"+0.9150987267494202","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":"Q1010776$493A3066-2AA3-4B15-9BE1-B3B632544429","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1010776","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1010776"}}}}}