{"entities":{"Q2410035":{"pageid":2420778,"ns":120,"title":"Item:Q2410035","lastrevid":55903036,"modified":"2026-02-21T00:18:52Z","type":"item","id":"Q2410035","labels":{"en":{"language":"en","value":"Upper bounds of proper connection number of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6791742"}},"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":"Q2410035$142612E7-00DA-43FF-93D0-45070F1B8C80","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f6cb4b5f28f33325e0b2f5d73c20fca87f4e7e4d","datavalue":{"value":{"text":"Upper bounds of proper connection number of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2410035$A872DDD7-E6CA-4AD6-A58C-205BE28EE953","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e31799eb538e07f8625a21c174309f4b0085303","datavalue":{"value":"1383.05102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$3AA6DAF0-B086-41B6-BEF3-8DD744119E9F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1e613e0d759c333ccd45ad5cc7a0d6159ddf47e","datavalue":{"value":{"entity-type":"item","numeric-id":245724,"id":"Q245724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$13A178A1-C87D-485E-B3A3-BCDB83AB2840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e538013e327176b97e08762f6e81dccb0f4bfb9e","datavalue":{"value":{"entity-type":"item","numeric-id":471941,"id":"Q471941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$3EFD3141-1E72-4D69-8FA8-643C0E964B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bf6b57361b3180efb360b271887d95e01377385","datavalue":{"value":{"entity-type":"item","numeric-id":831023,"id":"Q831023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$3FADBA8D-C824-4ABB-8D1D-2756F86FFC08","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$DCB17BEC-818E-4BDD-AD8F-65C4D2958CC9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eae4cdb5001296cfa1d627ad5453506a5832f064","datavalue":{"value":{"time":"+2017-10-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":"Q2410035$73DCC975-39CA-442B-9CD2-816E72455415","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05f1bc9ac82aae4e21e14fa5df08fb893ceaecbe","datavalue":{"value":"The authors study the proper connection number of graphs, a parameter similar to the rainbow connection number. Given a (not necessarily proper) edge coloring of a graph \\(G\\), a path in \\(G\\) is said to be proper if no two adjacent edges in the path receive the same color. An edge-colored graph is proper connected if every pair of vertices is joined by a proper path. (Thus, a proper edge-coloring of a connected graph is automatically proper connected, but it may be possible to use fewer colors in an edge-coloring that is merely proper connected.) The proper connection number of \\(G\\), written \\(\\operatorname{pc}(G)\\), is the smallest number of colors that can be used in a proper connected coloring of \\(G\\).  For nontrivial connected graphs \\(G\\), the authors obtain the upper bound \\(\\operatorname{pc}(G) \\leq \\max\\{3, \\Delta(G^\\ast)\\}\\), where \\(G^\\ast\\) is the bridge-block tree of \\(G\\).  The authors also obtain the following Erd\u0151s-Gallai-type result. Let \\(f(n,k)\\) be the smallest integer such that \\(|E(G)| \\geq f(n,k)\\) implies \\(\\operatorname{pc}(G) \\leq k\\) for every connected \\(n\\)-vertex graph \\(G\\). (Note that, for example, a complete graph has \\(\\operatorname{pc}(G) = 1\\), so this question makes sense.) The authors prove that \\(f(n,k) \\geq {n-k-1 \\choose 2} + k + 2\\) for any \\(k \\geq 2\\), and that equality holds if \\(k \\geq 3\\) or if \\(k=2\\) and \\(n \\geq 14\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2410035$EC03455F-ACF6-47AC-8F22-99E10DE20ECB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cfe23727306a8f36c06e3e9afd90d042a00b5c95","datavalue":{"value":{"entity-type":"item","numeric-id":497322,"id":"Q497322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$EDBD9AB0-64A3-4540-AF26-CCA15D3A0BD4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$9FADFC99-5BB5-444B-B050-C2DC144FD696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$054C1F5E-04EE-488B-B7F7-6E2EE5CB0CCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$51F407C7-0C86-42E4-9686-43C0CC500615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$CD10594E-92D4-460F-84B0-DDC11AC68BBA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92146ebc13d97055391ac3b88bbefd6b269c77f8","datavalue":{"value":"6791742","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$8EA7F2CC-C361-4F03-B428-F8FB70C08BFD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94ee28d7c07bb9d8a330fe9c9bad3aee9db8acd2","datavalue":{"value":"proper connection number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2410035$421A64F2-BE1D-4E1C-A757-E7B34562F706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19f5ef348a3b8aacdb1c53b4f10cd14de8416710","datavalue":{"value":"bridge-block tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2410035$E54A1D10-66BD-401E-B791-9CB9451185E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36526ca211eb4425ebb8748b00614bd48323a587","datavalue":{"value":"Erd\u0151s-Gallai-type problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2410035$57ECF2E9-C088-43C9-8164-CA047515AE5C","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":"Q2410035$4965B343-D80E-47F9-9CC7-A3A9607E9C2A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0f19532d3fef9ef439c0fcd7ef264ef53daf0bc","datavalue":{"value":"https://doi.org/10.1007/s10878-016-0056-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q2410035$3C4D7AF8-C678-4EE3-8D06-48B043D71F34","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68c185d583af975fb086aaa52a37e1d39159e19d","datavalue":{"value":"W2460556441","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$75573BED-6F7D-4C88-8E94-763354F8D702","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5da86a59bac848924256b2f4796bb4d7939677","datavalue":{"value":{"entity-type":"item","numeric-id":2829346,"id":"Q2829346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$09B2858B-A63D-4C64-9922-42134B13F626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6951289a528ef5e4a7a580bbc3485d72e768c239","datavalue":{"value":{"entity-type":"item","numeric-id":3178806,"id":"Q3178806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$6CCF4B09-A4D3-4297-805D-E9C57CE7436F","rank":"normal"},{"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":"Q2410035$FAD5440C-A277-4B48-9452-EB5EF9B3E0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2011ceda24fe14ec467d066a90d60c64bbae9c97","datavalue":{"value":{"entity-type":"item","numeric-id":442366,"id":"Q442366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$A947A797-7D68-481E-9DE7-70FF5DF1A686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89f14c27a2ea87c670a1006c7875cb9679a66258","datavalue":{"value":{"entity-type":"item","numeric-id":2911064,"id":"Q2911064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$57119EFC-9AB7-42F3-8CE3-F38DC231F162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00f0d21c10977bd500dd475802d6c1b1d717813","datavalue":{"value":{"entity-type":"item","numeric-id":3392716,"id":"Q3392716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$48B8B99F-2CB4-4512-BBB8-C93D148FABC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b33d6d740bf4c0b6f771140c00c0e9e56754f16e","datavalue":{"value":{"entity-type":"item","numeric-id":3057105,"id":"Q3057105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$AD2368C8-4DA2-4A35-82D7-817CD419CE64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5230dcd7e6215efd6d2d077467fefd4be470db1","datavalue":{"value":{"entity-type":"item","numeric-id":2375854,"id":"Q2375854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$20D4C1B6-A3D6-4619-BA26-A233785B133B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85c0cacd675b8fb348d1fe4bbb02e00ef54ccc6b","datavalue":{"value":{"entity-type":"item","numeric-id":723592,"id":"Q723592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$C4AB3E89-86DD-423D-84AE-CC0D7F113E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d0a670f2e78209bd1b37f08d283260683c4642a","datavalue":{"value":{"entity-type":"item","numeric-id":3089355,"id":"Q3089355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$EA367BD2-69BC-49BE-8FF5-088BF841E626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a66164a4bfbe1198dd54fba312ae9c6d974ebc0b","datavalue":{"value":{"entity-type":"item","numeric-id":408184,"id":"Q408184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$ED9ECB40-C34D-47F9-A544-27DD7BD86956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"644b972d8b27730fbb9cc813e9894d4bee82e8f4","datavalue":{"value":{"entity-type":"item","numeric-id":742605,"id":"Q742605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$E6AB9901-7D1A-4BCC-8DBE-BFE82DE8E776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"021e67b6b3e7123b914babb9ef3a10e0b84e8fd3","datavalue":{"value":{"entity-type":"item","numeric-id":2857035,"id":"Q2857035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$5871619B-69E0-43DE-A592-CF2FEBA407E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96a2d21a42d91d6b270d09a572d0543cd9136980","datavalue":{"value":{"entity-type":"item","numeric-id":367069,"id":"Q367069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$4E065FF4-C14A-4786-8367-8D6F2B0D4D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"888d09fa285d6263c5b316785736c46c141a679f","datavalue":{"value":{"entity-type":"item","numeric-id":397136,"id":"Q397136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$7AAFF8EA-D8A9-42B5-B0C9-FE0B50329DA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4fc88f00a5026c7d9ffa7e59f5bfe7207b9ec55","datavalue":{"value":{"entity-type":"item","numeric-id":1941399,"id":"Q1941399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2410035$5AC14AD3-609D-4485-ABCB-E4F175C20BEC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"246fa6bda9fd7c9d95a29794385d505a4a307c84","datavalue":{"value":"10.1007/S10878-016-0056-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2410035$D4419FB3-DA67-4A56-9C0A-E2C52A00C1DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56b612897a857348528af60c8374b9fbc5ad1f36","datavalue":{"value":{"entity-type":"item","numeric-id":2401802,"id":"Q2401802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da5fb77ba5314b7474970755161998711c96e888","datavalue":{"value":{"amount":"+0.8950134515762329","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":"Q2410035$D2553699-EF03-42AB-96B2-1486FDF0AE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f97d719e864636e8a5859ccc1a5842ebc5a3e193","datavalue":{"value":{"entity-type":"item","numeric-id":2375854,"id":"Q2375854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0039ef12df12f0d7f22f5ffa08592b40206034f","datavalue":{"value":{"amount":"+0.8892619013786316","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":"Q2410035$CF369984-3D10-4140-8412-53D9F9C39A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2156c485ad8dbfd2ec2e1eeb70edeadd357911b0","datavalue":{"value":{"entity-type":"item","numeric-id":442366,"id":"Q442366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ebfeb8dfd7b02ba92cade6b66d72f92cee9ef3f","datavalue":{"value":{"amount":"+0.8830618858337402","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":"Q2410035$4B70010E-5093-437C-BF27-DD3A60539269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abfa880a2aa4aa8514dc44e48351baec9ac692f9","datavalue":{"value":{"entity-type":"item","numeric-id":2315588,"id":"Q2315588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc1f53f2f01d09edb1da436bc9964b999dbec471","datavalue":{"value":{"amount":"+0.8721358776092529","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":"Q2410035$73319E3D-73D2-4C8F-91D0-88630A9974BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f32cf5aed45f866388ae964f7adab2b886c25a16","datavalue":{"value":{"entity-type":"item","numeric-id":510953,"id":"Q510953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"883c86449652ebc31b6e3c2606325398ab0a5905","datavalue":{"value":{"amount":"+0.869778037071228","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":"Q2410035$9263B132-F0F4-41E1-A030-63340B1CB3E1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2410035","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2410035"}}}}}