{"entities":{"Q540085":{"pageid":541852,"ns":120,"title":"Item:Q540085","lastrevid":62605398,"modified":"2026-04-11T07:13:30Z","type":"item","id":"Q540085","labels":{"en":{"language":"en","value":"Growth of graph powers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5903018"}},"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":"Q540085$BCBC58B1-4D00-4F46-9FD9-1715FB63AB82","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"40b304a5bf2da27659d5c37abd1c3efc23248da3","datavalue":{"value":{"text":"Growth of graph powers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540085$4494E259-4D35-48A4-B8ED-83B7BA138F17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"16a259e98306c70ff8fd01bf066c304a0175797e","datavalue":{"value":"1217.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540085$6757FE9C-ADF5-4D1E-8E72-9D7598F31624","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf458a392ae0db17eb0f85a88967799de18440d2","datavalue":{"value":{"entity-type":"item","numeric-id":322268,"id":"Q322268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540085$CDFC3978-9FAB-4CFC-9613-3B05A1D9AAA2","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":"Q540085$71606303-F8BC-4F4D-8E2C-7841E97CAE9D","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":"Q540085$655ACEDB-A4D4-4C07-B190-F3A5ABF511A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1b8c11de83ad5dde9babd08da4f8e3a9628e20d","datavalue":{"value":"https://arxiv.org/abs/1005.2542","type":"string"},"datatype":"url"},"type":"statement","id":"Q540085$61C11950-9D25-436E-B765-98F618C7EB83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"10efb320c1c164b5969fcc227abf9fc577f1732c","datavalue":{"value":"https://eudml.org/doc/226940","type":"string"},"datatype":"url"},"type":"statement","id":"Q540085$7CB5AE03-52F1-4CAD-B921-3CAEFEAB885A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c04fa1a4c9a81f44ce3f84f1169a82210574277b","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p88.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q540085$1F0E572B-3797-40CA-9C5F-5D5054DABC3B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a845edc0700d007ebbcd3f4d26f3f09150e95ead","datavalue":{"value":"Summary: For a graph \\(G\\), its \\(r\\)th power is constructed by placing an edge between two vertices if they are within distance \\(r\\) of each other. In this note we study the amount of edges added to a graph by taking its \\(r\\)th power. In particular we obtain that, for \\(r \\geq 3\\), either the \\(r\\)th power is complete or ``many'' new edges are added. In this direction, Hegarty showed that there is a constant \\(\\epsilon > 0\\) such \\(e(G^3) \\geq (1 + \\epsilon)e(G)\\).   We extend this result in two directions. We give an alternative proof of Hegarty's result with an improved constant of \\(\\epsilon = 1\\). We also show that for general \\(r, e(G^r) \\geq (\\lceil \\frac{r}{3}\\rceil-1) e(G)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q540085$4C9A7DCB-5505-4FB5-854D-553C7ECF2234","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540085$C4176B70-6D24-4B28-A8AD-62B84B147377","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"39d2ef868ebd570d06964f27260629effca02256","datavalue":{"value":"5903018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540085$B67903AF-D1B0-43B2-A515-A1F867185698","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":"Q540085$318562CF-FDE0-4F70-A107-52E5C87B32A0","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"32574e84bd4098bd0b19b75615a5d38fce6f4f1e","datavalue":{"value":"bafkreifoybws6lx34mkrkvczhqgzdymlct7lfupu3mhi3bff3xtqhyxpwq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540085$773C95DA-B24D-45DA-99F4-7D1F110108BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5830f0a46bcc4f16e764e90c09180aaa9b0bddbb","datavalue":{"value":{"entity-type":"item","numeric-id":2876017,"id":"Q2876017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9877e7e4b8c60b6381e2f795b142354b8ce9272e","datavalue":{"value":{"amount":"+0.9020876884460448","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":"Q540085$8A868444-12B9-4655-8A01-4839B62D1A20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7019f52479208a3343ecf53986c2d8cf8c43a958","datavalue":{"value":{"entity-type":"item","numeric-id":643002,"id":"Q643002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"718fc581816bf7f34b3c614edfda4d678b6a2dd1","datavalue":{"value":{"amount":"+0.8216204643249512","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":"Q540085$71B71E1E-3F19-43A0-97D7-7FC29C2ABBE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2520322f0db1e6f509be7e671c892180a26eac5e","datavalue":{"value":{"entity-type":"item","numeric-id":2855624,"id":"Q2855624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"514f041c318cfd418bce14de6baa5e35bca2a26e","datavalue":{"value":{"amount":"+0.7391731142997742","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":"Q540085$31D3C78A-5B8B-4294-B710-2840F9B866DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28a3888455b4a547e83f97b0cffad3b43eae5ace","datavalue":{"value":{"entity-type":"item","numeric-id":4908821,"id":"Q4908821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73685d9c68ea0779f5d0ef99d4fb9bd6005df543","datavalue":{"value":{"amount":"+0.7376953363418579","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":"Q540085$CB66E136-B5A2-4F25-AFEE-2227E6D89DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"514efd6bed0f8c39226363ae22868e212463e6a7","datavalue":{"value":{"entity-type":"item","numeric-id":5753991,"id":"Q5753991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5805654179fdb7e54d54eb79650e6f22f15e86bf","datavalue":{"value":{"amount":"+0.7343023419380188","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":"Q540085$7DF85C2A-C85A-4904-BF24-28E29F92F499","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Growth of graph powers","badges":[]}}}}}