{"entities":{"Q1010910":{"pageid":1012758,"ns":120,"title":"Item:Q1010910","lastrevid":66004539,"modified":"2026-04-12T06:53:06Z","type":"item","id":"Q1010910","labels":{"en":{"language":"en","value":"Repetition number of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541072"}},"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":"Q1010910$3657DD3A-49DA-4912-A7D0-F37556D8A9FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8b9043cca734584e54dc70d3089e4beb24e5968f","datavalue":{"value":{"text":"Repetition number of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010910$252ED92B-5014-4B12-A094-048175F6C37A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"484897b8600e315c8f682d7baac90d5b7c70b894","datavalue":{"value":"1178.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010910$C5D620E7-2C95-4022-A509-9C445D010496","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":"Q1010910$9D415E06-D30D-4DBB-A0CB-563DB14CB570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010910$0E0329EC-BB8D-4BC0-A2B8-DAB280B53E34","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":"Q1010910$CA3F5E60-D2D7-40C4-8E3D-958A946577FE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010910$57C5D5E0-B90E-40F1-8BC7-67EC5B21529F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1372e6cb1fdcda92150ac6d3ce2c91eb6e951f78","datavalue":{"value":"https://eudml.org/doc/117292","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010910$B5A7E63E-450B-4AB4-B3C9-F98088E39A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"9811130fa05ddd84ff024ef0a54815ac76ea3ce2","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r7.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010910$02F1EB2A-C755-4BB3-9C02-254586F0D958","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e3a1d0c4824a8932d4bbb0d7345e61191545d0c","datavalue":{"value":"Summary: Every \\(n\\)-vertex graph has two vertices with the same degree (if \\(n\\geq 2\\)). In general, let rep\\((G)\\) be the maximum multiplicity of a vertex degree in \\(G\\). An easy counting argument yields rep\\((G)\\geq n/(2d-2s+1)\\), where \\(d\\) is the average degree and \\(s\\) is the minimum degree of \\(G\\). Equality can hold when \\(2d\\) is an integer, and the bound is approximately sharp in general, even when \\(G\\) is restricted to be a tree, maximal outerplanar graph, planar triangulation, or claw-free graph. Among large claw-free graphs, repetition number 2 is achievable, but if \\(G\\) is an \\(n\\)-vertex line graph, then rep\\((G)\\geq\\frac{1}{4}n^{1/3}\\). Among line graphs of trees, the minimum repetition number is \\(\\Theta(n^{1/2})\\). For line graphs of maximal outerplanar graphs, trees with perfect matchings, or triangulations with 2-factors, the lower bound is linear.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$F08BD5CD-9F0F-4AA9-8090-4F99D6052E0D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010910$AA98B114-B268-4386-AAD1-C62013EE8383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010910$58A857D3-6532-4E46-AB16-CD299D1A4EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010910$A951A308-DAF9-47CE-A82D-9581D00B6318","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f9e0d3cf14edf56ad48a93a89f0c519e5ba51852","datavalue":{"value":"5541072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010910$8D61615A-6484-47E8-83D0-FFDC07F93BB2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"542949039064e7bbf24704ea759abb4a18f2a233","datavalue":{"value":"multiplicitx of vertex degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$9B8E0057-2CF0-466E-9BBC-831D95EAF79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b10cff0c23b9f6aa8789d5f16a4c9af5f5c9cb04","datavalue":{"value":"average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$A9474E8A-5CBC-4B7D-B096-1312239A09DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$F462F7A9-15E3-4D12-BE40-6DDE73E5D154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$30D1598A-BF70-438C-83A8-402BC642597D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94695b95e4deaff35ee38f4df4c3c0c319b4104b","datavalue":{"value":"maximal outerplanar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$B184AD46-548D-4D4C-9921-6A47190CBF82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c402bbe4761407be2e036cd2435c81a0fc82915a","datavalue":{"value":"planar triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$81B9B004-4DD4-4D8C-B892-FE9A22CFB0C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06260caf9c0a1940cbfec2e3a3656bd876884ea4","datavalue":{"value":"claw free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$F833D0D3-A23B-45E2-985A-92C7D8072E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4177e024ddd16cfc7043ad285c09cc7dd0eb60de","datavalue":{"value":"line grpahs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010910$C72C96DB-B1F5-461B-8EE0-B302BBA61675","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":"Q1010910$E489A62E-5CDF-4755-91D6-A7FACD260DB1","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"7ef505035fe40de4b0b75f45fe6f9cba727724e2","datavalue":{"value":"bafkreiag52htr5ueodkss5l3h2hzmgfcc2776vjn3nh6pboi3y3im4rqmi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010910$8D9F9176-48C9-4681-AB36-33E2C575C996","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25cf644b107583249e314ac79971f9b0214ec4ca","datavalue":{"value":{"entity-type":"item","numeric-id":2048571,"id":"Q2048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c984f448c7c8fb37c7b709a0a0e6b07b637f35c","datavalue":{"value":{"amount":"+0.8761277198791504","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":"Q1010910$DDA75CA2-AC59-40D9-AF66-45E3AD8B8DE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc2ef645a26b656e236a26d22873cc644732e795","datavalue":{"value":{"entity-type":"item","numeric-id":5460873,"id":"Q5460873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8a7282b0f2fe1524df2d7901bcc7b7c4f998393","datavalue":{"value":{"amount":"+0.7788347601890564","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":"Q1010910$3A0096A1-9EAD-4CCD-888C-5073F3DAD37D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78c9e69d68f335332fbc9075e48460495278aa4f","datavalue":{"value":{"entity-type":"item","numeric-id":2305934,"id":"Q2305934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a27a2715fc2c49c770ef282a8d84e0b0c523177","datavalue":{"value":{"amount":"+0.7775311470031738","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":"Q1010910$CA0BFBE7-14E5-4AAE-A430-F48F11794E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf0b9bd7700954af0454c628fe8d24a6e9a9ab74","datavalue":{"value":{"entity-type":"item","numeric-id":4355068,"id":"Q4355068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01ae211d0ed7a3f9ea51cbe79e1ae098bac1ba25","datavalue":{"value":{"amount":"+0.7746694684028625","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":"Q1010910$450C84EE-0EFB-413D-9089-AB16E67F5D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dae2c0287d96ce363e2389a2e1218d6318df60cd","datavalue":{"value":{"entity-type":"item","numeric-id":405103,"id":"Q405103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3857048703613401227df5a69cfd4695119ffb20","datavalue":{"value":{"amount":"+0.7713804841041565","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":"Q1010910$43B2B6C4-7937-4AF8-BE98-EDBF43697440","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Repetition number of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Repetition_number_of_graphs"}}}}}