{"entities":{"Q686447":{"pageid":688296,"ns":120,"title":"Item:Q686447","lastrevid":63717633,"modified":"2026-04-11T15:03:55Z","type":"item","id":"Q686447","labels":{"en":{"language":"en","value":"Bounded degrees and prescribed distances in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428302"}},"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":"Q686447$B519CF62-9AE2-47E4-B275-74E39A5F2C6A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9f18281237444a08c6c061d239baa14a3cf4fd8","datavalue":{"value":{"text":"Bounded degrees and prescribed distances in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686447$0F6A2BB0-80D3-4AD7-9605-DD3604636F3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"06afb0f73cfb3bf3c9d384b6ec148da9a11833bb","datavalue":{"value":"0786.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686447$3FE4C1D2-DC61-4F40-9779-E567730DCF75","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"68fdae9db0b2a4ed9118de4553106cd4ef22a1a1","datavalue":{"value":"10.1016/0012-365X(93)90144-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686447$DA8BBB94-0D72-4B31-BF77-F32F6D8860A8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ed6f21f55f5293ad80f20217ff98c9b7054441c","datavalue":{"value":{"entity-type":"item","numeric-id":168472,"id":"Q168472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$FE5DEB5C-8B48-455F-87BF-110EF7E20572","rank":"normal"},{"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":"Q686447$13E7D3DA-0E00-4D3F-AF09-C5AE9ED890F3","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":"Q686447$64A67AB5-1EE9-49B9-B6BF-D1DC6AAEDF20","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae4d7b05535bc7692a75fc587d4810a7bdebded5","datavalue":{"value":{"time":"+1994-05-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686447$E369DA9A-217C-45E7-9111-0EEA3D7F1018","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9200ed6639792ea48ea27425c5c7c63522f08abe","datavalue":{"value":"Two disjoint vertex sets \\(X=\\{x_ 1,\\dots,x_ m\\}\\) and \\(Y=\\{y_ 1,\\dots,y_ m\\}\\) of the same cardinality \\(m\\) are said to form an antipodal set-pair of size \\(m\\) \\((m\\)-ASP) if \\(d(x_ i,y_ i)\\geq 3\\) and \\(d(x_ i,y_ j)\\leq 2\\) for \\(i\\neq j\\). It is shown that if \\((X,Y)\\) is an \\(m\\)-ASP and \\(d(x)\\leq p\\) and \\(d(y)\\leq q\\) hold for all \\(x \\in X\\) and \\(y \\in Y\\) for some natural numbers \\(p\\) and \\(q\\), then \\(m \\leq \\min \\{ {p+q+1 \\choose p},{p+q+1 \\choose q}\\}\\) and it is conjectured that an even tighter bound holds, namely that, \\(m\\leq{p+q\\choose p}\\). The authors show that there are graphs for which the bound in the conjecture is sharp. They also prove the conjecture when the graph satisfies some further conditions. It is then shown that in a graph of maximum degree \\(k\\), the size of an \\(m\\)-ASP is at most \\(k(k+1)/2+1\\). Moreover, for every \\(k \\equiv 0\\) or 1 (mod 4) there is a \\(k\\)-regular graph with an induced \\(m\\)-ASP of size \\(k(k+1)/2+1\\), and for \\(k \\equiv 2\\) or 3 (mod 4) there is a \\(k\\)- regular graph with an \\(m\\)-ASP of size \\(k(k+1)/2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q686447$4321FF5B-A70D-4208-A87B-297C3122D5AF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$617AB0A0-E0BC-4412-B3DE-329339D7E06C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686447$B1362228-F757-4E14-BDA4-E7CA42FDBAD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686447$AADE2FE5-3E60-4E20-B712-42D4E66B4F97","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d72e5d44372d9abfb55ab3fd7328f27b478183bd","datavalue":{"value":"428302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686447$17C7EA2E-3675-49AC-8CF1-0B24BA435395","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d26cf14e6fa087e76a2aa23e0588ddfc55209eb","datavalue":{"value":"prescribed distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q686447$B58B4A96-AE8A-4333-B594-035B24278BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"680f525d9dc2a46600ffab2cbabebcfef8c1494c","datavalue":{"value":"antipodal set-pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q686447$9D9CE545-57DE-4CB7-B737-069E2B38F406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6906d309434fd0c76118d23a6a15594e9c5ca39","datavalue":{"value":"bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q686447$D571B384-357F-4732-A46D-028D970D3725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q686447$E5305874-4A13-48D1-A822-9D8C239AEB30","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":"Q686447$9CF672AD-2A69-4607-8718-71D5ED5D2CF3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9edecb511440383399e02e73639f3f749f79ed35","datavalue":{"value":{"entity-type":"item","numeric-id":5512798,"id":"Q5512798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$C490D49D-ACA3-429A-9B4D-51F8E636BDE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"537ba3b17ab4b056dd39fdc5a7b521309988d370","datavalue":{"value":{"entity-type":"item","numeric-id":1121913,"id":"Q1121913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$3C547EA4-115D-4891-A8F5-0F5D9650F2C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9881c1ae62081c6d316c874c058699bb32ffc793","datavalue":{"value":{"entity-type":"item","numeric-id":1165848,"id":"Q1165848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$0BD461A1-BD15-45A0-ACA3-34EC5C880214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90123fb8b3bc5647d627b7df7c71b59ab30ee438","datavalue":{"value":{"entity-type":"item","numeric-id":762464,"id":"Q762464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$B03B0A72-8B64-411D-A6C5-267E76EF8160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"685a25ccac67774bd926893fe5762f26c33d7d8c","datavalue":{"value":{"entity-type":"item","numeric-id":4133994,"id":"Q4133994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$13186B3E-F59E-4004-8DD4-7A460009A70E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15dab792519a2d2ecab1e35f06c8cf4c7305d744","datavalue":{"value":{"entity-type":"item","numeric-id":1071788,"id":"Q1071788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$5C7C5BF0-471D-41D1-A741-45E1C301F126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0feced9c4040ac614449d8ccb3b8151a9cb71852","datavalue":{"value":{"entity-type":"item","numeric-id":1090680,"id":"Q1090680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$62A8F357-D69E-4DA2-96C2-7B92DC73C4CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d593f6f740b923d727253fd62f65c3d592670fd","datavalue":{"value":{"entity-type":"item","numeric-id":5750908,"id":"Q5750908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$4C7C7012-950D-4652-AAC3-A52EBDD58F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66a10aaf9678c895a0f5781d7c0c71d26ee4fcf1","datavalue":{"value":{"entity-type":"item","numeric-id":1823939,"id":"Q1823939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686447$718FC115-6F38-495F-86C9-C781CFB08FC8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18cd2b16affa6a852f81982d042e38805e47aaed","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90144-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q686447$941AE11E-974F-49CD-83D4-424F1E0F3812","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e5cce275c6d0ef3cc196eb58945ae485337c3117","datavalue":{"value":"W2044686427","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686447$16F0E0AD-595E-43CB-9E76-6AA47775915D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d59647a4fc116dfbafc2e0dca40146e25c62a2cc","datavalue":{"value":{"entity-type":"item","numeric-id":4978077,"id":"Q4978077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b30d34427c3da3c7b76d9667a8c123594ca90d02","datavalue":{"value":{"amount":"+0.95663035","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":"Q686447$36C19308-F8D2-451B-AB27-530BE6921865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fb83e9766a80aca58c64269ac02b4ca8fd2c4ab","datavalue":{"value":{"entity-type":"item","numeric-id":1272673,"id":"Q1272673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"331dbf77e5997c46ff13ce56f68cd4d858bf9e88","datavalue":{"value":{"amount":"+0.93871963","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":"Q686447$9B675027-5569-412E-A117-D78841A15497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45b68e2529157467d98225c57ce9afd712cd9747","datavalue":{"value":{"entity-type":"item","numeric-id":2724758,"id":"Q2724758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d51a7ca8dc5a2f1b620568350436ade15b5ee55f","datavalue":{"value":{"amount":"+0.92549765","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":"Q686447$F82C57CB-AAF8-48F8-BD9D-8935D9B346BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2c2d04026b55115b9524b0939b25a51f95c28af","datavalue":{"value":{"entity-type":"item","numeric-id":2907818,"id":"Q2907818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33f9b09065ec10765a147c9da678669cbc332f13","datavalue":{"value":{"amount":"+0.9174485","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":"Q686447$CC471773-8AC1-49A6-A753-589FE49F0CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56a400c2aec5d69ef308c6c0205e4545d9ca6db2","datavalue":{"value":{"entity-type":"item","numeric-id":5928866,"id":"Q5928866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b432675b0eceb0e8b4d13da059805c25b009c25","datavalue":{"value":{"amount":"+0.91307545","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":"Q686447$583D97C4-945F-4ADA-8E68-C72E6DDF0017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4948a70b66fced83e273185e8f410a9ab47c0ec0","datavalue":{"value":{"entity-type":"item","numeric-id":4232787,"id":"Q4232787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b371cc9a5a2bbf371e569cc4ac931aec1b8fb7f","datavalue":{"value":{"amount":"+0.9130752","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":"Q686447$FEBACE4A-7AD7-44B4-87DC-A19950D9BA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aeb76d5a3a8bd79b78a7ed2a128ed1448e29f94d","datavalue":{"value":{"entity-type":"item","numeric-id":4651509,"id":"Q4651509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6db2bfd2ec9b34045673318fca65add2b54970eb","datavalue":{"value":{"amount":"+0.90922415","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":"Q686447$DE225A50-7ECB-4216-90CB-8B0555301278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2aa5e17bfb9fda7e1a7b822b45a5aa02263277f","datavalue":{"value":{"entity-type":"item","numeric-id":2568492,"id":"Q2568492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"296288be79c3ab0c22c01e640e207989b1e8b7bd","datavalue":{"value":{"amount":"+0.90785885","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":"Q686447$D89B14B8-B9C5-45F9-8060-C5C4912B89BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4db4ae9ba6cbd29ae95f09ea951d5b0784f28a66","datavalue":{"value":{"entity-type":"item","numeric-id":3366929,"id":"Q3366929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df94e1030c61c7691df5965c3f1ca35329992558","datavalue":{"value":{"amount":"+0.9078427","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":"Q686447$C901225D-DAA6-4CF6-9B98-966512AE4282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"360ac87e4718fc826c76d5e9dac98429b9fcf8b8","datavalue":{"value":{"entity-type":"item","numeric-id":967319,"id":"Q967319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38a05cc46c427997877aed6636a70f9f0fbe7cce","datavalue":{"value":{"amount":"+0.90630245","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":"Q686447$72CABDD7-F395-45D3-8EE6-0314712A45C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded degrees and prescribed distances in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_degrees_and_prescribed_distances_in_graphs"}}}}}