{"entities":{"Q540035":{"pageid":541802,"ns":120,"title":"Item:Q540035","lastrevid":62604966,"modified":"2026-04-11T07:13:24Z","type":"item","id":"Q540035","labels":{"en":{"language":"en","value":"The Fibonacci dimension of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5902985"}},"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":"Q540035$601C61C7-D553-4F38-8346-FF4C012F1AFB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f8e544deaee8154c5140f056928443b89267565","datavalue":{"value":{"text":"The Fibonacci dimension of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540035$14CA71FD-E4D0-4062-A07C-D1226E8A791A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"94b14cef7e6c79dfcaf5c8ebd67d5fbc9489d610","datavalue":{"value":"1217.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540035$7F5A15D8-5B29-48DF-B83F-46636776566E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3bfcf8a87928cedc4cb6acccce2badfe60d93b9","datavalue":{"value":{"entity-type":"item","numeric-id":262252,"id":"Q262252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540035$4C33BF3C-E90F-4257-A7E5-559EC4123B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ceb1fcf1c75dc367d934ec93f0fd1abaa5c7756","datavalue":{"value":{"entity-type":"item","numeric-id":251101,"id":"Q251101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540035$B9928DC4-1590-4115-93B6-FBA12FFD46A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c957339beeae6f46596c701e650eab7f54dbbfce","datavalue":{"value":{"entity-type":"item","numeric-id":283880,"id":"Q283880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540035$14B25DFD-6DEC-4913-92FB-9030E942DB55","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540035$9D36E643-0EDC-4086-AC9E-C489DC9A0882","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca412915d48bc02df19cbc26b81271d64e23ee32","datavalue":{"value":{"time":"+2011-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q540035$885EF296-C64E-4CAE-9793-35CE2D93CA0E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"03447d22f029841dab7af93163e9a18e4625b7e1","datavalue":{"value":"https://eudml.org/doc/232532","type":"string"},"datatype":"url"},"type":"statement","id":"Q540035$89F30443-D7D3-46E0-8AAE-DA0E957E80EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"6b1394185cc8e274c1f1c9d82d883402678c2a2d","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p55.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q540035$A143EE3D-065F-4133-A7E7-8A25913D207E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87b9fd481aef329b152ad9348f48e9eefc0f0554","datavalue":{"value":"Summary: The Fibonacci dimension fdim\\((G)\\) of a graph \\(G\\) is introduced as the smallest integer \\(f\\) such that \\(G\\) admits an isometric embedding into \\(\\Gamma_f\\), the \\(f\\)-dimensional Fibonacci cube. We give bounds on the Fibonacci dimension of a graph in terms of the isometric and lattice dimension, provide a combinatorial characterization of the Fibonacci dimension using properties of an associated graph, and establish the Fibonacci dimension for certain families of graphs. From the algorithmic point of view, we prove that it is NP-complete to decide whether fdim\\((G)\\) equals the isometric dimension of \\(G\\), and show that no algorithm to approximate fdim\\((G)\\) has approximation ratio below 741/740, unless P=NP. We also give a (3/2)-approximation algorithm for fdim\\((G)\\) in the general case and a \\((1 + \\epsilon)\\)-approximation algorithm for simplex graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q540035$92371A74-175C-43DE-8F8B-C3A5612BE3C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540035$DC8230BB-2891-4894-A402-DB95F494326E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540035$4A689161-2760-4077-ADCD-F92C15CB9EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540035$7FCC6DE0-C0AC-4CB5-87FB-03E892A7D77B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2306da75dea1427388fed5155fd879caa849af98","datavalue":{"value":"5902985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540035$DE59BAD8-85F7-4EB8-97C2-3FBDCCCA4605","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":"Q540035$3C777B69-597A-4D95-8D9F-91EB68054B37","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"339e381c29e83deb910a4b78a0cb6c5728ee58dc","datavalue":{"value":"bafkreigu4u5tzd73tqgucaniiosqqzi2vzuqc5fvzlsm2kojkrujxck2ee","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540035$6438359A-80FD-47AF-90A9-17ED05F2AE16","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"510094aa4810d81fae9c14389deb5673cc411501","datavalue":{"value":{"entity-type":"item","numeric-id":2446859,"id":"Q2446859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecc8021c975a9e0c556a6c6157c5c2d14fd33cac","datavalue":{"value":{"amount":"+0.8171434998512268","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540035$C909AB74-DE9E-440E-B7D6-91ADDBD4F831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02210394981bf610d86e9412d198162875874b91","datavalue":{"value":{"entity-type":"item","numeric-id":2350907,"id":"Q2350907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77a906b9f2fe46d2027471c439ed3c8d86bca2bf","datavalue":{"value":{"amount":"+0.8111620545387268","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540035$C2F41592-A36A-48D4-AF4E-B7667F743502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c16d3e4d2a25e2a1585d947b82adbdd1f54c5a2","datavalue":{"value":{"entity-type":"item","numeric-id":658012,"id":"Q658012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"107706351bf78373adc4deff27ee0e1c14852fe2","datavalue":{"value":{"amount":"+0.8015571236610413","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540035$63F4BDCC-9305-4C94-B889-538EC9A960A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d99f4e73c103e9f951616fde93f1b1517aafc4f","datavalue":{"value":{"entity-type":"item","numeric-id":1956242,"id":"Q1956242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14c7c9231e248e02bb280fe9dc598ba24c3533df","datavalue":{"value":{"amount":"+0.7867644429206848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540035$8856821F-866E-49D7-912A-41CD29BEE051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0e052f5b82bfe7e4b019ec428407bbebbdf76d9","datavalue":{"value":{"entity-type":"item","numeric-id":4713817,"id":"Q4713817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43c3ca933a53deff2659323697e60aceb610bf5e","datavalue":{"value":{"amount":"+0.7852774858474731","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q540035$60EFFCE9-DD64-4846-A8AE-C57AF363D186","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Fibonacci dimension of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Fibonacci_dimension_of_a_graph"}}}}}