{"entities":{"Q921017":{"pageid":922865,"ns":120,"title":"Item:Q921017","lastrevid":65397372,"modified":"2026-04-12T02:18:58Z","type":"item","id":"Q921017","labels":{"en":{"language":"en","value":"Induced matchings in bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4164904"}},"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":"Q921017$6C63E60D-4EA0-4680-9147-BDB8A950762B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9951e39a92490b49ff42c53fca27d17b34576235","datavalue":{"value":{"text":"Induced matchings in bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q921017$36D9A6D2-BA96-4711-9A7A-59241365DB78","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d36e164b31c880fe64d2895f08b0ab99bc4a3af4","datavalue":{"value":"0709.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921017$39599898-945B-4121-91D1-2CB362C21757","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"da4e56ac180e0fed4f6cd19adbcee82d98253b14","datavalue":{"value":"10.1016/0012-365X(89)90163-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921017$0BD7D527-89EA-4D74-ADC5-F9D9510144FA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921017$2A28C210-C83F-4EEE-BCBE-4E4F4D81DCFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a90237f4fbe17f8aa89942b7417b8396bf1098f7","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921017$85635D22-8782-4A8C-957D-53A4CD6FAFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3155ff163c931be8945149a68c11d68da0b397d6","datavalue":{"value":{"entity-type":"item","numeric-id":228779,"id":"Q228779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921017$0CED14B2-D7A7-46B0-8C14-CE79792F458A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23be2649b3047d769282fd02a194b75d7b76c1b4","datavalue":{"value":{"entity-type":"item","numeric-id":185070,"id":"Q185070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921017$C92194A3-D065-489B-8C3A-D6904348E8E8","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":"Q921017$40016D3A-8D8B-4A0C-8C63-65F1315E6892","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q921017$D63FA2B1-D2F3-4555-92B9-AFE194398414","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"73b74e7eec4c75cde3baea28ad5a995eb8057fd7","datavalue":{"value":"All the graphs in this paper are understood to be finite, undirected, without loops or multiple edges. An induced \\((k+1)\\)-matching of the graph G is an induced subgraph that consists of \\(k+1\\) independent edges of G. The authors prove several extremal results of this concept. A bipartite graph of maximum degree d without an induced \\((k+1)\\)-matching can have at most \\(kd^ 2\\) edges (Theorem 1). The extremal graphs for \\(k>1\\) are not unique but can be completely described (Theorem 2). When the extremal problem for \\(k>2\\) is restricted to connected bipartite graphs, the extremal problem drops by at least d (Theorem 3).","type":"string"},"datatype":"string"},"type":"statement","id":"Q921017$7AB4F6A7-5656-408D-886C-CA0794447733","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a55663aec12fd5dc29d6a06eb35cad7c86131b6","datavalue":{"value":{"entity-type":"item","numeric-id":594869,"id":"Q594869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921017$E9B8FC23-FD35-49D1-A4D1-1852D6BEDB7A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921017$A169FDDD-E287-4AD2-8125-422373936533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921017$3CE45426-484F-47A8-B1BD-21F8501C2C65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b713c3527f4dec428ce8fa9fa689f50a7cd246d5","datavalue":{"value":"4164904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921017$D4246125-BF83-4E2E-9CA2-68692CB69E21","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q921017$6ED39646-297B-4DC9-855D-2CDFF2F3330A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q921017$9E50B1CA-42FD-4E7D-895C-86520C0510F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q921017$5822E313-75B9-470D-B729-D9C860B8D857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae903708d6f0fe79537345cd261671d5dcf3f6dd","datavalue":{"value":"extremal problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q921017$4851A122-38AF-4C10-AEAC-764D6FE2DB23","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":"Q921017$E693F523-1732-49D5-ABA4-5B5178044EA5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0fd39281a799453c11c1f2ece6adebfe56db4c","datavalue":{"value":{"entity-type":"item","numeric-id":3039368,"id":"Q3039368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921017$E5A17C94-3E13-4098-AB04-A249433DA33E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4006caad69dfa0382a92adbfd038b3e19eaf98eb","datavalue":{"value":"https://doi.org/10.1016/0012-365x(89)90163-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q921017$0AC977C4-7204-429C-8357-921CAD8FB068","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ad4c78eb14954c33aa8deb0588260c4c509225ee","datavalue":{"value":"W2065003601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921017$E940DF83-CE67-4ECF-AC9A-A9C469CBA985","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f3920fd052247c885c133a40542fde7fcdb3590","datavalue":{"value":{"entity-type":"item","numeric-id":2971661,"id":"Q2971661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"420bd2a3ad0dcabf41155c7e917f93ede38a866b","datavalue":{"value":{"amount":"+0.9749496","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":"Q921017$9F03365D-8EF7-463E-9E1E-2C0AAC178FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"784c68f2ba8d5fc31cddab31372956fd89faa048","datavalue":{"value":{"entity-type":"item","numeric-id":1847371,"id":"Q1847371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3541bd94846c65e91260f2dbf2912beb90fba64","datavalue":{"value":{"amount":"+0.9577029","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":"Q921017$D640807E-64B0-4035-8329-6F2AC82F1870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a7f8e9a33e44ae83212e7937c83c450cbe1f6b0","datavalue":{"value":{"entity-type":"item","numeric-id":2816065,"id":"Q2816065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a8c17d65a4e8345ba7de1d1e0dbf64e8f33cd05","datavalue":{"value":{"amount":"+0.94553185","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":"Q921017$4120604D-1A6F-4B96-8794-0EEBAF6585D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"281e29fd2f352d81a7f211d67b78e493a4c6e8d8","datavalue":{"value":{"entity-type":"item","numeric-id":2826215,"id":"Q2826215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd8562f671330de467f364b5d2451d5777a1d39e","datavalue":{"value":{"amount":"+0.9408746","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":"Q921017$D0752820-5564-4A71-94DF-EE3017F030F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f3bf7e966e4bef5b03eecced5ef075d9a2cd3a2","datavalue":{"value":{"entity-type":"item","numeric-id":2059914,"id":"Q2059914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74800bb1934bd698a21b5fe31243ac4e00ab7794","datavalue":{"value":{"amount":"+0.93602777","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":"Q921017$EAC11F16-D30C-4C14-8A13-6081C9430257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee9b494a792d4ce537e8c514fedeb5715a26c619","datavalue":{"value":{"entity-type":"item","numeric-id":687143,"id":"Q687143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e40863f32184c659388eff16e9cfc3aa6dc9567e","datavalue":{"value":{"amount":"+0.93576163","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":"Q921017$B9CAD13B-78D3-4228-94AD-74AA51627717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"818066296f8f7357b7adae432d8616d6edf46003","datavalue":{"value":{"entity-type":"item","numeric-id":4944970,"id":"Q4944970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e2742b4c0453d224823ef69c5053dbcb36b0626","datavalue":{"value":{"amount":"+0.9341521","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":"Q921017$5D302101-9CB3-41E0-89BC-3D376A0F1CE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cba01ec3e19dd81eb237521e9d15c8ee42c32387","datavalue":{"value":{"entity-type":"item","numeric-id":1427466,"id":"Q1427466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0309e14321774cfb338f5bcb1838a6fce3fcc049","datavalue":{"value":{"amount":"+0.9280739","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":"Q921017$3C5E9726-AAAD-43AB-9EE0-BA7B8C5DA73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16fde4330d76758fc9e820bdb303878ec4f904c2","datavalue":{"value":{"entity-type":"item","numeric-id":5918091,"id":"Q5918091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1673558a9c0213ff89e787cdf4c5a5ca61f9f16f","datavalue":{"value":{"amount":"+0.9266694","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":"Q921017$C3B87A30-388F-4AE9-8CCA-A27FDB20905A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d787eaaae1ac29a0a2212c35c22262acbbbb22ab","datavalue":{"value":{"entity-type":"item","numeric-id":5919635,"id":"Q5919635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1673558a9c0213ff89e787cdf4c5a5ca61f9f16f","datavalue":{"value":{"amount":"+0.9266694","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":"Q921017$0299A736-E386-420D-9383-90F641C9496F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Induced matchings in bipartite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Induced_matchings_in_bipartite_graphs"}}}}}