{"entities":{"Q888591":{"pageid":890439,"ns":120,"title":"Item:Q888591","lastrevid":65140629,"modified":"2026-04-12T00:34:52Z","type":"item","id":"Q888591","labels":{"en":{"language":"en","value":"Generalized line graphs: Cartesian products and complexity of recognition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6502776"}},"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":"Q888591$36088535-6D0A-4C1F-9728-D38D89AE9210","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"564f4fa09ca9052a06533bd57f412cc1efbe9afa","datavalue":{"value":{"text":"Generalized line graphs: Cartesian products and complexity of recognition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q888591$178383AE-FB4A-4ECF-A54F-ABA2EE7A3776","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9229df9aa8f33b61a037fa8deab111efefca0a4a","datavalue":{"value":"1323.05109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888591$FB01D147-5765-4967-B05D-A6DAE923F9EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2be6c21d40ccd98953a049b3dfa892b383be34ed","datavalue":{"value":{"entity-type":"item","numeric-id":298986,"id":"Q298986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$87B52F35-21E9-4BE6-8622-C8409C95BED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa696e5ef25763a69354b976bf97c62b1e59544c","datavalue":{"value":{"entity-type":"item","numeric-id":279226,"id":"Q279226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$FF64E79E-47DB-48C4-A2D1-BB25A7A8F2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$F20583C6-009A-4299-BC9E-6BD025764607","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":"Q888591$4554914E-CAFE-4045-81EF-00637757D430","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"49c905baf0f1483cbda0527efa721826b9ca8c8f","datavalue":{"value":{"time":"+2015-11-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q888591$ADD5EAAB-3E4F-4068-8AB8-95796BF6B961","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd6feaa2c855b001dc916e549381d2f94823aa79","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p33","type":"string"},"datatype":"url"},"type":"statement","id":"Q888591$25AC08DC-FDF4-4EC5-91F4-6F8E1ABA7F4B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44c77e176083e6896c35c0fdada6eca062ee148b","datavalue":{"value":"Summary: Putting the concept of line graph in a more general setting, for a positive integer \\(k\\), the \\(k\\)-line graph \\(L_k(G)\\) of a graph \\(G\\) has the \\(K_k\\)-subgraphs of \\(G\\) as its vertices, and two vertices of \\(L_k(G)\\) are adjacent if the corresponding copies of \\(K_k\\) in \\(G\\) share \\(k-1\\) vertices. Then, 2-line graph is just the line graph in usual sense, whilst 3-line graph is also known as triangle graph. The \\(k\\)-anti-Gallai graph \\(\\triangle_k(G)\\) of \\(G\\) is a specified subgraph of \\(L_k(G)\\) in which two vertices are adjacent if the corresponding two \\(K_k\\)-subgraphs are contained in a common \\(K_{k+1}\\)-subgraph in \\(G\\).{  }We give a unified characterization for nontrivial connected graphs \\(G\\) and \\(F\\) such that the Cartesian product \\(G\\square F\\) is a \\(k\\)-line graph. In particular for \\(k=3\\), this answers the question of \\textit{J. Bagga} [Int. J. Math. Math. Sci. 2004, No. 29--32, 1509--1521 (2004; Zbl 1061.05078)], yielding the necessary and sufficient condition that \\(G\\) is the line graph of a triangle-free graph and \\(F\\) is a complete graph (or vice versa). We show that for any \\(k\\geq 3\\), the \\(k\\)-line graph of a connected graph \\(G\\) is isomorphic to the line graph of \\(G\\) if and only if \\(G=K_{k+2}\\). Furthermore, we prove that the recognition problem of \\(k\\)-line graphs and that of \\(k\\)-anti-Gallai graphs are NP-complete for each \\(k\\geq 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q888591$6C7EE5DD-F2E4-456B-99E8-421F84DF30C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888591$B238AFB1-7BDF-4857-9239-99170D164C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888591$6396B915-8E60-4795-8EE5-EE8B14C85AFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888591$E4B4515C-4FFA-4E4F-84D7-A6AB12E7F2A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"49188c049520a66c0b26e098825729c51e5c6182","datavalue":{"value":"6502776","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888591$ECEE65DD-C226-4381-BBF0-A27D9D0BAEF5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b57286b5c048239e4c64604e166115d54d39bf6","datavalue":{"value":"triangle graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q888591$628805A3-8433-4B56-B595-A19C686D1067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55a7279bf717f64677911022e3b8d65e18914fba","datavalue":{"value":"\\(k\\)-line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q888591$444A23A1-7878-44E8-8928-7D1660483024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fc7c05fe22c0b0e512b2491fdf2973dc3bd1c2a","datavalue":{"value":"anti-Gallai graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q888591$A0E19B87-BA45-4870-BAF3-A5F1F890D470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ad68fb8f92e2f2e8cca9daf204f10053137e539","datavalue":{"value":"Cartesian product graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q888591$44A85EF2-DA5B-4D54-B0A4-2E17E5A0636D","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":"Q888591$731D3182-011E-40D0-BD60-8575FA683598","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"75339080179f6a5228a5e09ed3e181fba139b008","datavalue":{"value":{"entity-type":"item","numeric-id":2275916,"id":"Q2275916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$6B5A25EE-73F3-468B-B6B2-2DCC107453DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a6872ac601723d7c225d3fd0a184a15390eb3a5","datavalue":{"value":{"entity-type":"item","numeric-id":442382,"id":"Q442382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$80A5234E-AD8D-40CA-9A3B-3BB6040FAEA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5d24c642644d57e63acb85a8eb82e903c1e5d02","datavalue":{"value":{"entity-type":"item","numeric-id":1926043,"id":"Q1926043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$B5676346-C054-4206-B399-B6DCE2680D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b5c8e2648f313bdca47a92b4c396d0c5efa494","datavalue":{"value":{"entity-type":"item","numeric-id":3617906,"id":"Q3617906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$55A4DCD7-D9E3-4ECB-A225-32DD5C6011C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8441974b945556340a513a6bc8cba251ab5a9ea8","datavalue":{"value":{"entity-type":"item","numeric-id":1774770,"id":"Q1774770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$3B66C9A6-1CAE-4614-B994-C3F6303AF390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f63e38e4851ca0e3a13042d4f415c0b9fe4f5434","datavalue":{"value":{"entity-type":"item","numeric-id":5601346,"id":"Q5601346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$0B9EBEEA-A70D-45E3-B811-D1737949F1C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4994190b45c92d2283f1bee86b7a0b36b905564d","datavalue":{"value":{"entity-type":"item","numeric-id":1070249,"id":"Q1070249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$450D5A32-E156-4681-8338-90938AA0C2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60e3d166c1330cdd5edcd2ea7168986b05993d0d","datavalue":{"value":{"entity-type":"item","numeric-id":3472137,"id":"Q3472137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$3AD72C89-D9E2-488D-B6D1-DF171EC28837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ac693277545d124f5cede4aad4253cc3ff4188b","datavalue":{"value":{"entity-type":"item","numeric-id":1393416,"id":"Q1393416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$93C123F1-46B9-42CA-9BFE-ED33BE3A714D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e11f22b170738b29adafd91e5ec7f6271a062570","datavalue":{"value":{"entity-type":"item","numeric-id":1356412,"id":"Q1356412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$E7ACE7FD-D252-459F-96B7-51357806D665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$EBA76433-7375-4ED0-B4E2-3CFE6873D4F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34fcd3676a48894111968c6d5852d57308f440f2","datavalue":{"value":{"entity-type":"item","numeric-id":4693345,"id":"Q4693345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$B977CB64-CCE5-4EFC-B0EB-51A65A5C47D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9e7cd57ee07658f24a94eb335717edcb222c7e","datavalue":{"value":{"entity-type":"item","numeric-id":1126196,"id":"Q1126196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$0264FF5C-3FB0-4CF2-ABF9-BA7A70E519E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ad7df6fc66261f0adbf0d71d21cd6218acbb91","datavalue":{"value":{"entity-type":"item","numeric-id":4047571,"id":"Q4047571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$BFE5E879-8319-42B6-AD09-C8D663E12DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c4fa646ae0d19f2c36cdb1afac0c8ca380bdbc7","datavalue":{"value":{"entity-type":"item","numeric-id":4867717,"id":"Q4867717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$16D74F3A-D9F3-47D6-AEB3-0161ED92ECF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"551935769f3a53978c52d86549323035a6d9a21d","datavalue":{"value":{"entity-type":"item","numeric-id":1272535,"id":"Q1272535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$B5E83F8B-EE20-48B2-8100-68D72083C725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a9c646d12d557ede4b6d9ea0171fbcc08e831fe","datavalue":{"value":{"entity-type":"item","numeric-id":2264685,"id":"Q2264685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q888591$8E8B0647-37E6-481A-B9AB-15A6E73B9A27","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c15d37fde4fa1b25b6be521cc54808be1cd69d72","datavalue":{"value":"bafkreifayqaig6c2jjg4t7ml2uc7ywknr3jdfgzkyx5leqxyecvro5vdne","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q888591$06B462EB-4746-420C-B859-92DE6EA05988","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7896c1834f8249fe8255c9f51cde5fe1cf8a314","datavalue":{"value":{"entity-type":"item","numeric-id":4693345,"id":"Q4693345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50cdea4cbb25732d29c8a3b46d9f7abd60440cd5","datavalue":{"value":{"amount":"+0.7827803492546082","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":"Q888591$41F0299E-0133-4059-9B26-7AF013B921A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e9e47697bcfd86ea405bd0e9b00aa07aab3b95b","datavalue":{"value":{"entity-type":"item","numeric-id":3832614,"id":"Q3832614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d14e7c50cf7a7451813cedbc4094d34c1e63490","datavalue":{"value":{"amount":"+0.78150475025177","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":"Q888591$BF79B51E-F54F-4421-AB43-56EC4CE5E897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"903221e511a89b88a16e4ee841e534da6835b7f0","datavalue":{"value":{"entity-type":"item","numeric-id":442382,"id":"Q442382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a46c4db593c128e8737792d0cdfeff5bf574b169","datavalue":{"value":{"amount":"+0.7681775093078613","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":"Q888591$C5D6B277-556E-41FD-AE99-EFF5933FEB1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c67810a9a547af4390968406183d85009214827b","datavalue":{"value":{"entity-type":"item","numeric-id":3125658,"id":"Q3125658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2792afc7894732c499053d6d8316744ace4baf30","datavalue":{"value":{"amount":"+0.7456151843070984","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":"Q888591$96C49021-0C24-4E27-9EE6-71BACF4D3061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"207a42506ae63f3cd5add76275e7bd7cef8258b4","datavalue":{"value":{"entity-type":"item","numeric-id":1334947,"id":"Q1334947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"463d501c6a0d6303382235f6f8b6b983f590d255","datavalue":{"value":{"amount":"+0.7382934093475342","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":"Q888591$8807847A-C11B-485B-98A8-44CBECAFEE17","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized line graphs: Cartesian products and complexity of recognition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_line_graphs:_Cartesian_products_and_complexity_of_recognition"}}}}}