{"entities":{"Q789416":{"pageid":791264,"ns":120,"title":"Item:Q789416","lastrevid":64390362,"modified":"2026-04-11T19:32:46Z","type":"item","id":"Q789416","labels":{"en":{"language":"en","value":"On the sphericity and cubicity of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3845633"}},"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":"Q789416$3B3BD095-3D74-4E7E-A449-33C1D314632D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b560ee21cd181916a60d07abca203d29395d0c05","datavalue":{"value":{"text":"On the sphericity and cubicity of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q789416$A54B4128-9E67-4D16-A046-FAA69F1F5BF5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07c7975a3816fb40572e44d90d3a2232116cb4d8","datavalue":{"value":"0533.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789416$7B671A39-F49A-4519-BC7A-AF787B8A20C9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1d5adad7591bf4492c10bf6211ca92626a3f0f2c","datavalue":{"value":"10.1016/0095-8956(83)90057-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789416$29F2BEF9-24D5-403E-B469-D101822EF712","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6077ee98d9630e9737fc0514d33b3b5053e02ef2","datavalue":{"value":{"entity-type":"item","numeric-id":221502,"id":"Q221502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$2F7A6ADF-A4FF-482E-A6A2-4180B78758D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$B065DD08-0DDA-4DC8-ACE4-6F22B157BB74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q789416$B37C37B7-0C3A-41A2-8229-A1AB3B904DCD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2fe8a0b2493850f0dcf4f310e5a20fc7d4b0065f","datavalue":{"value":"The cubicity of a graph G is the smallest n such that the vertices in G can be mapped into closed unit cubes (edges parallel to the axes) in n- space so that two vertices are adjacent in G if and only if their assigned spheres intersect. The sphericity of G is defined similarly using closed unit spheres instead of cubes. It was shown in [\\textit{F. S. Roberts}, Recent Progress Combin., Proc. 3rd Waterloo Conf. 1968, 301-310 (1969; Zbl 0193.243)] that the cubicity of the complete N-partite graph \\(K_{2,...,2}\\) is N, and in [\\textit{T. F. Havel,} Ph.D. dissertation, Berkeley (1982, p. 234) see also Congr. Numerantium 35, 361-371 (1982; Zbl 0516.05060)] that the sphericity of the same graph is 2 when \\(N\\geq 2\\), so that cubicity can be arbitrarily larger than sphericity.    In the reviewed paper, the question of whether a graph's sphericity can exceed its cubicity is answered in the affirmative: for each of \\(n=2,3\\), a family of graphs with cubicity n is constructed and it is shown that the sphericity of these graphs must exceed n. The actual values of the sphericities are not calculated; so it is left open whether sphericity can significantly exceed cubicity. It is also left open whether there exist graphs of cubicity \\(n\\geq 4\\) whose sphericity exceeds n, and it is shown that the proof technique used for \\(n=2\\) and \\(n=3\\) breaks down for \\(n\\geq 5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q789416$553967CD-E68C-45DE-83CC-719082D22E40","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789416$271B4126-EE55-4DFD-ABC3-F47BBBA5DD66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76cae80e5e24506bb3d6df2b19b993aefbed5b5c","datavalue":{"value":"3845633","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789416$96ACF282-A268-49AD-868B-FED3041D934D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85a22ccc86b3b3959b6fddc0f7abebfad01ef9a1","datavalue":{"value":"unit-diameter spheres","type":"string"},"datatype":"string"},"type":"statement","id":"Q789416$2D7B34D3-A3E5-4B2E-9AD7-EE2BCFB97A3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e58047e3d5057ed0f01d1973015b5569826e2564","datavalue":{"value":"unit cubes","type":"string"},"datatype":"string"},"type":"statement","id":"Q789416$E078923B-BC38-40AC-A089-F9FA5649D5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"863d90c74cddaf658d1037277d1cf9c2fb806265","datavalue":{"value":"sphericity","type":"string"},"datatype":"string"},"type":"statement","id":"Q789416$123F6BFE-4471-4E99-A647-DC7B97112057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba8f9aa88bb3241f9100e65ab8dc861bb79feec1","datavalue":{"value":"cubicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q789416$A0E5B10C-857E-4F44-A5BF-6B3C489AE87A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$5343EF34-81CC-4424-9F33-50BCDB9DD773","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":"Q789416$3EEA17E5-94C7-4503-81C8-7A8D2C1A7949","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e3a3320129c508974ce30da8d9fd756b53d74bc3","datavalue":{"value":"https://doi.org/10.1016/0095-8956(83)90057-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q789416$45638F05-DB52-4D7A-8B2D-0BADC3533AD1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"501a3d333e74ab4107ea615a4ee11f1325ca7270","datavalue":{"value":"W2036640404","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789416$C8F31082-00E4-45A9-98E9-639EB90D8B6C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$A8AE9B3B-B0B3-462C-9E9A-B3B17600C4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7f66135fe18fd69ebdf9dddcd1f014b077affa4","datavalue":{"value":{"entity-type":"item","numeric-id":3663348,"id":"Q3663348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$9A59B762-DE5F-4D59-8D88-4D76B49A47F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3a38712b31f963fa35655767fef7a0a52215e1a","datavalue":{"value":{"entity-type":"item","numeric-id":4194048,"id":"Q4194048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$A0A094C5-F18F-416C-A394-D7B91F13E965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"196a684f63929c4141b35f71d7498adcba261ffd","datavalue":{"value":{"entity-type":"item","numeric-id":595671,"id":"Q595671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$4C88CF0B-0307-42BC-A34E-10D9EA69FA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ea24d0d08bd225859187316389977dd9b54dcc","datavalue":{"value":{"entity-type":"item","numeric-id":5588433,"id":"Q5588433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$CDDC087A-4AE7-4BAF-96B5-F2E497241F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd444ac2099fb3b5a15da02a0171b8b4a45b7ea","datavalue":{"value":{"entity-type":"item","numeric-id":5588432,"id":"Q5588432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$70395BBF-96D1-461F-9049-F72BC52445D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e391041a85d1e9612197d6b6c0b07d23ac311188","datavalue":{"value":{"entity-type":"item","numeric-id":5568974,"id":"Q5568974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$6807C99D-DC40-414C-9128-C672B4E0C607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ec1943eba5ed8c491829a013130a4d281196f7d","datavalue":{"value":{"entity-type":"item","numeric-id":5665244,"id":"Q5665244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$17CB9620-0CCC-4EE4-8768-5C53FE4B12A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83e358645f83771721a37bf4e7b0420ebd174d8c","datavalue":{"value":{"entity-type":"item","numeric-id":3953699,"id":"Q3953699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789416$E384816F-BDC4-4F8D-96B3-50A089AB17E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25c5b043ebdfad3cbf05550d130b35946b69126e","datavalue":{"value":{"entity-type":"item","numeric-id":1077426,"id":"Q1077426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dbbd9bccc34fb7459b5d058303f25f73f0574dd","datavalue":{"value":{"amount":"+0.83928317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$CCACC692-49DD-4B5D-A0F8-A3E0F8EE1443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"016d45fd2f8f32a5c183f8de25eedffd4f84b318","datavalue":{"value":{"entity-type":"item","numeric-id":807631,"id":"Q807631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da7acbbf60023f1c793b9e7516a684a68e9f90ff","datavalue":{"value":{"amount":"+0.7497911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$9831C882-AE19-4A9C-B4E0-1D2475EEB714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a0ce5ccada493a242ac61fe3266673082d92ba4","datavalue":{"value":{"entity-type":"item","numeric-id":581416,"id":"Q581416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf90c7c1b7745c3e2abb86f5a45c3a737f3b2594","datavalue":{"value":{"amount":"+0.7475301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$03EF4172-61FA-41FC-9D89-B114175FC308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06b7e00a6780e7856ce7339be4a1802e916d01e1","datavalue":{"value":{"entity-type":"item","numeric-id":4429239,"id":"Q4429239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b51320ae5633fc1464b0c5e7f765339e848dc3d","datavalue":{"value":{"amount":"+0.74072367","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$EB2E1C05-A3A3-4696-A079-F1E4A5204FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ff9fb7d147be067d88fd2a8e941c518f7ed551b","datavalue":{"value":{"entity-type":"item","numeric-id":1867285,"id":"Q1867285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c866cbf9859be754115922f4d6c44266d203890","datavalue":{"value":{"amount":"+0.73905313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$A6975DCE-8BA6-4028-99FA-D0B876DD1EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c9e16d3fa477d3156b0d810d3d48bc8c4558c11","datavalue":{"value":{"entity-type":"item","numeric-id":1173697,"id":"Q1173697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4fba75d0af46075d44d2addd8f130d1bf9c4d03","datavalue":{"value":{"amount":"+0.73885924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$A22D6E38-6045-448E-9483-B25B25E581BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5c89954bfada91970ade222f6faa33a3d021ecd","datavalue":{"value":{"entity-type":"item","numeric-id":636729,"id":"Q636729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a9b0eef3a40114423f063be1ecb8817bdb35422","datavalue":{"value":{"amount":"+0.7384967","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$A4674287-0312-4741-9A2A-083A8999FD02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a1c2298b03122768600cdc90285c9abc3916a07","datavalue":{"value":{"entity-type":"item","numeric-id":5387702,"id":"Q5387702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14009db1f9997be9f24ccdc0b9162858fe778537","datavalue":{"value":{"amount":"+0.7360155","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$7A48974A-2DEB-4516-BCFE-C446BD9087E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bfcd5da03418f621eaab8ddfc99bc37fc14bd71","datavalue":{"value":{"entity-type":"item","numeric-id":685682,"id":"Q685682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"463b162954e35b239f8ca2d890f0d294bad71857","datavalue":{"value":{"amount":"+0.72428477","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$A3C66FB9-B1C7-4F04-8349-11E19C3F4B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2ef679d3f009911aa8d7818f4bdf6070103f871","datavalue":{"value":{"entity-type":"item","numeric-id":4221902,"id":"Q4221902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2fb3a814cd76b31cda5e6a8b38eadcd1c34a429","datavalue":{"value":{"amount":"+0.7204399","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q789416$542F9862-38F1-41EC-857D-777CF2F295D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the sphericity and cubicity of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_sphericity_and_cubicity_of_graphs"}}}}}