{"entities":{"Q2478167":{"pageid":2488910,"ns":120,"title":"Item:Q2478167","lastrevid":44166450,"modified":"2025-11-20T12:47:33Z","type":"item","id":"Q2478167","labels":{"en":{"language":"en","value":"Tight lower bounds on the size of a maximum matching in a regular graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5250086"}},"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":"Q2478167$C54E2528-2195-421C-8D0E-DECD7EA8C93F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e27ed19d5069d107514ab0bc355f2419868d60e","datavalue":{"value":{"text":"Tight lower bounds on the size of a maximum matching in a regular graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2478167$2C6E90AB-0D08-4501-AFE0-9D45BB3EFF07","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"922412c92322ed02b2533bc1730cb34e56b3c904","datavalue":{"value":"1143.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2478167$C0FFE6AA-92EB-4D9C-8CCB-F712721511C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ef3efb47b5163e35efff4dde79a3bbdd3dc566b","datavalue":{"value":{"entity-type":"item","numeric-id":186200,"id":"Q186200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2478167$E428769F-73B3-4325-AEB8-E93B375E5B36","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":"Q2478167$CB0AF4F7-B982-4364-9A03-66F8A594BD1A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2478167$01930D36-F302-4F34-B760-5AD17070BCE3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d80a5c8b6f628310cf811f48b9c17f65f1aa8a2b","datavalue":{"value":{"time":"+2008-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2478167$2D623131-4001-4BF3-BE4C-798C28AA90FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa1b70efda1166a146f605147aec5c847314f4d7","datavalue":{"value":"A set of pairwise nonadjacent edges of a graph \\(G\\) is called a \\textit{matching} in \\(G\\), while a matching of maximum cardinality is a \\textit{maximum matching}. There are two recent very useful surveys on matchings in graphs: References [5] and [6] of the present paper. Recently some lower bounds are introduced for the size of a maximum matching in a regular graph (references [2] and [4]). In this paper also the authors by applying the well known Tutte-Berge formulation for the matching number \\(\\alpha'(G)\\), i.e.  \\[  \\alpha'(G)= \\min_{X\\subseteq V(G)} {\\frac{1}{2}}(| V(G)| +| X| -\\text{ oc}(G-X)), \\]  obtain interesting lower bounds for the size of a maximum matching in a regular graph. They show that for a connected \\(k\\)-regular graph \\(G\\),  (i) if \\(k\\geq 2\\) is even then,  \\[ \\alpha'(G) \\geq \\min\\{(\\frac{k^2+4}{k^2+k+2})\\times \\frac{n}{2},\\frac{n-1}{2}\\}, \\]  (ii) if \\(k\\geq 3\\) is odd then,  \\[ \\alpha'(G) \\geq \\frac{(k^3-k^2-2)n-2k +2}{2(k^3-3k)}\\cdot \\]  By constructing a class of regular graphs, in each case, they show that these bounds are realizable. We noticed the following misprints: On page 655 lines -11 and -10, all \\(w\\)'s should be \\(v\\)'s.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2478167$E96D6970-73CC-47C3-9171-4DB2A32838A0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c028bb8c66668c8ac76bc7a6bb4415aaa23a35a8","datavalue":{"value":{"entity-type":"item","numeric-id":322366,"id":"Q322366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2478167$3A67867C-334D-4AF7-8172-EC04046AC66B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2478167$6F5F7075-DBED-474A-9DD9-1F051057CAF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2478167$0669C9E2-AD11-44C8-ACB8-0311555FFA04","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c50231c6e8883dbac47e0ba26cc852b00c2ebd23","datavalue":{"value":"5250086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2478167$5B5EBA7D-C7F5-4A74-AEAF-F88528E2AC00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3842779000597abe3dc3cef2451250276bc01d5","datavalue":{"value":"maximum matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2478167$08425CB9-61C2-4FB6-88E1-B93BDE1A59C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2478167$A6B5DAE7-A998-44FE-949C-02B6D409ABC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2478167$184B7F43-A9D9-47E9-87E8-5CFFB2B8F1F0","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":"Q2478167$566C25D7-2B48-4BC1-AFD3-A56866AF4DC6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"54c6cba2cb72e95a3756fa6bf7e8472cfda7ef03","datavalue":{"value":"https://doi.org/10.1007/s00373-007-0757-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q2478167$0CBD0869-B84E-4869-85F6-B91E3AA6C92E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99a10ccb411a24cbde3265638b64e9559ce9cc88","datavalue":{"value":"W2035633339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2478167$1EE80E11-86EB-4C2F-9B33-F6D79E61B4B5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"498893103a6d92ad89921d985362ceb50f779362","datavalue":{"value":{"entity-type":"item","numeric-id":1877645,"id":"Q1877645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2478167$43DF4605-DEC2-453C-8971-1CDB61570CF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fadb8d1750f4aea8a18e04321045caa9919aac06","datavalue":{"value":{"entity-type":"item","numeric-id":1043811,"id":"Q1043811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2478167$08E69777-A8B4-44CF-8359-8671CC48F5E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67bacf332f969eb6f43028234d17ab8c714a9d35","datavalue":{"value":{"entity-type":"item","numeric-id":4871750,"id":"Q4871750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2478167$6403BF31-D498-4904-85C6-D36F695DE2A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ce24a17e21c88b2662e26e0c78015b9d56999808","datavalue":{"value":"10.1007/S00373-007-0757-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2478167$590D42BD-9BFC-47DC-B6E4-82260F69DEC4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6441f470722b9231616a07bab2bb6bc127529031","datavalue":{"value":{"entity-type":"item","numeric-id":2222947,"id":"Q2222947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1741488b32dc800029ec4facd81bcc3784286c9","datavalue":{"value":{"amount":"+0.9579159","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":"Q2478167$E848E6EA-2642-4B26-99A0-0C25BCBE83EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a580d8e05005bfb2a75bf76ad34bd1e41a841d7d","datavalue":{"value":{"entity-type":"item","numeric-id":4553732,"id":"Q4553732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87b54c52e918d53e438da4fdb30b6055684e3156","datavalue":{"value":{"amount":"+0.95077837","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":"Q2478167$F6BDF4A1-4E96-410F-8899-2DE74B6C049B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e01637b2fcd1af0df20247760c4bed52030c34f1","datavalue":{"value":{"entity-type":"item","numeric-id":1877645,"id":"Q1877645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b562896c9108c0cce540749017c88c2445cab4a","datavalue":{"value":{"amount":"+0.9467168","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":"Q2478167$203EFD1D-1265-4516-B35A-27AB2D556A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7880c54fad19ab406d7a2092d7d18ec8ef22f4c1","datavalue":{"value":{"entity-type":"item","numeric-id":4474098,"id":"Q4474098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b562896c9108c0cce540749017c88c2445cab4a","datavalue":{"value":{"amount":"+0.9467168","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":"Q2478167$BE35FD7C-5BB3-4283-87BD-F8B19BFBD650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e65e54ceffe500e00ba4d80ab495005fc15001a","datavalue":{"value":{"entity-type":"item","numeric-id":1949755,"id":"Q1949755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1c26bf41b20bd576a749417ba3fdd8c7f4fcac7","datavalue":{"value":{"amount":"+0.9425053","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":"Q2478167$E3EB619D-5430-42EC-BC79-538DD0D5649A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff43ba2fef2a734364bd7e5a1ad3617dab8737a","datavalue":{"value":{"entity-type":"item","numeric-id":394310,"id":"Q394310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2964f67c1bec8ddcb8b6b830ed8aae759e083e6","datavalue":{"value":{"amount":"+0.94216824","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":"Q2478167$97104190-0C16-489D-961B-4CB7AC12D705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9216e6fef54fb7a03ef002146d80fa7b3e02bda","datavalue":{"value":{"entity-type":"item","numeric-id":5382147,"id":"Q5382147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bedbd7fb94f267a99dc7a8bc003bf336d1c1309","datavalue":{"value":{"amount":"+0.9400455","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":"Q2478167$49917054-D85A-4A83-9450-1DEC120FCDBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f037db2eb41f7eae7fe833b526cfc4a455443326","datavalue":{"value":{"entity-type":"item","numeric-id":5898479,"id":"Q5898479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1229fa2fb7b1a1ead6f521082d7d67cad3c9e1f","datavalue":{"value":{"amount":"+0.9396448","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":"Q2478167$A00BA152-E29F-46C8-AF32-BA82E75ACDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c512fbf5ea4629dcd8473ba379ac8b169dc2cb99","datavalue":{"value":{"entity-type":"item","numeric-id":4722104,"id":"Q4722104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f549c820fd9d0a0e911f729046eb0f546aac8db6","datavalue":{"value":{"amount":"+0.92834544","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":"Q2478167$835CD9B1-76E7-47C1-A03F-CB0DFFDB8E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646ebc317da9ee34a6de2159a804130311b72bc5","datavalue":{"value":{"entity-type":"item","numeric-id":607026,"id":"Q607026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec027cda4f09aac202f6f6df130fa92d683776fe","datavalue":{"value":{"amount":"+0.9268931","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":"Q2478167$1D1795F1-5E99-4CB7-904B-2091DFBD5FFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2478167","badges":[]}}}}}