{"entities":{"Q2185229":{"pageid":2195972,"ns":120,"title":"Item:Q2185229","lastrevid":57776244,"modified":"2026-04-02T11:53:14Z","type":"item","id":"Q2185229","labels":{"en":{"language":"en","value":"Homomorphisms into loop-threshold graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7208436"}},"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":"Q2185229$EF9BD23D-531D-4F23-AC91-96CF4872F88E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a74ca75de53a9ca4fb9a71e5ae4da34a6c6f7c01","datavalue":{"value":{"text":"Homomorphisms into loop-threshold graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2185229$78BC4C73-0742-4E8D-9F1C-CB566DC5C2E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a9aca9c431fe9fd330a82896a802a561149f7f2","datavalue":{"value":"1441.05120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$2FF6024B-F290-483B-949F-F1F49ECD995A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"48379a4f9adace676af408a07a1146aa27e3a77b","datavalue":{"value":"10.37236/6207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$BD804722-15DB-490F-ACDE-64313C8666FF","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":"Q2185229$E96B96C8-5FA9-466D-8C56-DD59A4619503","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"84fdf3ed3ab7383ca4f016ac37ce5ef0ef7cb738","datavalue":{"value":{"time":"+2020-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2185229$25C26DE9-22A4-4BB7-8554-61C736022426","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92dc30d4dd3006a040e18615c13b5571717640d7","datavalue":{"value":"https://arxiv.org/abs/1606.02660","type":"string"},"datatype":"url"},"type":"statement","id":"Q2185229$47037AF7-DD90-4488-8035-669C13CE498A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"931e1e9f75c40ac3fda20499d0d7dd1c114fac9d","datavalue":{"value":"Summary: Many problems in extremal graph theory correspond to questions involving homomorphisms into a fixed image graph. Recently, there has been interest in maximizing the number of homomorphisms from graphs with a fixed number of vertices and edges into small image graphs. For the image graph \\(H_{\\text{ind}} \\), the graph on two adjacent vertices, one of which is looped, each homomorphism from \\(G\\) to \\(H_{\\text{ind}}\\) corresponds to an independent set in \\(G\\). It follows from the Kruskal-Katona theorem that the number of homomorphisms to \\(H_{\\text{ind}}\\) is maximized by the lex graph, whose edges form an initial segment of the lex order.  A loop-threshold graph is a graph built recursively from a single vertex, which may be looped or unlooped, by successively adding either a looped dominating vertex or an unlooped isolated vertex at each stage. Thus, the graph \\(H_{\\text{ind}}\\) is a loop-threshold graph. We survey known results for maximizing the number of homomorphisms into small loop-threshold image graphs. The only extremal homomorphism problem with a loop-threshold image graph on at most three vertices not yet solved is \\(H_{\\text{ind}}\\cup E_1\\), where extremal graphs are the union of a lex graph and an empty graph. The only question that remains is the size of the lex component of the extremal graph. While we cannot give an exact answer for every number of vertices and edges, we establish the significance of and give bounds on \\(\\ell(m)\\), the number of vertices in the lex component of the extremal graph with \\(m\\) edges and at least \\(m+1\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185229$35E4A3A3-6B86-4902-972A-EBBC879C3B83","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$7E63AB9B-9BC8-49AC-BCF4-9693863A5B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$1F6C4791-3AB4-4B35-95E5-85E10BF15FD4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a6272be45b70da1bade0d333e8df174b2b12f5c","datavalue":{"value":"7208436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$AFC8A84C-2E7C-4520-A8DB-DDAB0AE4C23F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"876a2e05e69b57cca591faf7a0ea5fd04eda99e3","datavalue":{"value":"homomorphisms into a fixed image graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185229$A2720CA6-86A1-4297-8883-9AF2A31A7094","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab5a422918621b46149cf3b2991e66a46628e6cf","datavalue":{"value":{"entity-type":"item","numeric-id":271642,"id":"Q271642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$7E812157-0FDB-4FEA-935D-600E1C54B740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1b59ffef3369def057adeb9a916517ae7c7cfd55","datavalue":{"value":{"entity-type":"item","numeric-id":1659604,"id":"Q1659604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$10AA1140-5B5B-4173-BD3F-7C6B94040821","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":"Q2185229$59D90B72-FE14-46C3-9A9F-40394CE3EBAD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7f6e1b1241a84496d0a1392e5e9395a84979a6ff","datavalue":{"value":"W3030445364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$7B9A2A81-39A7-4628-9418-D6303C7A1A7C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"397ce419aa25b31a1e357d79143a79b25a87a4f6","datavalue":{"value":{"entity-type":"item","numeric-id":456377,"id":"Q456377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$7A4E4476-E988-4472-8185-66CF99A826D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"491820c8ea9091f5329d6867a580f860d82e051f","datavalue":{"value":{"entity-type":"item","numeric-id":3466354,"id":"Q3466354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$D9CCFA09-C9F2-4279-9A32-86CB34A869C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f19a42cbed0db742cf2f9f2331d8945ae27f8ae2","datavalue":{"value":{"entity-type":"item","numeric-id":1569058,"id":"Q1569058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$D1D22FDE-1735-47E5-81FC-1E0AF1F93DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c42399b7fac0541e4112b6e670bf60bcb3a44c8","datavalue":{"value":{"entity-type":"item","numeric-id":5199417,"id":"Q5199417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$E81B16D5-FE16-4029-9B9C-4A75D53F71F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"964275d916d9aed11d331ee2d1047080c9bb947f","datavalue":{"value":{"entity-type":"item","numeric-id":640424,"id":"Q640424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$778DCDC0-5C44-4BD3-8CB3-6391AB3E4905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69d1069848f5f0516019f837a53399852185535a","datavalue":{"value":{"entity-type":"item","numeric-id":5418768,"id":"Q5418768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$92E3DED0-2A45-4895-848B-9930354D0C0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"235da5ac8aac1351868f7bf0abdc5cb1cb444b67","datavalue":{"value":{"entity-type":"item","numeric-id":2434716,"id":"Q2434716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$1391958B-0132-4BE2-8E8E-63F0ACCF7CA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1be2a7edc683762cffd43359667df7a5b577da6","datavalue":{"value":{"entity-type":"item","numeric-id":2958203,"id":"Q2958203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$BAE9D19A-BA39-4E0D-A5E0-AB5EEDFA1CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d8823510636b495d513ffe6e509a953d1c525b4","datavalue":{"value":{"entity-type":"item","numeric-id":5418775,"id":"Q5418775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$2177F011-04EA-4FE3-A6BD-FDB0092855BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea260a70990969e22235b5c261b9408d3ceee7aa","datavalue":{"value":{"entity-type":"item","numeric-id":641174,"id":"Q641174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$70B603F0-FF24-4410-97D7-EDCB3D8B0081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba1f7859275e8b348adac71afb681462b8fb5c52","datavalue":{"value":{"entity-type":"item","numeric-id":4920651,"id":"Q4920651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$76CB634F-A5CD-469A-88B0-91F1897BF6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf348ad9cc5a34d177f1d877dc3b6db66c2b2cf","datavalue":{"value":{"entity-type":"item","numeric-id":4660722,"id":"Q4660722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$5DDC7881-3D77-4084-BBAC-2235325161F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c7d878a45416c94e8126496072474ae49debf8f","datavalue":{"value":{"entity-type":"item","numeric-id":5364240,"id":"Q5364240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$E71DD81D-99FD-4595-9A43-54D15C620DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e8e8430cb9ed877eebc0187316c8bc2a60dce5","datavalue":{"value":{"entity-type":"item","numeric-id":2731583,"id":"Q2731583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$916BB23A-8634-45B8-A5DF-1A115BDC6943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d96fe1377adf4bc2473cc2c298e11ba7b240673b","datavalue":{"value":{"entity-type":"item","numeric-id":4071752,"id":"Q4071752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$A2B4C6C5-08A5-456C-9C0D-186C6A72E7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f452cfc46c61b9aec3f0c92cdf87b0bd8c84f73","datavalue":{"value":{"entity-type":"item","numeric-id":5726070,"id":"Q5726070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$ED77BC1F-212F-428A-B976-4F28BFECB7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d1d5524b91a030cb506c147be19b598758c8009","datavalue":{"value":{"entity-type":"item","numeric-id":1899209,"id":"Q1899209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$E272FA72-ED41-41B3-A69A-16818286F597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6354243434d10765dadd5cc5769af155849b34dd","datavalue":{"value":{"entity-type":"item","numeric-id":995772,"id":"Q995772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$E8ADB06D-A7FB-4ABE-8B35-B614799CB082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e822d011535eb197a82f8a9a0935d7837c54415","datavalue":{"value":{"entity-type":"item","numeric-id":3557538,"id":"Q3557538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$A05763AE-B987-4176-839E-8679D32378CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3590a5e53014145490c65a01802af7fd97ee1884","datavalue":{"value":{"entity-type":"item","numeric-id":4575432,"id":"Q4575432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$9D300D9F-B28B-4B99-B5F4-E91FB5AD0982","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d2468f4022788651f088906a6303b562b7a1a149","datavalue":{"value":"bafkreickgcbdrum2lhfvvngiokrqgxuedi2q3qso3oyow2rj6qjupuxxsa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185229$77DABBE3-3DF9-4E8B-8E79-CEECC49FA41A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e05029f28240ef64819e99c7c176ab86065e4c9","datavalue":{"value":{"entity-type":"item","numeric-id":5199417,"id":"Q5199417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47bc47181ca2b22af5ec055936634b88e07d7161","datavalue":{"value":{"amount":"+0.9031221866607666","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":"Q2185229$E4BD6EA8-35DE-4827-B175-F119136E2F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64189c9c4d049dc2e903c0aa183613baf564b8de","datavalue":{"value":{"entity-type":"item","numeric-id":5418768,"id":"Q5418768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0efa74b1e054129d3a86bcb8bd5d4620e0a84d51","datavalue":{"value":{"amount":"+0.8895102739334106","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":"Q2185229$56455E82-5184-4E12-A6EC-556CE7E2EBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23617051ed81bb45ea6708f64e38190573541282","datavalue":{"value":{"entity-type":"item","numeric-id":1756116,"id":"Q1756116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d6c24aed48e7b6b931df0d996ac2e0169cb64a5","datavalue":{"value":{"amount":"+0.7533447742462158","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":"Q2185229$F4F47C4D-0197-4BC4-B348-23D2BAD03478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b30552234855aa0fdb65eaa300ce2114f73e58","datavalue":{"value":{"entity-type":"item","numeric-id":4575432,"id":"Q4575432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc79cf067d87021ac2d3d8c15389ee748c5be0c6","datavalue":{"value":{"amount":"+0.7439600229263306","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":"Q2185229$A391D393-F0FE-4751-8CA1-8B46414DF648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13824194b1be9055616d8464c091bf72190052da","datavalue":{"value":{"entity-type":"item","numeric-id":5251205,"id":"Q5251205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"081592d565197f28716c24bb7dbe50e772720823","datavalue":{"value":{"amount":"+0.7330340147018433","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":"Q2185229$ECC2E841-B2E2-41A9-8893-2906E2E609DC","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185229$49F7C0FD-0B07-49B1-ADFF-6F3B93AAB57E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2185229","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2185229"}}}}}