{"entities":{"Q1310247":{"pageid":1320997,"ns":120,"title":"Item:Q1310247","lastrevid":67133910,"modified":"2026-04-12T15:31:11Z","type":"item","id":"Q1310247","labels":{"en":{"language":"en","value":"Evaluation of the characteristic polynomial of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 475052"}},"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":"Q1310247$F6AFE3FE-D0D0-4678-8527-E92C900E232F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0323b78c74a454ddc62f8b4beaa6578dddbc3a01","datavalue":{"value":{"text":"Evaluation of the characteristic polynomial of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1310247$1533C93C-7D7E-4EA8-AAD2-013D8B010A22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"158a454284114b1b81531f39e5b3b7cd701db577","datavalue":{"value":"0789.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310247$BD08AC21-5324-4238-9D09-02812F5FA236","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e2171fa38b4be9f663d5e10008ec372c43fd6fd7","datavalue":{"value":"10.1016/0895-7177(93)90266-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310247$1BB85775-33F1-4B12-888B-C0955232457E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b010567da0e068295e34b824b5eafea5ffd18ef1","datavalue":{"value":{"entity-type":"item","numeric-id":166953,"id":"Q166953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$6767A2F2-0DB6-4081-B5E0-5281AD64AB3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d0f506d9f4280d6b2b60ede7578329839e1e903d","datavalue":{"value":{"time":"+1994-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1310247$D05905D1-F709-41B7-9AD5-C3ABCDD03579","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"35c61333744f7e5152aaa4b5aa21d94806fe60ee","datavalue":{"value":"The author adapts the classical ``Le Verrier-Faddeev-Frame'' method for the evaluation of the characteristic polynomial of a graph by first diagonalizing the adjacency matrix. The resulting technique can be shown to be \\(O(n^ 3)\\) instead of \\(O(n^ 4)\\). The author also shows how to efficiently find (in \\((O(n^ 2)))\\) the characteristic polynomial from the known eigenvalues of the adjacency matrix.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310247$554FE226-0158-41D7-82E1-065F452BE136","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310247$A19A35EF-78AC-41CE-AA65-829A0CFAA8DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310247$16253FE4-62D6-4AD5-8F1C-4C5B245C269C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"435fc09aa5bae392ec1d4876bc8984b3801d4655","datavalue":{"value":"475052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310247$19BFA251-9141-444A-90E8-4FD90A498854","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf24d89f4f0821f90ed933db7d403c989feed0ad","datavalue":{"value":"evaluation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310247$D770E872-9609-4B53-9847-9180658D43EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64287d55cb2f38dd0f11da246e78f83648de9a8a","datavalue":{"value":"characteristic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310247$671A957C-63A6-4746-AAB4-BE713B8938DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310247$EAEF150E-3A7D-4E5E-A6BA-FB042C1C4538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"811604a75801fcd709c8667f83ea26944825b8d2","datavalue":{"value":"eigenvalues","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310247$37FFD077-9C61-4485-9F56-FCA5FAB3F55F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd63054ff0c3e851a80886d71109fbb583fd0ef0","datavalue":{"value":{"entity-type":"item","numeric-id":182481,"id":"Q182481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$16649B04-E121-4285-8056-90058CFC2975","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6b6816c3de7983b793bf4c42808a1cb69f396cb6","datavalue":{"value":{"entity-type":"item","numeric-id":342501,"id":"Q342501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$F964134B-25D8-47BD-9A56-C41B43882871","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":"Q1310247$535197C2-6855-47D3-B8A7-803AE1D241E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ca192309f656dd1b13cc6af03c53452f1388d521","datavalue":{"value":"https://doi.org/10.1016/0895-7177(93)90266-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1310247$12107379-3E80-4F30-8607-19449AF4C780","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b17fa080a6224c1354dc1466e99d6d62eaba45f3","datavalue":{"value":"W2119888463","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310247$B42EEC7E-A924-4BD6-B30B-6885F0BF8FA1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ab333ecd9a78c169f74af957e019081ab880b76","datavalue":{"value":{"entity-type":"item","numeric-id":5629664,"id":"Q5629664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$EDA02440-2B14-4413-98A1-4ADDBBF0320F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72253c36682bd4fdc81427fc1534850d522b8cc8","datavalue":{"value":{"entity-type":"item","numeric-id":5510191,"id":"Q5510191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$BEDC6141-4FD0-4FDD-84F9-5211DD5FD1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95aeba50a812e017a04ca95e7e9b37418f1257fa","datavalue":{"value":{"entity-type":"item","numeric-id":5329152,"id":"Q5329152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$548ADA01-DB42-4C3E-8DE4-09A6E0C5BD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5480b78a6842d5bbb1677977eb65ee45b697ab8","datavalue":{"value":{"entity-type":"item","numeric-id":5807164,"id":"Q5807164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$0B640FCF-916F-4C6D-8425-ECC31723FEEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c0e24da131f46e5d5abee3f558dd4543d104fc","datavalue":{"value":{"entity-type":"item","numeric-id":3686748,"id":"Q3686748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$5468292E-AA76-4A43-855B-08637BA90446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93d537ebc35e61dd6424996fd999debdc01d4c99","datavalue":{"value":{"entity-type":"item","numeric-id":3710565,"id":"Q3710565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$D992A9C6-B219-40BF-8DEA-0A5B5EE1DEAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8ae9c32beb45ccd9818225c2a58afc5e68adbf1","datavalue":{"value":{"entity-type":"item","numeric-id":3713483,"id":"Q3713483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$7D9C52DB-414A-4FCD-B6B4-9A2FB730B442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa60a5c29d3b4a0d50fe2c189e6ea1e387413281","datavalue":{"value":{"entity-type":"item","numeric-id":4039860,"id":"Q4039860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310247$B0B16461-9DC4-4D8E-A3FD-659B0B6BE7E6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e6ab8e41ffc030f205d563e6be17affbcacd853","datavalue":{"value":{"entity-type":"item","numeric-id":2938758,"id":"Q2938758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26d0f7f9896fdeb0de66845711aefd9fd498440b","datavalue":{"value":{"amount":"+0.8217611312866211","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":"Q1310247$CCB6234D-58B5-41BD-84C9-A57F76AB32B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d8f3e754029ca0873e00987831611b5264e388d","datavalue":{"value":{"entity-type":"item","numeric-id":4489172,"id":"Q4489172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688d9813abb79515fd789f20f4ec4b0df8a7bba0","datavalue":{"value":{"amount":"+0.8189855813980103","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":"Q1310247$F9EF231D-BCA0-4354-BA95-9C168AE1C9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5792b010f46060b043c9233e56fc4d873438ad","datavalue":{"value":{"entity-type":"item","numeric-id":5710448,"id":"Q5710448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5356ba59cda229cad44c7c2688ee14ab43c5aec","datavalue":{"value":{"amount":"+0.8089798092842102","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":"Q1310247$47330A3A-2DEB-488A-8557-4CE4401BDDB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a23f7600a4edf0f56bec1e03871a9f384d1ea856","datavalue":{"value":{"entity-type":"item","numeric-id":1057861,"id":"Q1057861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a70ba7c7d4fc02c34358ec2cf5f25287341c92bd","datavalue":{"value":{"amount":"+0.8036825060844421","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":"Q1310247$9FBCC137-A24D-4061-85D4-45B91C80259B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"561bab92146b877b84ae90d9ad221d795797114b","datavalue":{"value":{"entity-type":"item","numeric-id":2333249,"id":"Q2333249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9be0e7d24092f979c063d29b8b0417990f01e005","datavalue":{"value":{"amount":"+0.7946763038635254","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":"Q1310247$13B0420C-252D-4ABF-9858-920FC9A1740A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Evaluation of the characteristic polynomial of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Evaluation_of_the_characteristic_polynomial_of_a_graph"}}}}}