{"entities":{"Q1916397":{"pageid":1927139,"ns":120,"title":"Item:Q1916397","lastrevid":46435257,"modified":"2025-12-24T19:03:55Z","type":"item","id":"Q1916397","labels":{"en":{"language":"en","value":"On the isomorphism problem for a family of cubic metacirculant graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 896545"}},"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":"Q1916397$C6271538-2010-4D15-A816-DB3A7B5412C7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0113c4d19ed275df879719bd678d23842a3c0e0e","datavalue":{"value":{"text":"On the isomorphism problem for a family of cubic metacirculant graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1916397$291C954E-4F1C-43EF-8F9F-C13D7345013C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ca1a49ff445071a6bc5cfbe5471a877d007be2e","datavalue":{"value":"0858.05077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916397$09C5BC76-5AD7-4A5F-B6C0-7407F5DA6801","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6502a9043706bf416c8855a8dec9d104c63dc7cf","datavalue":{"value":"10.1016/0012-365X(94)00100-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916397$71FC3FD4-863A-492E-A7A5-15C1639B2F43","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"443059ed3ba4898db05b88c091a803dbbe6729d0","datavalue":{"value":{"entity-type":"item","numeric-id":873803,"id":"Q873803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$FA275153-0FB3-4DCD-8CBF-9A4A5A6E77AF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$63B50A59-4AB9-4396-8467-441E1E7F59E2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"855b294c40ea15d15c772c1cf5a9dca8de76ccfa","datavalue":{"value":{"time":"+1996-09-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1916397$1B6FDFE1-CB90-4D4A-BC2E-8ABD7011F631","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c5f3534a6c4eb401bacbec5f1cb9a95b8003c6a3","datavalue":{"value":"\\((m,n)\\)-metacirculant graphs were introduced by \\textit{B. Alspach} and \\textit{T. D. Parsons} [Can. J. Math. 34, 307-318 (1982; Zbl 0467.05032)] using a set of subsets \\(S_0,S_1,\\dots,S_\\mu\\) of \\(Z_n\\), where \\(\\mu=\\lfloor m/2\\rfloor\\). The author of the present paper had characterized earlier the components of cubic \\((m,n)\\)-metacirculant graphs with \\(S_0\\neq\\varnothing\\). These are either circulant graphs or generalized Petersen graphs with certain specifications. Using this component-characterization, the author first presents an algorithm of complexity \\(O(\\log^3_2(mn))\\) to determine these components.   Let \\(\\phi(m,n)\\) denote the family of these \\((m,n)\\)-metacirculant graphs and \\(\\Phi=\\bigcup \\phi(m,n)\\). In the main part, the author presents an algorithm for isomorphism checking for graphs in \\(\\Phi\\) with same time complexity \\(O(\\log^3_2(mn))\\). This is done by imbedding \\(\\Phi\\) in the bigger class \\(\\Psi\\) of graphs whose components are either circulant graphs or generalized Petersen graphs with given specifications, and painstakingly checking for isomorphism conditions between these graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$1D3351D3-307E-4106-9A25-F5A06DC650B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916397$890E1951-DA37-4385-8778-E1C9F17BADC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916397$021CCCB1-3047-4F5C-9208-C9EA2D5809C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916397$B953871D-5AA6-4631-A550-8D8EA48F7D73","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97b07fd8d5d72afcdb8f072075d6a7211cc0e815","datavalue":{"value":"896545","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916397$3DA90403-FA34-40E5-8E63-1DBFCB22A124","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7004ea3c45e788d894ca43ad9fb77d664ad32ef0","datavalue":{"value":"automorphism group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$B3C97CE2-8912-4B13-9E59-109B2FF72F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f89e212a3d20834a57bece2099adecbbf41b351b","datavalue":{"value":"metacirculant graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$32EC61C8-CC9E-4977-B2CD-B4B3A20401E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"838e316c2483ef64533e291f4a64eae5d7152e8e","datavalue":{"value":"circulant graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$E62681AD-E719-46AC-9586-1D53B1EC175E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c64631efb2354f83109b2bcccf07450d0f2489c0","datavalue":{"value":"generalized Petersen graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$2E3F9EE3-95E3-4B12-87C8-1B486C8E547E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$F405438B-ED4B-44DE-A44D-EC9B4D6A823C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6ee572ae22305c7b4e7a1b4f073c2a448a3c57f","datavalue":{"value":"isomorphism checking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916397$753ED525-E17F-41C3-8736-62B3E94BFDCB","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":"Q1916397$A2A3E7D7-5A6D-4C07-944F-45D377856AEE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca65ef0f294eb8c69021b8c388d1a1c2b4cc7f9f","datavalue":{"value":{"entity-type":"item","numeric-id":3715142,"id":"Q3715142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$CAA823A6-BD02-449F-B8E4-D8AA446106A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cf10b8a3af126cdb94338213578d93d0c2bb558","datavalue":{"value":{"entity-type":"item","numeric-id":3919737,"id":"Q3919737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$19994BE7-BDFF-498D-AD36-5B63F985A28F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f270080bc7726e0c5ca9d7ffad937c1d07dfcc27","datavalue":{"value":{"entity-type":"item","numeric-id":3937434,"id":"Q3937434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$82FD3017-9057-44FB-82A0-9AEEC287610F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d45d926271251aca46519af253caa082834b3b93","datavalue":{"value":{"entity-type":"item","numeric-id":3708043,"id":"Q3708043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$CB6F5985-C4E5-4051-AEBB-94A89F83E2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f24b6cf13ec3258a06cb8ea8c6f9a24d31c47e","datavalue":{"value":{"entity-type":"item","numeric-id":5625213,"id":"Q5625213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$981E6FC1-0A61-45C3-846E-0E8637688BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73fec37fd1d8ef9d9a93417edbde49727621745d","datavalue":{"value":{"entity-type":"item","numeric-id":1175293,"id":"Q1175293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916397$4768CADF-A72A-4F34-A62A-E229A27EBE64","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee634927e63fe4808d84080cf8a447644d63682d","datavalue":{"value":{"entity-type":"item","numeric-id":1376668,"id":"Q1376668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef806ace753e631086b65d58ae576341302a71d6","datavalue":{"value":{"amount":"+0.8503904342651367","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":"Q1916397$DE8B9F4F-722D-4CFA-8D23-807154412605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4fca9c24e1090bb8717578272be3c188848d191","datavalue":{"value":{"entity-type":"item","numeric-id":1175293,"id":"Q1175293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cffb88aee1f32dbe9fc5fdb10f4b743807b537a4","datavalue":{"value":{"amount":"+0.8293359279632568","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":"Q1916397$DCF8730B-073E-47BD-B0ED-63D2313626FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a52ce4d983fcd104ffa33165ee7cac3ee464639","datavalue":{"value":{"entity-type":"item","numeric-id":4235700,"id":"Q4235700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9df12a572d5ba0482a38b1ea924ba012d1e3a4e0","datavalue":{"value":{"amount":"+0.7902331352233887","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":"Q1916397$FA4DBA8C-2F98-46AA-A18C-B6C4F468AC18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1916397","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1916397"}}}}}