{"entities":{"Q1386432":{"pageid":1397172,"ns":120,"title":"Item:Q1386432","lastrevid":46971774,"modified":"2025-12-25T23:27:02Z","type":"item","id":"Q1386432","labels":{"en":{"language":"en","value":"Covering the edges of a graph by a prescribed tree with minimum overlap"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1154571"}},"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":"Q1386432$80B20C5E-A96F-48C3-A612-AED1626EF3A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d7e3f508c43bcf59a8aac45552e1efbf5c31bc1e","datavalue":{"value":{"text":"Covering the edges of a graph by a prescribed tree with minimum overlap","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1386432$7AD64BBA-ADD7-489B-AA19-F93F96D11B9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c92f16b91639f8265ff8f6b664feb4ff43cbd86d","datavalue":{"value":"0906.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$3362A8EE-8CA3-44CC-85DB-B259B0F94609","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386432$E8CA4DF0-0F8A-474F-94B2-949112329620","rank":"normal"},{"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":"Q1386432$552B3B40-8EC7-435A-9145-0415A726DAC0","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":"Q1386432$8BF2D3B9-B5E1-46CA-87CD-BC6FCAD93D3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386432$9C93A36C-C3B1-42B3-B8EB-9B3E46EA5F35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1001c55d7d9b1f13a0b1df5dbb73264773e01cb","datavalue":{"value":{"time":"+1999-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1386432$04FE828E-E7B3-41D3-B10F-48622586B3B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcce055d8261263da8defdf9242751e2361e43f3","datavalue":{"value":"Let \\(H\\) be a graph, and let \\(k\\) be a positive integer. If there is a covering of a graph \\(G\\) by copies of \\(H\\) such that no edge of \\(G\\) is covered more than \\(k\\) times, then \\(G\\) is said to be \\(H\\)-coverable with overlap \\(k\\).   The minimum \\(k\\) for which \\(G\\) is \\(H\\)-coverable with overlap \\(k\\) is denoted by overlap\\((H,G)\\). We define the redundancy of a covering which uses \\(t\\) copies of \\(H\\) as \\((t| E_H| -| E_G|)/ | E_G| \\). The authors show that if \\(H\\) is a tree of order \\(h\\) and \\(G\\) is a graph with minimum degree \\(\\delta(G) \\geq (2h)^{10}+ C\\), where \\(C\\) is an absolute constant, then overlap\\((H,G)\\) is at most 2. They further show that such a covering with overlap 2 and redundancy at most \\(1.5/(\\delta(G))^{0.1}\\) can be found. The authors also prove that for every tree \\(H\\) of order at least 4 and for every function \\(f\\), the problem of deciding if a graph \\(G\\) with minimum degree at least \\(f(h)\\) has overlap\\((H,G)=1\\) is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386432$C7A1F23B-35EE-40A0-95C7-846B08D5635F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$542F48C9-A60D-4D08-B200-C528360FA7FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$C289A929-26BE-4AF9-9026-E4F5377286B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$E2662746-CD6F-406C-AEA4-8B4CFEFAF951","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a5e65fc12f86191996165e3c27b186d65137f3c","datavalue":{"value":"1154571","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$8AE8F013-ED5F-4601-84B9-2F4995553103","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d142027bf3153eebb876131ac5297907f4e838","datavalue":{"value":"covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386432$A4621930-BFEB-41AB-9266-5419D06A1694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63f9e7be6a54a7cfa206daf3d124db12fdb5ad3d","datavalue":{"value":"overlap","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386432$D9625BB2-BA5B-415C-B07C-8924EA85C45A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386432$F05342EB-1747-4B87-A49D-C9260A3D92E9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"71941e8026984bbc6297878157400ea7dd33d20f","datavalue":{"value":{"entity-type":"item","numeric-id":1876689,"id":"Q1876689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386432$722BE1AA-0450-4EBA-8A37-9789F43078BD","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":"Q1386432$A4C43CC3-F28D-4A3B-9A18-A872AD4D6FB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f2fa3629ccd575286ab1d67cf6c60bd5686a0ff","datavalue":{"value":"https://doi.org/10.1006/jctb.1997.1768","type":"string"},"datatype":"url"},"type":"statement","id":"Q1386432$C43151C3-E1EE-4C58-9FDA-8EEAE4869FFB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfc94c1984337d5fb44eb75f5f3bed90b90064be","datavalue":{"value":"W2095046926","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$147702F0-286A-4C82-B6A9-9B4ACAC8A66B","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":"Q1386432$E2A822B2-3AC5-4121-9B5C-C798E8F6DB97","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":"Q1386432$E7EE8B4B-E296-450D-B67E-BE3BD2B54C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd47b3d7d8840e5bd7dd266c61cfb25ce0ae8e","datavalue":{"value":{"entity-type":"item","numeric-id":4083463,"id":"Q4083463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386432$368DFB10-7E0B-469B-B927-4672B6F79F4C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72cd38f08b5c7c83401801e7f49cf5bb6c0e92e9","datavalue":{"value":"10.1006/JCTB.1997.1768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386432$C41BC4B8-3707-4B5D-ADF2-5D6300D60C26","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8767af0f4a85332e1199a9ee324b9514b423f04","datavalue":{"value":{"entity-type":"item","numeric-id":4552171,"id":"Q4552171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db08be870885f357b8a656cae0fd8bdd3f72adc1","datavalue":{"value":{"amount":"+0.8271006941795349","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":"Q1386432$B1563DD4-4A12-4BF0-ACEC-09A2D6DDE428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6d205215242da2b9c6a9154d925d25954d32d42","datavalue":{"value":{"entity-type":"item","numeric-id":941380,"id":"Q941380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d2133ac22e695df7b9d8913483a556b8b1e5afc","datavalue":{"value":{"amount":"+0.7992042899131775","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":"Q1386432$AA98BE1E-7D26-4B58-AF71-0D31D40A48D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad7ccc420390b1e8921c52ba586806ffecca5425","datavalue":{"value":{"entity-type":"item","numeric-id":5900919,"id":"Q5900919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90a145289580df210b755f904b973cabe010a737","datavalue":{"value":{"amount":"+0.7696713805198669","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":"Q1386432$77993C23-4B3E-405E-8324-EFB04FAD032A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03e879479d76028deb250e010bb630ddd6631284","datavalue":{"value":{"entity-type":"item","numeric-id":1850010,"id":"Q1850010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f13fa64028e85bfbedf97cd5ea594e9ec6baf0f","datavalue":{"value":{"amount":"+0.7593041658401489","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":"Q1386432$5D5AB310-174D-40B8-B931-D14A63D3EB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0dc2cf51498be5a652e10309ad7ec4323d594fd","datavalue":{"value":{"entity-type":"item","numeric-id":1775897,"id":"Q1775897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f896e71b8ce7513faf168ef61bb6e455bcc5fed","datavalue":{"value":{"amount":"+0.7554804682731628","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":"Q1386432$612C9D87-40A1-421C-990F-8099F09A1C2E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1386432","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1386432"}}}}}