{"entities":{"Q1579571":{"pageid":1590311,"ns":120,"title":"Item:Q1579571","lastrevid":72241476,"modified":"2026-04-14T03:35:01Z","type":"item","id":"Q1579571","labels":{"en":{"language":"en","value":"Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1506835"}},"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":"Q1579571$F576D77B-E136-4CB6-B348-5B0ECD3C3B97","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2dcc5f61f976449250410dd6b4133ae9377cb7d6","datavalue":{"value":{"text":"Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1579571$E367856F-836B-4B16-A24A-2E0DEE917DBA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a65c2e889420103ff2671635657c2c7667378cf9","datavalue":{"value":"0962.05032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579571$FD585BEA-28E8-405A-9F36-4C2B69BE0FC2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d10c778e244cd5c35962405573929d97728626f","datavalue":{"value":"10.1016/S0012-365X(00)00055-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579571$A87D3878-CA53-49E3-B566-29839C97D73F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d62d1b98a8e47330bd8d09b4c364147d7b3d1f6","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579571$A4D4528D-9C7D-43CD-A921-F77B5CD2F85A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"217017280ceb05457760231c73be6ea7ebbf811d","datavalue":{"value":{"entity-type":"item","numeric-id":186127,"id":"Q186127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579571$DE8E1B19-CB58-4C06-81FF-A05C327F69E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579571$AEF48266-CAC1-44BE-8143-FC8EA074301F","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":"Q1579571$D28070D1-0803-48B8-8CF9-421FA0E6755B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"513086f907e3433d6abf8ca52bcce129020bab74","datavalue":{"value":{"time":"+2001-06-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":"Q1579571$06CC8CEA-3DB7-4322-9DFE-422BD5244421","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba37fc13f067a60d162a5d0008bbfbfd5c7dce04","datavalue":{"value":"A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs is called a semicomplete digraph. An oriented graph is a digraph with no directed cycle of length two. In [Ars Comb. 58, 271-278 (2001)], the reviewer raised the following question: Let \\(D\\) be a strong semicomplete multipartite digraph with a longest directed path of length \\(p\\). Does there exist a strong spanning oriented subgraph with a longest directed path of length \\(p\\)? The authors present the following complete answer to this question. Every strong semicomplete multipartite digraph \\(D\\) with a longest directed path of length \\(p\\), which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph with a longest directed path of length at least \\(p-2\\). Examples show that the bound \\(p-2\\) is best possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579571$9816EB30-A8C7-4DB1-8CE9-57AADDED21ED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a65d3702174a536f0cf916db67d42643a023895","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579571$223794DB-7776-4C8B-ABA3-0DEC6D4ACB7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579571$9C12E2EC-6EFC-459D-B9D5-B7783DDABC77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579571$D4326D6D-E2C0-4350-8D08-24B5A5ECD84C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2532b2fce38631b69e5a03994c857a1ddda4c778","datavalue":{"value":"1506835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579571$B017C04B-B573-4273-B990-2D740294A0E2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"696c86e7c8ae25d013e1baf92316ca662151659c","datavalue":{"value":"semicomplete multipartite digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579571$A0956D7A-65B3-465E-92DB-E42A027D7201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bcb88e4835cfef6b70b1d60481bd40424864103","datavalue":{"value":"spanning subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579571$C97CCF6B-6FC3-4790-B481-5B6A428EF8D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579571$9C5AF27A-01FE-41CD-AED4-2E4C031459F4","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":"Q1579571$35AC4CC0-3189-4CD7-BA04-8F4FD6FEBBC5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e609b80abcf229e06a71208b54c5171da97463fa","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00055-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1579571$CA945758-0196-4603-AD01-23989D35E869","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"132ecae2d0001d8bd02a67e192f4d00c8397908c","datavalue":{"value":"W1964296470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579571$5744D180-040A-4CAF-83DF-0682CD2BE8C5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ee7fc8a3e51971ca5564b4d91e3016e9e259586","datavalue":{"value":{"entity-type":"item","numeric-id":1297460,"id":"Q1297460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe07372e472fe4cad99b0bdce611d309f7c0fbdd","datavalue":{"value":{"amount":"+0.94229716","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$93A51E2B-A1C3-4423-A6E9-89302538FD1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5414ce181fea5086e88467c4bde41d532910777d","datavalue":{"value":{"entity-type":"item","numeric-id":1850069,"id":"Q1850069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af840fafb3459a81cfa97dbff3413d5b04fac7bb","datavalue":{"value":{"amount":"+0.9302039","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$12EA5D18-1414-47EA-B490-EBD4413E600B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1892fd19db168817a4d73bc15a80c6500292895c","datavalue":{"value":{"entity-type":"item","numeric-id":3767374,"id":"Q3767374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c392a47d1fa572be83ba2b0bc40c0ad4426fdf4","datavalue":{"value":{"amount":"+0.8927865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$CFA2AC6B-FB1B-408B-9E93-3F819E0E48C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07d3491969960a28cf1f54d556930af4507abe84","datavalue":{"value":{"entity-type":"item","numeric-id":3800073,"id":"Q3800073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c392a47d1fa572be83ba2b0bc40c0ad4426fdf4","datavalue":{"value":{"amount":"+0.8927865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$B0A9EBF8-2A73-483E-81A4-01A5FC7691ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4c730fe7b6ed3a9bc6b683205642d4d0c3e5e9e","datavalue":{"value":{"entity-type":"item","numeric-id":3722538,"id":"Q3722538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58520c0704d472aaa8d96c0b51482ade0cbeff4e","datavalue":{"value":{"amount":"+0.89003116","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$E1152970-7FBD-4765-B27B-528D415E62D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66a5a4090c355771e2f0d31afbb2887048e52b63","datavalue":{"value":{"entity-type":"item","numeric-id":4695387,"id":"Q4695387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5729479b37a668a09c41698cb587232ec96083f5","datavalue":{"value":{"amount":"+0.8848748","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$028F364B-0DA9-45EE-9624-397ABE780228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9482463dbdd14833410719354592ccc59bfe0dad","datavalue":{"value":{"entity-type":"item","numeric-id":5937609,"id":"Q5937609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3bff4ee8e76051f431047f6b004607f3c04ffaf","datavalue":{"value":{"amount":"+0.8819635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$A8AD6516-B65A-4801-9052-A2C827CC5E08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afaa73de04be20f9bbf6623e3807001c178d5bde","datavalue":{"value":{"entity-type":"item","numeric-id":2765953,"id":"Q2765953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b005466336b45afd01df42e2ae4ba2e91bd7ce80","datavalue":{"value":{"amount":"+0.8782352","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$F093484C-75F5-4392-9738-32EBEC9999D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85c62d6eddb4a988d96e57b8f2c26528937701e9","datavalue":{"value":{"entity-type":"item","numeric-id":3768926,"id":"Q3768926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bcfa690647d951781e13d4e16984e6311cb042e","datavalue":{"value":{"amount":"+0.8780909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$8880206D-6D3C-4762-A2A2-E763EF3A6BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f10a73ff06563287053ea15457f03a49d36342e","datavalue":{"value":{"entity-type":"item","numeric-id":4568152,"id":"Q4568152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83a20c4c3b01c69ec6b466e0e9b70d412dc56d03","datavalue":{"value":{"amount":"+0.8730139","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579571$9858E4D6-67FC-4CD1-8136-508E4F08591E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Longest_paths_in_strong_spanning_oriented_subgraphs_of_strong_semicomplete_multipartite_digraphs"}}}}}