{"entities":{"Q1613456":{"pageid":1624196,"ns":120,"title":"Item:Q1613456","lastrevid":72342915,"modified":"2026-04-14T04:15:50Z","type":"item","id":"Q1613456","labels":{"en":{"language":"en","value":"Graphs satisfying inequality \\(\\theta(G^2) \\leq \\theta(G)\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792388"}},"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":"Q1613456$50FA305E-696D-4863-84F4-CED954D5A893","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b430a101c5d431ee88f5c3877f39298ebde6a71","datavalue":{"value":{"text":"Graphs satisfying inequality \\(\\theta(G^2) \\leq \\theta(G)\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613456$65335714-2340-4A17-9847-25F2420A9D95","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e075f6f30a5efe590c14c5e26e293b7dbb0c2178","datavalue":{"value":"1007.05078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613456$6E9C3A91-F88F-4C84-AA39-AC9C9724021E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b44799216075d459f583a0b750c0e98b5a2e08c0","datavalue":{"value":"10.1016/S0012-365X(01)00423-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613456$B8432CCE-050C-4BCC-B9FF-02EA7925612F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0773d061fd21812ffedb20167cb17d9330bb172","datavalue":{"value":{"entity-type":"item","numeric-id":1613454,"id":"Q1613454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613456$98AAE987-CCF9-40A0-998D-3F11A1ABADD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a14fc2cb2776d88f8064014c705ec86962d9c1a4","datavalue":{"value":{"entity-type":"item","numeric-id":209045,"id":"Q209045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613456$22E1B01F-D7CE-4EB0-86F6-8DD51616C647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ca286c63652ce51e99eea34a8cf18c80e58d370","datavalue":{"value":{"entity-type":"item","numeric-id":1613455,"id":"Q1613455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613456$7D80B6E1-8FC1-482C-A8DD-12053219EFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a241874cdab558394c3806d25083b628915834e","datavalue":{"value":{"entity-type":"item","numeric-id":209047,"id":"Q209047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613456$E0A3F6D4-8078-4DC0-A8EC-ED1315338D4B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613456$E91D1503-7FF7-4C41-8039-560F95F9F617","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613456$F8C967B0-FB3A-4E5A-BA22-E4DFE29A75DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f6f0b2624ae24189a9655731b9be87994c6cb6c","datavalue":{"value":"An edge clique cover of a graph \\(G\\) is a collection of cliques that include all edges of \\(G\\). Denote by \\(\\theta(G)\\) the smallest number of cliques that form an edge clique cover of \\(G\\). The authors study the relationship between \\(\\theta (G)\\) and \\(\\theta(G^2)\\), where \\(G^2\\) denotes the square of \\(G\\), i.e. the graph obtained from \\(G\\) by adding edges joining vertices \\(u\\) and \\(v\\) whenever the distance between \\(u\\) and \\(v\\) in \\(G\\) is 2. The main results of the paper are: If \\(G\\) is a connected graph with \\(n\\) vertices and \\(\\theta (G)\\geq n\\), then \\(\\theta(G^2)\\leq \\theta(G)\\). If \\(G\\) is a connected chordal graph with \\(n\\) vertices such that \\(\\theta(G)\\) is equal to \\(n-1\\) or \\(n-2\\), then \\(\\theta(G^2)\\leq\\theta(G)\\). If \\(T\\) is a tree with \\(n\\) vertices, \\(n\\geq 3\\), and \\(m\\) is the number of leaves in \\(T\\), then \\(\\theta(T^2)=n-m\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613456$8CEACED0-5F35-4FB5-9B70-C9AC18F27129","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613456$5DD91B88-A9CD-45BE-A547-4D5169BA4FB9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613456$4FB8CFD0-A35D-48A8-B116-2F36DA7963C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613456$ED685A2A-9467-412D-AB02-005BB978E45C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5b9bc3cbfde3e7b1fb043311722d78b35e0a469b","datavalue":{"value":"1792388","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613456$41F6B080-5723-48DA-AC15-64D79D038D0F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94a797f3335033b70a78d737d840f60eee03751c","datavalue":{"value":"edge clique cover number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613456$2B9D084A-534D-40E5-88CB-6D6E097C7EE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88efe65d6c26a7e23f90db896a1413e2be9d5d57","datavalue":{"value":"the square of a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613456$054BE13E-26F0-48DD-93F6-256CD0897D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613456$7A0D343E-C7ED-43DD-8730-9076D187828A","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":"Q1613456$23B8DE64-F536-4D9B-B52D-07D004747445","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c063947851b5bfdb15b29c963932be0cc2746b3","datavalue":{"value":{"entity-type":"item","numeric-id":2495511,"id":"Q2495511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0da094d116a195c349ef788faca1df684942f78","datavalue":{"value":{"amount":"+0.868141233921051","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":"Q1613456$DE30710A-BEF2-433A-9189-72B83AF2F369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2e77b6a64615473518971f7c037cc35ec1636ad","datavalue":{"value":{"entity-type":"item","numeric-id":1100482,"id":"Q1100482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da739d59ec46333456a9a56678c4cf04a2a1c28e","datavalue":{"value":{"amount":"+0.7756265997886658","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":"Q1613456$FB40391D-9FFA-4736-990F-907B73AEBD8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9f26ba5f800b5710ef129e9e4de6d5d27db1368","datavalue":{"value":{"entity-type":"item","numeric-id":4629999,"id":"Q4629999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdf2ecb6b4ad6d679013cae3d091728df09f4f99","datavalue":{"value":{"amount":"+0.7729012966156006","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":"Q1613456$A9712785-94BD-4C9A-B42C-31D99636AF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e151fc20bd335e957c53ee5e48b7a13c8abfba39","datavalue":{"value":{"entity-type":"item","numeric-id":6055943,"id":"Q6055943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bc2e41fde964b1731f3014318605fce83d8bca3","datavalue":{"value":{"amount":"+0.7653012275695801","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":"Q1613456$76290E76-D57E-45E7-939E-06315C8D187E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74a7f94c2c5450f07dac9106da94a08250e1670d","datavalue":{"value":{"entity-type":"item","numeric-id":3313890,"id":"Q3313890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9045d36cc9b15be49eb4efc5a2d66fb2c1e3308","datavalue":{"value":{"amount":"+0.7642114162445068","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":"Q1613456$6F174C36-6DC5-40C7-B5D2-C447B5BB56C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs satisfying inequality \\(\\theta(G^2) \\leq \\theta(G)\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_satisfying_inequality_%5C(%5Ctheta(G%5E2)_%5Cleq_%5Ctheta(G)%5C)"}}}}}