{"entities":{"Q1869026":{"pageid":1879768,"ns":120,"title":"Item:Q1869026","lastrevid":71020359,"modified":"2026-04-13T18:57:51Z","type":"item","id":"Q1869026","labels":{"en":{"language":"en","value":"Graph recurrence"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1895795"}},"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":"Q1869026$699FD504-B223-43E5-9740-E330672473A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b22c8e64171e3da927d07d1906bb37d55d0a813","datavalue":{"value":{"text":"Graph recurrence","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1869026$EC4733F9-8FAD-4253-83E6-8066999945FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"161a10dbd581a36587718caad2cdf0fc66158f03","datavalue":{"value":"1022.05051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869026$FD3035E7-A751-4D54-8C73-8B44F6B15996","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe4146ea13f507f0ccdb38e83787c844188a1bd4","datavalue":{"value":"10.1016/S0195-6698(02)00136-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869026$BAD7250E-497C-47A7-834B-360ABA77AA53","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"57d4e16ac21f5611be434cc82ab62e1b494cbe13","datavalue":{"value":{"entity-type":"item","numeric-id":378143,"id":"Q378143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$AE207A90-1643-4104-A54F-1BACE09DDBC4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$8792D555-B539-4C14-B711-0125C2559BB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"00fc66ee85e9b306af3b2dc59b88166cc25a2f20","datavalue":{"value":{"time":"+2003-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1869026$09BA3EFA-15F0-4D35-A8AC-D95B67084012","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db33b1cd3f7cc6a9c9f90512a2083cdbe4ca13b9","datavalue":{"value":"This paper is related to the graph isomorphism problem and deals with particular types of graph invariants called graph recurrence sequences. Let \\(G\\) be a graph of order \\(n\\) with adjacency matrix \\(A\\). Then each vector \\(x_0\\in \\mathbb{R}^n\\) determines a graph recurrence sequence \\(\\{x_i\\}_{i=1}^n\\) whose terms satisfy the recurrence \\(x_{t+1}=A x_t\\), \\(t\\geq 0\\). If this sequence determines \\(G\\), then \\(G\\) is said to be determined by \\(x_0\\). If \\(G\\) is determined by \\(e_i\\), the vector with 1 at coordinate \\(i\\) and all other coordinates 0, then \\(G\\) is said to be determined by vertex \\(i\\). Complete graphs, complete bipartite graphs, cycles, wheels and trees are all shown to be determined by a single vertex. The author also proves that if \\(G\\) is determined by one of its vertices or if the vectors in some recurrence sequence of \\(G\\) span \\(\\mathbb{R}^n\\), then \\(G\\) can be distinguished from any other graph in polynomial time. Two other topics related to graph recurrence sequences, \\(m\\)-equivalence of graphs and separating vertices, are introduced in the paper and their relevance to the graph isomorphism problem is explored. Numerous open questions related to these topics are posed throughout the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869026$5446F501-CBB3-4B2B-A0B1-E6101233CC7C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869026$46FCF2EE-BAAB-4555-9260-4CEEFEA150DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869026$38D1A687-1B28-4AC3-9BC0-C8F049943216","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db91b7805eb804d0f9c9787dd89d6958584a199d","datavalue":{"value":"1895795","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869026$418AA361-404B-4357-B8DD-C69F325729EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec3505d4a1a47ba6779c1bc97acbae985df00be0","datavalue":{"value":"isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869026$123F190C-5502-4A23-8B7D-9103EE40F827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89b5c28ce31c1759628c64ba1269e0bb145a7d1d","datavalue":{"value":"recurrence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869026$FFE02886-E23C-40FC-BFBB-53DECE181BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1869026$90559AC6-B230-4B8E-9428-49719EC98B84","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1d16ec944265e3d9b06e8bdaecd8f498e3ff0138","datavalue":{"value":{"entity-type":"item","numeric-id":241267,"id":"Q241267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$5EE0CC3E-C1FD-491A-8611-3FDA4A7CAB1B","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":"Q1869026$82CDD5B4-8FBD-4A66-A68D-E7AE1F595621","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1bb63192136286ee2b68ee1b226f2d4a02b4b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3901544,"id":"Q3901544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$8B65BB92-5A1E-4E41-8B66-57AA04E82B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5189bf01b82986e7f3fa2dfeba49f704674d7b46","datavalue":{"value":{"entity-type":"item","numeric-id":3320418,"id":"Q3320418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$DD9CD292-6607-40FD-B1AC-53693AD1AEB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"566ff1f2a128f5300661cecc6ae5d1c56f4f2a1f","datavalue":{"value":{"entity-type":"item","numeric-id":5597464,"id":"Q5597464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$DAEEF0F9-F217-4B41-BA2F-3CB919DB7763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4cc4a7ecc6049fce452aec78e65ad081d5e7ec","datavalue":{"value":{"entity-type":"item","numeric-id":4148000,"id":"Q4148000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$3F32F20E-E927-42E0-9301-183E2F1DDD8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1fb25059117f6dfa64a3b394b3edcc67100b7f7","datavalue":{"value":{"entity-type":"item","numeric-id":4187325,"id":"Q4187325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$39A048FE-C7A2-4B56-901D-8EE6DEE0FE29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2de3ec857f6169c81f2908b5b9720efbe3cb44f0","datavalue":{"value":{"entity-type":"item","numeric-id":1168744,"id":"Q1168744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$4500B62E-4362-4BA7-A057-99A5A6D52BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0229ca53743e93370595b3e27543d2eb923e5acd","datavalue":{"value":{"entity-type":"item","numeric-id":3150175,"id":"Q3150175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1869026$E129E97A-BBB4-478A-B264-1AE026D84F74","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"761d7ea65c30f78ac679bafbb632abd2157e833d","datavalue":{"value":"https://doi.org/10.1016/s0195-6698(02)00136-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1869026$DEE96458-6618-4817-85FB-F495668C1BDD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d700e82516fa305c50bfab408671dec449c0075d","datavalue":{"value":"W2912902786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1869026$792C337A-127D-4B9D-B5B1-F564422DBDB1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"795e4678d341f9f755f5982ad54550ca4f0e4423","datavalue":{"value":{"entity-type":"item","numeric-id":1328437,"id":"Q1328437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ef64746f5cd289457ad96afa1bf93f8acf9d550","datavalue":{"value":{"amount":"+0.7038160562515259","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":"Q1869026$5DE2C5D3-2D21-4BE0-999C-F631FFCD8444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ac1372f98fbfb5fa73e7dfc3877fd9b9e8b9868","datavalue":{"value":{"entity-type":"item","numeric-id":2888296,"id":"Q2888296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96a2e9e37aba9f0c877961f57249b80e3ae689d9","datavalue":{"value":{"amount":"+0.7004152536392212","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":"Q1869026$A19BCE5F-03FB-445B-9E65-92427B90CD5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e6c38f9fdbc746b060c5087fb9df00adc97da51","datavalue":{"value":{"entity-type":"item","numeric-id":3312272,"id":"Q3312272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9597663f5683fe4d958d5450745b1b6252cc23af","datavalue":{"value":{"amount":"+0.699135422706604","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":"Q1869026$A22F9563-0123-49E9-9DD8-52313E6AE8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa4729c237fb934d3c82ee1d5d673510d90028eb","datavalue":{"value":{"entity-type":"item","numeric-id":2408975,"id":"Q2408975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2646189a464bdd238523c81f7e4a6026e0703c97","datavalue":{"value":{"amount":"+0.6954829692840576","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":"Q1869026$91F4507A-8AC0-47DD-BE19-322F8C7C0617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3c526b0cad5aace8296ebe811956dfd9621a5c1","datavalue":{"value":{"entity-type":"item","numeric-id":2857261,"id":"Q2857261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16b2ecdf9660b468755a5489fde43274f04945a5","datavalue":{"value":{"amount":"+0.6943318247795105","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":"Q1869026$0D5B154E-4074-41C5-BA7C-ACC6B4B852DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph recurrence","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_recurrence"}}}}}