{"entities":{"Q510346":{"pageid":512113,"ns":120,"title":"Item:Q510346","lastrevid":77817359,"modified":"2026-05-06T10:07:25Z","type":"item","id":"Q510346","labels":{"en":{"language":"en","value":"Symmetric graphs with respect to graph entropy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6686282"}},"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":"Q510346$ECFD301D-7B00-49D8-A021-1F21C339F2FF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d3e921a95a6e9d26618174453cfec9c0a77b5894","datavalue":{"value":{"text":"Symmetric graphs with respect to graph entropy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q510346$8A08AF49-239F-402C-954A-621197484A27","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a692e34390c9f3b286ef894ea88f9c46c4c9ccb0","datavalue":{"value":"1355.05114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510346$48BF7783-31A7-4260-88D2-55D8E5B57F4A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f0b3ffc15c1934b0092b8f326c0a3189e78bf0ff","datavalue":{"value":{"entity-type":"item","numeric-id":510344,"id":"Q510344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$39B47CC4-FAF3-47B0-A3E9-3B6E697982D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fe38f629716644acdb439cce6e5e579246c130c","datavalue":{"value":{"entity-type":"item","numeric-id":510345,"id":"Q510345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$3C0E7403-C9EA-46A8-931D-5EAE9D9D9CCE","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":"Q510346$9F43A1D9-EEC0-4B89-B1BD-467F1AC57A12","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a051f678ce9f4f7380cf2de9c6018ea50fabc5c","datavalue":{"value":{"time":"+2017-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q510346$BC554C65-E8B5-4F8E-A71C-343E385B63B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"025ddb03635fcc03005b87e3ef161b4b807ef167","datavalue":{"value":"https://arxiv.org/abs/1510.01415","type":"string"},"datatype":"url"},"type":"statement","id":"Q510346$35DC77B0-CCA8-445C-A76C-AB4301039AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"2018b01deee84323d49d96404bed82c34de45751","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p29","type":"string"},"datatype":"url"},"type":"statement","id":"Q510346$F6BA7C2A-3359-4B7A-BA8B-F8B3DF2EF719","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"217a54f2cb1af01f0516713a56f3c8b7f3a341cd","datavalue":{"value":"Summary: Let \\(F_G(P)\\) be a functional defined on the set of all the probability distributions on the vertex set of a graph \\(G\\). We say that \\(G\\) is symmetric with respect to \\(F_G(P)\\) if the uniform distribution on \\(V(G)\\) maximizes \\(F_G(P)\\). Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we characterize all graphs which are symmetric with respect to graph entropy. We show that a graph is symmetric with respect to graph entropy if and only if its vertex set can be uniformly covered by its maximum size independent sets. This is also equivalent to saying that the fractional chromatic number of \\(G\\), \\(\\chi_f(G)\\), is equal to \\(\\frac{n}{\\alpha(G)}\\), where \\(n = |V(G)|\\) and \\(\\alpha(G)\\) is the independence number of \\(G\\). Furthermore, given any strictly positive probability distribution \\(P\\) on the vertex set of a graph \\(G\\), we show that \\(P\\) is a maximizer of the entropy of graph \\(G\\) if and only if its vertex set can be uniformly covered by its maximum weighted independent sets. We also show that the problem of deciding if a graph is symmetric with respect to graph entropy, where the weight of the vertices is given by probability distribution \\(P\\), is co-NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q510346$8EF4FE80-7017-4FBF-9924-F84ED5660125","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510346$0B3FE863-3BD0-49B7-936B-6C63DC6E6F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510346$63132FF3-27A2-41B6-A336-9B482A6980E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b2773d305bb22ed635d748bc939993c6750608ab","datavalue":{"value":"05C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510346$9A0E82A7-B6F0-4EAA-A801-872351CA3C35","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c50238c776cfe76a03800fa76a10d05182135fdc","datavalue":{"value":"6686282","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510346$F94F28AA-F876-4A33-BDDF-39C1B2F8A2E4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53e4d6781b233a5e23f1d342d16da9b28d1014bb","datavalue":{"value":"graph entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q510346$0B440F97-E7DD-487D-BD30-C97E384A9B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"637872e1bd0dd812655871ae455bcab7bf55fd2b","datavalue":{"value":"fractional chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q510346$AA29B63D-D99D-48A0-871B-F8EACB42CF2C","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":"Q510346$175F54F6-1A56-4DEE-8F4C-A37042C89504","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"819fd2d23ce5d83c867c22358ef2afb90598ab5c","datavalue":{"value":{"entity-type":"item","numeric-id":898092,"id":"Q898092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$A547E8B0-CE73-41C7-89EE-2EF5B9976BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0b2ce3f8d8de10e2796c77ee20629890b421e45","datavalue":{"value":{"entity-type":"item","numeric-id":810528,"id":"Q810528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$09EB3989-C56B-451E-A550-06252D9CFF01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49c68f48b66d4d04696fdb7856ffc7754b328bdb","datavalue":{"value":{"entity-type":"item","numeric-id":3038628,"id":"Q3038628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$F99C7C3B-670F-46C8-A9E2-86A67DCF6162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d27dacc5c86087ff2495c99b8279b01d00250f","datavalue":{"value":{"entity-type":"item","numeric-id":2716030,"id":"Q2716030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$57F82017-A696-48B5-B18B-5B162D8B9666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c53b8d116e8b0316b6acb30c6f5566a6b3df1c3e","datavalue":{"value":{"entity-type":"item","numeric-id":1584259,"id":"Q1584259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$1B253A95-DAA2-47F8-90FD-49D943D9E2F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34018e0596996ff05bb65cc90b8bc3b77ba0da66","datavalue":{"value":{"entity-type":"item","numeric-id":4053473,"id":"Q4053473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$CAE993DB-4187-42CB-AF77-93B7C0822050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b160f68a987433ec6756c19b5344c313602ae4e8","datavalue":{"value":{"entity-type":"item","numeric-id":4777339,"id":"Q4777339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$CDFB4808-7B6B-4A5E-BECC-F1015317F733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fe1f566242e8ecf1db61864069dff52b7764a7f","datavalue":{"value":{"entity-type":"item","numeric-id":3739153,"id":"Q3739153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$35C3833E-4DE1-43A2-978A-C229B9A3E67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9252987cdeaddd0d5f71af23ae55fc6572407756","datavalue":{"value":{"entity-type":"item","numeric-id":4404779,"id":"Q4404779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$F2C0E7A4-4CA9-4411-B577-BB859EF8DD5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54bb4c2777cd467560e702eb291b1b40429f95f8","datavalue":{"value":{"entity-type":"item","numeric-id":1196687,"id":"Q1196687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$50A29F5A-0255-4F9D-A826-3D87491ED1BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf98203816cb1470684b1e7747ede6d410d21620","datavalue":{"value":{"entity-type":"item","numeric-id":3033797,"id":"Q3033797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$FD1E7FA2-858C-473D-A3A7-25D9A9E19A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8bb76ae1194dedb64116e06f554f5ce7ef43f34","datavalue":{"value":{"entity-type":"item","numeric-id":1122979,"id":"Q1122979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$9AF9E854-7C05-42B3-955E-8EA632FDF0C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efd1e75117190f93cf858396ac9b916262b9ecdb","datavalue":{"value":{"entity-type":"item","numeric-id":4840778,"id":"Q4840778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$16F76810-C321-4EA3-8267-483A5DF5B8E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcfb3a9771a46f2b7990e15d9e5eca98c3dea962","datavalue":{"value":{"entity-type":"item","numeric-id":2758342,"id":"Q2758342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$6BE00C37-ADF3-4C91-8CAD-2E612980F8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1863d37c8bc914a0a0f094e7c9767fdd7017d055","datavalue":{"value":{"entity-type":"item","numeric-id":4897434,"id":"Q4897434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510346$FE14BDD8-67AD-4874-9AE7-C1E64335E839","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"09fd3b2deed4bdb1cb61f409d0f47af25c3d351b","datavalue":{"value":"bafkreiewj44k6lsb6c3b2igwwbse7r4skepx3dfgxpp6w6vfwt56w5wncu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510346$E3B53BF7-83DD-4BD8-B6A8-9B6830956D69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11b65f8a85004271554cfde318c010f7d8c00e66","datavalue":{"value":{"entity-type":"item","numeric-id":898092,"id":"Q898092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af61daef5c57a0c2a7bb754b9f8cb0cdcbd141bc","datavalue":{"value":{"amount":"+0.9150684475898744","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":"Q510346$95912C1F-EEF8-4496-9B0E-3CB976616992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b88af853a8aee54211442a2ad9ecaed7b9ea1e59","datavalue":{"value":{"entity-type":"item","numeric-id":1584259,"id":"Q1584259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24cc3002ebb80d77f8f36e6be3b87da0aae40e0e","datavalue":{"value":{"amount":"+0.7579931020736694","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":"Q510346$75171674-584C-4871-A86B-2FAF942E040B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d323f45bf24368937168867ca9e59836cbe9f250","datavalue":{"value":{"entity-type":"item","numeric-id":2758342,"id":"Q2758342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24cc3002ebb80d77f8f36e6be3b87da0aae40e0e","datavalue":{"value":{"amount":"+0.7579931020736694","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":"Q510346$8CC5C523-2F9A-404C-B008-3FCD4D486719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2540492d2ab4fe17ad4c75a2e5d17e39a4773d57","datavalue":{"value":{"entity-type":"item","numeric-id":4840778,"id":"Q4840778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9468a982d97099493d481038272cc382f76963da","datavalue":{"value":{"amount":"+0.7497097849845886","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":"Q510346$75624C14-E102-4485-BDDA-ABC05B2B186B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d1fe729797977d7581ee9a39f562cf76f15555","datavalue":{"value":{"entity-type":"item","numeric-id":3033797,"id":"Q3033797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15e4b69cac17b6fee43f61c81a377ca747fdf9a9","datavalue":{"value":{"amount":"+0.747442364692688","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":"Q510346$FB86953D-D591-4299-A009-F2A1700F8DB7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Symmetric graphs with respect to graph entropy","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Symmetric_graphs_with_respect_to_graph_entropy"}}}}}