{"entities":{"Q941396":{"pageid":943244,"ns":120,"title":"Item:Q941396","lastrevid":65575785,"modified":"2026-04-12T03:33:03Z","type":"item","id":"Q941396","labels":{"en":{"language":"en","value":"Long paths with endpoints in given vertex-subsets of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5321324"}},"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":"Q941396$83C78E7A-E398-4639-A46B-A7B262BD8E60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"55608eca46e692fd858269bd8390964ead6439fd","datavalue":{"value":{"text":"Long paths with endpoints in given vertex-subsets of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q941396$467ACB5E-6AD2-47B2-A4FC-1CC94AEC9704","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed5faf50196a464e1c1cc36bdfe7a7c3dc3bd929","datavalue":{"value":"1152.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$9D957389-3655-4951-BD12-8BAA9CACA935","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84dbbd96058bd9a7accca3e624f3150ac3057b92","datavalue":{"value":{"entity-type":"item","numeric-id":186102,"id":"Q186102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$F072C7B1-D1D2-4651-86E3-9B7448295B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"347fecbfc47b37539faa04d7bda9825bc6c893ad","datavalue":{"value":{"entity-type":"item","numeric-id":198775,"id":"Q198775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$CF10AF37-765A-473B-9F35-9E014B66B69B","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":"Q941396$03A1C645-690A-4476-900E-ADF2D03B1678","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2bf0f0ee9c49018dff9c641c5da1a78a5da873e5","datavalue":{"value":{"time":"+2008-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q941396$8C193131-A578-4BE3-BC4A-6EF6445755F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d2d769446bc561fc5c11afabc9926643d6f6e98","datavalue":{"value":"It is proved that if \\(G\\) is a connected graph of order \\(n\\) and \\(t \\geq 1\\) a real number, and \\(M\\) is a set of vertices with \\(| M| \\geq n/t \\geq 2\\), then for any vertex \\(v \\in G\\), there is a vertex \\(u \\in M\\) with a path \\(P\\) from \\(v\\) to \\(u\\) such that  \\[  | P| \\geq \\min\\left\\{\\frac{4}{4+t}d_G(u) + \\frac{4-2t}{4+t}, \\frac{2}{1+t}d_G(u) - 1, d_G(u) + 1 - t\\right\\}.  \\]  It is also shown under the same conditions on \\(G\\), \\(M\\), \\(n\\) and \\(t\\) that either there is a cycle \\(C\\) containing all vertices of \\(M\\) or there exists a path \\(P\\) in \\(G\\) from vertices \\(u_o\\) to \\(u_p\\) in \\(M\\) such that  \\[  | P| \\geq \\min\\left\\{n, \\frac{f(t)}{1+t(t)}(d_G(u_0) + d_G(u_p)) - 2t - \\frac{6}{1+f(t)}\\right\\}.  \\]  where \\(f(t) = \\min \\{\\frac{4}{t}, \\frac{2}{t-1}\\}\\). These results are related to and motivated by the concept of cyclable sets of vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q941396$E780BCEE-3FB8-4FC5-9A62-415B0AE73133","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$EB0109DC-7E5F-481D-A055-A7FA169F671D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$195BD9D9-8FA1-4AD8-B82E-5EBF24187173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$36702462-0D8B-422F-B5E4-4969D38A6BBA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"559e9b8727f05a430bb0d8e0b97376639b01ce41","datavalue":{"value":"5321324","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$2DF3DE38-CEE3-47C8-A37F-D5C4BF151A7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b790e6a299118fa4770dcdac7a97b01ea769cf17","datavalue":{"value":"long paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q941396$A477B71D-65EE-422C-ACB0-B109E118C761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c49caaef4d0d5cc613f53c9bbc489e8cc1e1df9e","datavalue":{"value":"endvertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q941396$BB219AA5-7B7C-4F15-A2FC-931322BE57D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b064239038ee1a771c75dcf49f01efada6cdd6a","datavalue":{"value":"connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q941396$7F099017-FF6A-422A-9AB5-E079FEF38638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47406dbc0eead05d7fb3452796aedf02966dd136","datavalue":{"value":"cyclable","type":"string"},"datatype":"string"},"type":"statement","id":"Q941396$61EEEA73-10E5-48A0-952E-5A65BDCC72A1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69ba710ec323ba2b1e2239c5bdd6e4165b935d93","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$6AE7CEC6-80AF-44C0-BFF5-98CC6D882F41","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":"Q941396$40EA1EE2-6EF6-4F4F-B476-DFBE8415BBB7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f223bc006058a5b8d3fc76d0bf5bfe80d79022f6","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.08.056","type":"string"},"datatype":"url"},"type":"statement","id":"Q941396$7C74719A-68EF-40F4-91EF-F5610A9AF8B4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c4a363e696b54b03dd707e227be63ffc4da67791","datavalue":{"value":"W2064300756","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$D9D739D9-EBD9-460A-9870-B138F24CFB78","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d2f8516ceb4d54cd2baf6ee4feeeb544056520e","datavalue":{"value":{"entity-type":"item","numeric-id":4506067,"id":"Q4506067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$17E04ECD-1B24-4524-AA08-797B2E7E4D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e26f7bacc93ec1437f8a173f664fa73211a15e0","datavalue":{"value":{"entity-type":"item","numeric-id":684399,"id":"Q684399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$5B262D67-14AE-414A-B0C6-3D076C358E31","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":"Q941396$0F21F2C5-DFC5-4EEA-BA89-F8AA86F56AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a017bff7464c5460512b90412db6eb63211e1319","datavalue":{"value":{"entity-type":"item","numeric-id":1916132,"id":"Q1916132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$7B29D29F-AED6-463F-8566-D02ADCB9AF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$EE6570B3-CA0C-4B64-ACE6-6B541AA52FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83e552dd1bb657be7458f9b37519e51fcd8b784f","datavalue":{"value":{"entity-type":"item","numeric-id":4294587,"id":"Q4294587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$C60BCB22-8976-45E1-B7B7-8D662BD63B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14dcc9c96f6c72fbc9a4feb8a83dc5eacad8748","datavalue":{"value":{"entity-type":"item","numeric-id":3265306,"id":"Q3265306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$5D1872CD-80B3-449A-B620-DA8679FDE6D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed0b82ae82773b964a96367bdde8d8d4e478307","datavalue":{"value":{"entity-type":"item","numeric-id":4878666,"id":"Q4878666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$EF39F689-44F1-4F88-AAC8-EB3BF1F36047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36dd8678296a45be018f864d1b157732b4e14a19","datavalue":{"value":{"entity-type":"item","numeric-id":1850630,"id":"Q1850630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$50F0DD8C-0D34-4FCA-86AC-AD0346CBE07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0d9c586ef9cf53af881c9950417cc5b66679aa","datavalue":{"value":{"entity-type":"item","numeric-id":3264678,"id":"Q3264678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$88DCD3D0-1620-442B-869C-7CE564A2CE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fda4b4f3f642da69f3574160a584d145f6434b0","datavalue":{"value":{"entity-type":"item","numeric-id":775674,"id":"Q775674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$04688AC4-BDAE-4D09-BBC1-337E8CC06F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"decedcf9d745df972af60bdd468da099f0f718c6","datavalue":{"value":{"entity-type":"item","numeric-id":1901041,"id":"Q1901041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$BE966F9E-B404-4BC7-B5C0-2F562E8C0BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8e02c3bb1fe0bf1aac3aad3f270fbcc7b4339cc","datavalue":{"value":{"entity-type":"item","numeric-id":4013430,"id":"Q4013430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$26D9F883-353F-4720-A846-61F7ADB6DCC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba1adc80beaa9add77a0599d62fd8a9b93f6395c","datavalue":{"value":{"entity-type":"item","numeric-id":4134010,"id":"Q4134010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$CF87B57B-64E8-47D6-9921-801091DC323B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc0cc475c4333543bfa43e3b2380913a6c9cd5e5","datavalue":{"value":{"entity-type":"item","numeric-id":4865531,"id":"Q4865531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q941396$1FCBB4EE-42BE-430F-9F0F-D844BB17E5DF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f2b48abe110e23eda5e0f8211f13df5a535eff6","datavalue":{"value":"10.1016/J.DISC.2007.08.056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q941396$524F6899-10A3-4752-81A6-05E5A3D02738","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0066327753252f5762ef297bc62c25f495f43c0c","datavalue":{"value":{"entity-type":"item","numeric-id":2715999,"id":"Q2715999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef9da08c2a219b57728adcd4bf9117088811b6f8","datavalue":{"value":{"amount":"+0.8054978847503662","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":"Q941396$2BEA2F0F-B252-4FBC-B701-28D2F182B936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fe58b1d4399b515f2606a003625e89becc84480","datavalue":{"value":{"entity-type":"item","numeric-id":3333075,"id":"Q3333075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abfad5e30219448f88572719909d743910961508","datavalue":{"value":{"amount":"+0.794242262840271","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":"Q941396$D5288D3A-F6D9-41A8-8280-7442381BCB98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9e86e179451e65532516893b4580dc429c8469f","datavalue":{"value":{"entity-type":"item","numeric-id":5897109,"id":"Q5897109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf21ac594257696290f8600757d4650758e9c161","datavalue":{"value":{"amount":"+0.7799282073974609","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":"Q941396$1C524EFB-DADA-4F60-A8E7-167070D04D91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02e21e0c4ff3025dd2d58760123f1d7305c97fcf","datavalue":{"value":{"entity-type":"item","numeric-id":5397248,"id":"Q5397248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beeb0c5d85b3d8e1d1302d67c2a5ca10b6560ab1","datavalue":{"value":{"amount":"+0.7786347270011902","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":"Q941396$6C622F74-5424-4131-AD0B-212C1BEF6F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8126beba18139f61bcedc1361f072eb46e93f141","datavalue":{"value":{"entity-type":"item","numeric-id":3764181,"id":"Q3764181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b6125693b5a392a5c7732d2f95457607f102d7f","datavalue":{"value":{"amount":"+0.7772815823554993","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":"Q941396$31ADFC7D-BCC0-45D6-99B8-D2F72C84C0BD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Long paths with endpoints in given vertex-subsets of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Long_paths_with_endpoints_in_given_vertex-subsets_of_graphs"}}}}}