{"entities":{"Q1962042":{"pageid":1972784,"ns":120,"title":"Item:Q1962042","lastrevid":47437267,"modified":"2026-01-01T18:17:02Z","type":"item","id":"Q1962042","labels":{"en":{"language":"en","value":"Recognizing \\(k\\)-path graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395010"}},"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":"Q1962042$55CD89B5-AC90-4B30-A20C-2C4CC74BAEB0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4e344e37244fd96b87b4c8c57b2e19db92bda50","datavalue":{"value":{"text":"Recognizing \\(k\\)-path graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962042$6FFD6150-9E24-4B1A-9767-F31698AC3FB5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"afee0be4037288a1c1752ac31fba3811608e35ee","datavalue":{"value":"0941.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$6F4F4391-60E4-4CA3-ADCE-D5E6805F546F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d173b9219cbe3ab5eb4217b31d2fb1937a49de00","datavalue":{"value":"10.1016/S0166-218X(99)00132-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$C9806166-F3CF-4088-A653-1413D2815D07","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eff762197dd54e00deaa160ce0bb6a3d51702cd3","datavalue":{"value":{"entity-type":"item","numeric-id":178604,"id":"Q178604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$F1D8E28A-5480-48E5-B1D4-28D2B9038C1E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$9F491ABC-EB38-4A79-9A44-9F7DE811544E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2c9151fa0f749bd3123f145d0659353c941f93c","datavalue":{"value":{"time":"+2000-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962042$4D042D37-C0B2-4299-8F1B-7AFD296EDA93","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5acd5bc92474904163b57e718759198bda98a096","datavalue":{"value":"A recognition algorithm for \\(k\\)-path graphs is given for every integer \\(k\\geq 2\\). The \\(k\\)-path graph \\({\\mathfrak P}_k(H)\\) of an undirected graph \\(H\\) has all length-\\(k\\) paths of \\(H\\) as vertices. Two such vertices are adjacent in \\({\\mathfrak P}_k(H)\\) if their union forms a path or cycle of length \\(k+1\\) in \\(H\\), and if the common edges of both paths form a path of length \\(k-1\\). The class of all graphs \\(H\\) where the start vertex \\(x_0\\) of every path \\(x_0,x_1,\\dots, x_t\\) of length less than \\(k\\) has at least two neighbors outside the path be denoted by \\(\\Gamma_k\\). The graph \\({\\mathfrak P}_k'(H)\\) has also all length-\\(k\\) paths of \\(H\\) as vertices, but here two vertices are adjacent whenever the corresponding paths form some length-\\((k+1)\\) path in \\(H\\) (they are called strongly adjacent paths). This means that \\({\\mathfrak P}_k(H)={\\mathfrak P}_k(H)\\) if there is no cycle of length \\(k+1\\) in \\(H\\). Using the notions of a biclique as an inclusion-maximal-induced complete bipartite subgraph and of a polarized graph, the author gives a new characterization of \\(k\\)-graphs (in Theorem 3), which is a necessary and sufficient condition for a given graph \\(G\\) to be equal to \\({\\mathfrak P}_k(H)\\). A polarized graph is defined to be a graph \\(G= (V,E)\\) together with certain sets \\(M_1(x)\\), \\(M_2(x)\\) whose union equals the neighborhood \\(N_G(x)\\), for every \\(x\\in V\\). By this characterization the author finds algorithms for polarized \\({\\mathfrak P}_k\\)- and \\({\\mathfrak P}_k'\\)-graph recognition \\((\\Gamma)\\) and he also explains the advantages of applying polarized graphs (algorithm 1 and algorithm 2). By the application of algorithm 2 the author finds all graphs \\(H\\in\\Gamma\\) such that \\(G={\\mathfrak P}_k(H)\\) for a given \\(G\\) (the \\(k\\)-path graph recognition \\((\\Gamma)\\) which is described by algorithm 3), and he proves that algorithm 3 is correct (in the \\(\\Gamma= \\Gamma_k\\)-variant, the running time is \\(O(|V|^4)\\), and there is at most one such \\(H\\in\\Gamma_k\\)). Finally, by algorithm 4, the problem to find all pairs \\(k\\geq 2\\) and \\(H\\in\\Gamma_k\\) for a given graph \\(G\\) such that \\(G={\\mathfrak P}_k(H)\\) is treated, and it is shown that algorithm 4 is correct with running time \\(O(|V|^4)\\) (Theorem 11). And in this way also an extension of a known uniqueness result is obtained (Theorem 12).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962042$6802604E-03BB-4780-8C71-BF108BA4296D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$11CC9D27-0BC8-4AE2-A1DE-0476B41ABFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$9CD82E06-E9C7-49B8-B8C0-2B0FE13FA36A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$415B5606-D87A-47F9-BCA1-583C4485BD97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$49E7620E-85F3-4FAD-866C-1B6CAC0BC5D0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b43ec138e82473278109ec53cd7e61724d8e037a","datavalue":{"value":"1395010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962042$50C7684D-6998-4A30-9AF7-D9B60C3EACBD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962042$935F1EAB-FDC2-4E11-B153-8841827FF584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"840cfc080003a12db98cd42dcb22f1513a666bcd","datavalue":{"value":"\\(k\\)-path graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962042$CD4C40B8-D646-46A5-AF71-A487F298B5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962042$D4662B09-8CD4-4C53-9D24-7B6B6096869B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbe7772041fed9d4e9da3ed55b7821bc4ddc24e3","datavalue":{"value":"polarized graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962042$A4FA2B42-4E0E-4FCB-BCEA-A3E63F556A78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bbb1088043ab5fbf02685384cb2a3ae983be6eb","datavalue":{"value":"graph recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962042$9EA55328-52AC-4585-96D9-6ED380715F63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$BC0AA367-8AE1-4CD2-957C-889A7A884170","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":"Q1962042$4BD359BA-97E0-466F-A605-AEEBA26BE428","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a2ba823f9a8ad83a6304036a6fb9fb911050c46","datavalue":{"value":{"entity-type":"item","numeric-id":4355070,"id":"Q4355070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$99CAD2F3-B25C-4CC9-929C-D9144495026E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea5a15848bdf43c92b62193740fbfa899317211f","datavalue":{"value":{"entity-type":"item","numeric-id":3832614,"id":"Q3832614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$EBA96856-064A-4556-9734-3FF597F6A94D","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":"Q1962042$58E849F0-E8D0-464D-BB57-F6F52FC370BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb692daa0e299b2649093d915f749eb10c41db2d","datavalue":{"value":{"entity-type":"item","numeric-id":4862112,"id":"Q4862112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$A2B71E0B-20E0-4E20-A771-042F2189D07C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c17052c65f7fe1d77b1cab9e8238414349692ac","datavalue":{"value":{"entity-type":"item","numeric-id":3137761,"id":"Q3137761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$397034DE-B620-4CF3-B097-C840DBBA2F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2e5a5b964e58a4c1b445c047d7344e912592d3d","datavalue":{"value":{"entity-type":"item","numeric-id":5932702,"id":"Q5932702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$B4C2D83B-7A0A-4882-9A22-24067C0C776B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7a5e61c140f53f63655fe2f128f05bb22d6abc2","datavalue":{"value":{"entity-type":"item","numeric-id":4373687,"id":"Q4373687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962042$6669FBFC-5171-4D34-9912-C24472165EA9","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":"Q1962042$022C2B0C-93B9-497A-86D3-F4169E9A9182","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":"Q1962042$7B7FCB6F-2D88-4FCE-B436-F62400E94D4D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad646a5146560c8e868837e9fc6d63cbc9092167","datavalue":{"value":{"entity-type":"item","numeric-id":4373687,"id":"Q4373687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aff7d267c701eb28a02f7aaf179cc47cb24a1a3","datavalue":{"value":{"amount":"+0.8142933249473572","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":"Q1962042$98B48D3E-9520-406A-999E-01E1D2AEEC67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7a28a35597c61a92f90bfb2c33043f47bdf53f9","datavalue":{"value":{"entity-type":"item","numeric-id":5900347,"id":"Q5900347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"586b51b608e7a3759b8a49cc2be1cebe6c7c7349","datavalue":{"value":{"amount":"+0.8138020634651184","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":"Q1962042$2F21A467-61D8-42CB-947A-C7A6EA6F695F","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":"8acaef50fcda14c34ca74ea7ca00acf7744715db","datavalue":{"value":{"amount":"+0.7920138239860535","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":"Q1962042$49A8E848-DA29-4271-BA8F-A93159CDB92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa4c19686dc1c9542ce56e5f70450628deabd085","datavalue":{"value":{"entity-type":"item","numeric-id":5224858,"id":"Q5224858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c074775c278f4fca49970ecf12efa4f979b009b","datavalue":{"value":{"amount":"+0.7777677774429321","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":"Q1962042$C441D63C-43C8-407D-B22C-2B700D6A2DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a943fe405531e69807c4993dc0bb4f407a759e31","datavalue":{"value":{"entity-type":"item","numeric-id":6056699,"id":"Q6056699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e80c54258797fab37b290b91e60e9893e8cf8a8","datavalue":{"value":{"amount":"+0.7777343392372131","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":"Q1962042$C377D0D6-22DF-4B10-A66A-488CE2375A07","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962042","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962042"}}}}}