{"entities":{"Q1297441":{"pageid":1308191,"ns":120,"title":"Item:Q1297441","lastrevid":70091544,"modified":"2026-04-13T12:23:07Z","type":"item","id":"Q1297441","labels":{"en":{"language":"en","value":"Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1321801"}},"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":"Q1297441$7D304EBC-AA56-4546-9978-73C57E1634C5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72a5e92d9ffebbce0697ed7146ae95aca2bda7cd","datavalue":{"value":{"text":"Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1297441$36F23CF7-2E1C-4FC6-88C4-F3F979467399","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1461e619ad259e0eafe93e6dde1306885f1d58b0","datavalue":{"value":"0928.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297441$1929EB7C-3DAA-4B90-AA50-D99D7D4AD4A7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d380ae7ef7f463860a6bbf644b04ffbfdcca256","datavalue":{"value":"10.1016/S0012-365X(98)00209-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297441$6D78EDAA-126C-4B5F-957E-523AE80358E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31743fa6e40464ac5b61eb56bb62ad64c952c415","datavalue":{"value":{"entity-type":"item","numeric-id":186288,"id":"Q186288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$573E49D9-5C2B-4417-A983-38F18FD2A5CC","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":"Q1297441$66B21C90-5ACB-41DE-89BF-907F39A4B4FB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d604edbdec21d88f35e4a6e416134363ddfe3b58","datavalue":{"value":{"time":"+2000-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1297441$6FBCD0B5-11FE-4804-9D31-0747F23FFB59","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"04f3a72dc6565d62690667dd9614083f549fe8c3","datavalue":{"value":"A acyclic digraph \\(G\\) is said to have the Gallai-Milgram-Linial property for clique covers if for every induced subgraph \\(H\\) and every clique cover of vertices of \\(H\\) with sink-set \\(S\\), there is a vertex cover of \\(H\\) by \\(c\\) cliques whose sinks come from \\(S\\), where \\(c\\) is the largest number of pairwise nonadjacent vertices in \\(G\\). The author gives the necessary and sufficient conditions that acyclic digraphs have the Gallai-Milgram-Linial property. Five forbidden subgraphs are presented to establish the results.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297441$ACE8BC92-A6E3-42AE-8ABD-EB7C5DDA3EA4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297441$14DEE4C2-F600-4708-9A4E-C478CC69A819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297441$E217ECC9-BC11-4E10-A8BB-DBDA8C20F8A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd6237408e1e01262bae97c49e9f08fac341f6a0","datavalue":{"value":"1321801","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297441$46FB674C-C284-4A9E-A63D-ACD3B4ED0815","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298a551ef47c5b20057a4bfdb8bbc9e28d84ca03","datavalue":{"value":"acyclic digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297441$8A769E51-1D1B-40F9-ABAC-19BEB91FBC5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4425f73fcf561bdce49150c5b56c855fd5dd899","datavalue":{"value":"clique covers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297441$9F6FF69F-4BA9-40E0-80C1-F4E02C792BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297441$31DBD4EB-0AC3-4033-8150-EBA8247FE77A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a23500c0b440757ffeb96713615f2e6e6db59f42","datavalue":{"value":"Gallai-Milgram-Linial property","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297441$D052661A-25EC-43C2-A8AB-7626D4BAD7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453a43e7e93d9a367957c940a4dbc5498dddc3ee","datavalue":{"value":"forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297441$DAB067A3-CB1E-4ACC-93C3-ABAB47A37498","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"47bea2b4d39621f5b323782296b354a90f4f5f5e","datavalue":{"value":{"entity-type":"item","numeric-id":516046,"id":"Q516046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$3F88D985-AC56-4C5C-AD07-4D185D3874D9","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":"Q1297441$56C89BFC-9DA4-4EC8-9FC9-1BCFF9839325","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9ca545fa961a7149251e4212e44ff25b84ca82f","datavalue":{"value":{"entity-type":"item","numeric-id":687099,"id":"Q687099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$A96224AF-EEAE-4B43-B35D-A5A19A6D5460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22ad8c0cf8959fb3be24778fa28798afcfd7af02","datavalue":{"value":{"entity-type":"item","numeric-id":3286847,"id":"Q3286847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$602949C1-6BF8-469E-B76B-46A1C6B3C4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8265efab4607f278a43a6817a867c599f4faccb","datavalue":{"value":{"entity-type":"item","numeric-id":3033587,"id":"Q3033587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$4DD131E2-BBC6-4A1C-ABD4-5B55DF879392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bd269295ba877c106cd58908caf0f087a4411b","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$CE7B33EC-B05E-49B1-8E81-8DD3F1EF94E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$9767FCDD-B818-41E1-B4F1-A996D8813113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bad490746f3d137c8fc2d3faa8fba778e2c1116","datavalue":{"value":{"entity-type":"item","numeric-id":3283482,"id":"Q3283482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$FF1A05F6-5585-4D6A-9A34-3F8E069E0F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3540803e6c2941a79b658c1ad46488049de9a54a","datavalue":{"value":{"entity-type":"item","numeric-id":5966939,"id":"Q5966939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$F8A38077-CE51-400D-829A-81DC79E3248D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$76BCD345-73CE-4BE0-BFC0-76E114AEEE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28fe120dcb413d61d6856a7e0e513e10b113e883","datavalue":{"value":{"entity-type":"item","numeric-id":1250116,"id":"Q1250116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$89CCE837-333F-4D23-A9E1-ACFCB10FAA5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b176b62f645a81bede2a6fe7f397a8c79f1d7a6","datavalue":{"value":{"entity-type":"item","numeric-id":1155625,"id":"Q1155625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$20A26935-9EA1-4124-951F-4C9709D4C79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbe097f62791bcc42fe71dd30e6b393e0a8c6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2553445,"id":"Q2553445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$F90D2096-44FD-4212-9E66-470749612DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18195acc4b73d0932b3036eea3f7322faeaa53a9","datavalue":{"value":{"entity-type":"item","numeric-id":1073032,"id":"Q1073032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297441$2CBE4C50-7B5C-4235-8126-A8A7ADF2E386","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6a014c7f97ee28349b4ee44eac2dad8ac486af9a","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(98)00209-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1297441$F98B3901-0707-4A51-80E2-A1A254C6C405","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bd0bb8b6979c3757b717fb3bed17238076072a77","datavalue":{"value":"W2062222767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297441$2E0A2891-3ACB-4947-AC17-8A99F1E81BF4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32cdeeddd4e4986d59124777bcc5a34aed486640","datavalue":{"value":{"entity-type":"item","numeric-id":4519730,"id":"Q4519730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60f5a054994d184832f224ffff04ee6c00ffb166","datavalue":{"value":{"amount":"+0.88761914","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$F2F23B16-E24F-4FC1-8339-B463B82DE852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"219439658270652e17210b7a50f1706cc7f1268e","datavalue":{"value":{"entity-type":"item","numeric-id":3783328,"id":"Q3783328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b2710c7476ba9186da32223ea193598c6c6258a","datavalue":{"value":{"amount":"+0.8737955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$5E7CAAC4-757D-4005-83C6-E0A2333A7FD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f8e0d5311cd9435f48bda009ae85eeded323aa7","datavalue":{"value":{"entity-type":"item","numeric-id":1584403,"id":"Q1584403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc6c3442965b52fc3446c5b038d62f8070dbb03c","datavalue":{"value":{"amount":"+0.87140614","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$021442DD-F0AF-4F59-B96C-4833581D5A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f87ea1bfd06beadd1c1504f4a30095ed80150a2d","datavalue":{"value":{"entity-type":"item","numeric-id":5294935,"id":"Q5294935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7a4165122d9d6891147d4e44798d41a389b6150","datavalue":{"value":{"amount":"+0.8677509","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$DB6B70E2-231D-469F-8DC9-92157DBE4C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baa7c6196a0926b547c0d7bf0d55af6158b7179d","datavalue":{"value":{"entity-type":"item","numeric-id":2483388,"id":"Q2483388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a8deb82585095e01cc62a75b86af1e008683119","datavalue":{"value":{"amount":"+0.86632586","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$EFCC8F0A-994A-4930-AF2C-E4B60014D33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a13bf6aa79fa8c2267c32ecb0ba830256e979f26","datavalue":{"value":{"entity-type":"item","numeric-id":1343162,"id":"Q1343162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee0c5f61f0234a0d2c7cd28066cbf39ee3fcaa65","datavalue":{"value":{"amount":"+0.8650734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$79ABACEC-3C6F-4C4C-AA2C-032C41F0CAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6426f71be0ea4f6887169a40fb92e1db910a75f","datavalue":{"value":{"entity-type":"item","numeric-id":3784100,"id":"Q3784100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4ee40836bfcd9124875a7549e18dddae392a644","datavalue":{"value":{"amount":"+0.8604633","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$97AEA08C-97FC-4B47-93CF-14104D94CF35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"815338128b6d220a000ebd434fa0ab8d644467fe","datavalue":{"value":{"entity-type":"item","numeric-id":4030553,"id":"Q4030553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba5f92edf34256a8e17b8cef3d86ea77816be716","datavalue":{"value":{"amount":"+0.85907954","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$39B21DB2-3B99-4B6F-B1CF-FC2E6FDAA0D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a62550d5656209cfaf19a85ceb1aca6553056a60","datavalue":{"value":{"entity-type":"item","numeric-id":5404906,"id":"Q5404906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0d9d5791d989433e04511e7dc70bc45d2af8bc1","datavalue":{"value":{"amount":"+0.8581116","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$987FB8DC-B98C-4483-B725-7578AD466698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e71a9931c4b4df34a69ed0bf9b35e40930748e4","datavalue":{"value":{"entity-type":"item","numeric-id":4014438,"id":"Q4014438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a6bfae3acefda32adaf7d9a4dfc67bd934d5876","datavalue":{"value":{"amount":"+0.856892","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1297441$5E803CF6-BD65-4574-BA39-40B3ECBE441B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Acyclic_digraphs_with_Gallai-Milgram-Linial_property_for_clique-covers"}}}}}