{"entities":{"Q6969944":{"pageid":21322728,"ns":120,"title":"Item:Q6969944","lastrevid":84048962,"modified":"2026-05-08T19:55:04Z","type":"item","id":"Q6969944","labels":{"en":{"language":"en","value":"Some digraph classes that meet the directed path partition conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8054312"}},"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":"Q6969944$B9BBB593-BC80-4795-B581-CFE982D0B5C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"109bead20afd52a6f799bd3e043452f2bfc60bd0","datavalue":{"value":{"text":"Some digraph classes that meet the directed path partition conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6969944$8E3E3B14-1666-4522-9CD1-988B90D5B7F4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9aad002625f021a3547cf8b9483dd7d2c5790251","datavalue":{"value":"1569.05117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$7C0F33EF-FC45-4E15-A1DE-76DE6ECD0F58","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c5ace9736bf88fa676b5d7372d50a6d6583b5c02","datavalue":{"value":"10.1016/J.DAM.2025.04.048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$E4B30135-8EE5-4A57-9300-D2EDAC21B3A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bd3d0d5170af5da0ab3d1934e3ad2930f0725a3","datavalue":{"value":{"entity-type":"item","numeric-id":6969943,"id":"Q6969943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$15B95FB3-EB0A-4EFD-9A30-F23121C5D0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4529b33ccbb30087bbff2bcda94749ff45dbef65","datavalue":{"value":{"entity-type":"item","numeric-id":2185447,"id":"Q2185447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$50D4C18D-BD44-4BD7-97DA-940C9863CBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78de1431a255ccb7ac36c72594dd920de6ebb057","datavalue":{"value":{"entity-type":"item","numeric-id":2095565,"id":"Q2095565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$19D3AAB3-17C4-4DCB-97A2-9D2635301A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9dd2981da28734788aed862c6d726cfd050998ac","datavalue":{"value":{"entity-type":"item","numeric-id":1989527,"id":"Q1989527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$0F9BC480-B054-45A9-975C-EA915486EEE8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$05568828-6376-4338-94B7-C76F5F39C0DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a2026fb75f5daddaed5a35be8cef68702a6e3d6","datavalue":{"value":{"time":"+2025-06-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6969944$473437FA-A398-4297-9401-999379E77773","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a40d415aa4d2c813dcbe7cb0329c1d976894b59","datavalue":{"value":"Let \\(D\\) be a digraph, and \\(\\lambda(D)\\) be the length of a longest directed path in \\(D\\). The directed path partition conjecture (DPPC) says that for every \\(q \\in \\{ 1, 2, \\dotsc, \\lambda(D) - 1 \\}\\) there is a partition \\((A,B)\\) of \\(V(D)\\) such that \\(\\lambda(D[A]) \\leq q\\) and \\(\\lambda[D(B)] \\leq \\lambda(D) - q\\). This paper proves the DPPC for certain graph classes.\\N\\NA digraph \\(D\\) is said to be \\(k\\)-quasi-transitive if, whenever there is a directed path of length \\(k\\) from \\(u\\) to \\(v\\), then we have that \\(u\\) and \\(v\\) are adjacent in \\(D\\). Given a digraph \\(H\\) with vertex set \\(\\{u_{1},\\dotsc,u_{t}\\}\\), and digraphs \\(D_{1},\\dotsc,D_{t}\\), the composition over \\(H\\) with \\(D_{1},\\dotsc,D_{t}\\) is the digraph \\(H[D_{1},\\dotsc,D_{t}]\\) defined as the disjoint union of \\(D_{1},\\dotsc,D_{t}\\) along with the arcs \\((v,w)\\) where \\(v \\in V(D_{i})\\) and \\(w \\in V(D_{j})\\) such that \\((u_{i},u_{j})\\) is an arc of \\(H\\).\\N\\NIn the first half of the paper, the authors show that non-strong \\(3\\)-quasi-transitive digraphs and strong \\(4\\)-transitive digraphs satisfy the DPPC. The authors use the structural characterizations of such graphs by \\textit{H. Galeana-S\u00e1nchez} et al. [Discrete Math. 310, No. 19, 2495--2498 (2010; Zbl 1213.05112)], \\textit{S. Wang} and \\textit{R. Wang} [ibid. 311, No. 4, 282--288 (2011; Zbl 1222.05090)] and \\textit{C. Hern\u00e1ndez-Cruz} [Discuss. Math., Graph Theory 33, No. 2, 247--260 (2013; Zbl 1293.05136)] to prove their results. From the result of \\textit{A. Arroyo} and \\textit{H. Galeana-S\u00e1nchez} [Discrete Math. 313, No. 3, 293--300 (2013; Zbl 1256.05085)] that strong \\(3\\)-quasi-transitive digraphs satisfy the DPPC, the conjecture is now known to be satisfied by all \\(3\\)-quasi-transitive digraphs.\\N\\NIn the second half of the paper, the authors prove two results on compositions over unicyclic digraphs. First, let \\(T\\) be a unicyclic digraph on the vertex set \\(\\{v_{1},\\dotsc,v_{n}\\}\\) with \\(C = v_{1}v_{2}\\dotsm v_{t}v_{1}\\) being the unique cycle in \\(T\\), and let \\(D_{1},\\dotsc,D_{n}\\) be digraphs such that \\(D_{1},\\dotsc,D_{t}\\) have the same order, and \\(D_{t+1},\\dotsc,D_{n}\\) each satisfy the DPPC. Then, \\(T[D_{1},\\dotsc,D_{n}]\\) satisfies the DPPC. Second, if \\(C = v_{1}v_{2} \\dotsm v_{t} v_{1}\\) is a cycle and \\(D_{1},\\dotsc,D_{t}\\) are any digraphs, then \\(C[D_{1},\\dotsc,D_{t}]\\) satisfies the DPPC. These results generalize an earlier result of Arroyo-Galeana-S\u00e1nchez [loc. cit.] on sufficient conditions for a composition to satisfy the DPPC.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$6E8C845B-F4EA-4D1A-B27F-EAFE45EA75F8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0b482c2cc67ce97ca4ac3c158555ef94e0919967","datavalue":{"value":{"entity-type":"item","numeric-id":2104982,"id":"Q2104982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$7265C816-602F-42D1-B292-2D4D26F35BF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$C8F1E0CC-205B-4999-B315-5239CA8B075F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$7CA546D6-1A66-4AB3-9C71-E1217EE11143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$5B2A27E1-0A6E-4D00-BD98-008E2C1DDEAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$A3C30434-9530-4C6A-B699-A9131115A309","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"30a629d57d2171991554dca41c236374602316fa","datavalue":{"value":"8054312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6969944$5AE92DC3-E27B-495C-B071-AACDD8C10FAA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ebc22d8187ea672fec2c0fc855212abe29ca422","datavalue":{"value":"longest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$63267CAF-7138-47DB-B11B-4F8E2E42AE30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7feebe8ee5c813494a7442ff79acd0bf0784a65f","datavalue":{"value":"3-quasi-transitive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$A7E64643-84FE-40A1-8E3B-BED032FB266D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10f22e50cf5f18971195d1ac0b11e95c21213cc4","datavalue":{"value":"unicyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$C0AFFE19-BA19-4376-8BF2-715592B73189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f9946779af43068db84959d7ebfa6d74959256af","datavalue":{"value":"composition","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$3A8EDF1D-2A2F-4CE5-BC43-46E3971AFF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$F080E9CC-0443-464E-B22E-A03FED9C0149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a6abd881a56495780aafa106e4ce9af3a9f9fb7","datavalue":{"value":"path partition conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q6969944$D1584E03-A05F-41CB-B8A8-11568EF29325","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":"Q6969944$EDB6AF89-F462-4C79-A497-B8AB6D1CBF48","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f7766e40263d3fe3096dc4aab28df13718b76a3","datavalue":{"value":{"entity-type":"item","numeric-id":2166278,"id":"Q2166278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$FACC77BE-4806-4A68-AA56-76699B9FAD65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc7e9552117bb3698fbf746f360c979f71145282","datavalue":{"value":{"entity-type":"item","numeric-id":1928451,"id":"Q1928451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$1C2C814E-F6E9-430F-8D0A-65B298CA967C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebade38ddfaf89228b6b45ac4d3ced1aae55aa16","datavalue":{"value":{"entity-type":"item","numeric-id":2501556,"id":"Q2501556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$4C8EFB28-6AD0-4BCB-9ADE-2AF6C81BFA2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ea75064f615a743f50755baa2ab480c29d3a106","datavalue":{"value":{"entity-type":"item","numeric-id":2866454,"id":"Q2866454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$42D16954-6A6F-43E2-B339-1351275661AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eb3382b3dc81d5167bcb8b8f23564551d92c342","datavalue":{"value":{"entity-type":"item","numeric-id":5492647,"id":"Q5492647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$162DD2DF-4D6E-4073-8A18-4E0FE14B4923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a6a71cf66a39e60d614e236f3061e3ecb18074c","datavalue":{"value":{"entity-type":"item","numeric-id":708416,"id":"Q708416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$4945B884-1B16-4997-9AB2-91DF7E15F6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d7f5b38f643afc5e6d05c85eea9f9ee0a063e8","datavalue":{"value":{"entity-type":"item","numeric-id":2860856,"id":"Q2860856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$ADBC5527-D8CE-428E-8DA0-B3162515ACC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1353d2952977fbf18a6627382605f90076a5b95b","datavalue":{"value":{"entity-type":"item","numeric-id":3309863,"id":"Q3309863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$BAF791E1-9DDA-4FD5-807E-6A549BE1A85F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b8248564e17297607d0ce60538defa7ba666678","datavalue":{"value":{"entity-type":"item","numeric-id":626767,"id":"Q626767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6969944$6F1CC2D4-1DE1-4EDA-BF17-626663728073","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some digraph classes that meet the directed path partition conjecture","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_digraph_classes_that_meet_the_directed_path_partition_conjecture"}}}}}