{"entities":{"Q1174181":{"pageid":1184930,"ns":120,"title":"Item:Q1174181","lastrevid":46213057,"modified":"2025-12-24T08:05:53Z","type":"item","id":"Q1174181","labels":{"en":{"language":"en","value":"A note on compact graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8208"}},"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":"Q1174181$639F5AAD-89B0-4609-A711-5D985DBEE094","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"908e5b2a7723fd7d26221e4b602e1b610781d745","datavalue":{"value":{"text":"A note on compact graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1174181$3BD9BF85-B02E-46C1-B49C-AFBF88996E30","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e8007b646ac6185a9452655a9b802c500b2b1cd6","datavalue":{"value":"0771.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$5B76320B-ACEF-43D3-A21B-7938513AA743","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6a4636c71d7b06344bb312f31849940a092b13b6","datavalue":{"value":"10.1016/0166-218X(91)90049-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$930BFE79-CD0E-4677-A3C4-6C2B912DF116","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":"Q1174181$9C734B06-36D0-41B4-B175-B26EF44E4BAF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1174181$F0F11C97-1771-4B24-B275-C652796CF948","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e51ba0c5df19f729a3664a6b4f61aea28db73a0","datavalue":{"value":"Let \\(G\\) be an undirected simple graph with adjacency matrix \\(A\\). By \\(S(A)\\) we denote the set of all doubly stochastic matrices which commute with \\(A\\). We say \\(G\\) is compact if the extreme points of \\(S(A)\\) are all integral. It is not hard to see that the integral extreme points of \\(S(A)\\) are precisely the permutation matrices which commute with \\(A\\). Note also that \\(S(A)\\) is closed under matrix multiplication. Compact graphs form a fairly restricted class, for example, any compact regular graph must be vertex-transitive. The main result of this paper is a simple polynomial time algorithm for deciding whether a graph \\(H\\) is isomorphic to a given compact graph \\(G\\). The bad news is that the problem of recognising whether a graph is compact is not even known to be in NP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$7A91BC96-5B52-4313-A8E6-8F46B4BA609D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$C9D73AF1-F6BC-4767-B33D-99876296490A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e0bbeefc3d633ef2a2ca36004dc27235255343f","datavalue":{"value":"15B51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$3BFB4949-4FFA-465D-8B4D-1FCD58FA41EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$B8EF9896-3900-4A01-8547-CBCCDEC824DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$FA17717B-3742-4008-8423-9CFFC7B5E1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$E7797673-7A96-4189-9500-2CD83BE00DBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2874e4cc514356c78b2f5a1760402acba0ca3c5d","datavalue":{"value":"8208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$CA8B16C9-F092-47E9-8857-2D56730CCEC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec3505d4a1a47ba6779c1bc97acbae985df00be0","datavalue":{"value":"isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$78B2420C-DAE4-4A54-B97F-683E53638AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$F6C353EC-628A-4F13-929D-5D0D6A0E00D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"363dbc7ab788b58ed966afa90c6c29df183fd7b7","datavalue":{"value":"doubly stochastic matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$016740B0-99C2-4B03-BBE9-45ABC5F85E9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18ee3a80cd5ac96e9cd588561d71f3861b4eedae","datavalue":{"value":"permutation matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$33B21266-E70C-4F94-AD1F-EBD4F56D19DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$D8629B7E-75EF-407C-A66C-C45813D0D00C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9762514e7f492c20a83ecde4a326eb6d041011","datavalue":{"value":"compact graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174181$2CC0462A-3660-4317-998A-48B472139745","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a04ecc81832bff993b189ec55412cfe64658861b","datavalue":{"value":{"entity-type":"item","numeric-id":196797,"id":"Q196797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$568C0AF6-3BC5-46D2-9130-2BC92745FF7D","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":"Q1174181$FF075F9A-47BB-489F-AEB3-EF70F0200A3F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0d4712586fc706e9f2c1995dc7a01f19751ecda","datavalue":{"value":{"entity-type":"item","numeric-id":1110617,"id":"Q1110617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$79EDE0A8-B99F-4A93-95F9-DE9175C4F45D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7df60897b7f36fcb755315945b431813c52a78e4","datavalue":{"value":{"entity-type":"item","numeric-id":3910010,"id":"Q3910010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$3040064D-51D6-475E-AD05-0304C85A37F2","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":"Q1174181$1DBCB7EA-3693-4C8A-B1FD-D3A2184379C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"993523c8e0a8bcaa45c9861547e4408c240b92e7","datavalue":{"value":{"entity-type":"item","numeric-id":4120604,"id":"Q4120604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$6404193C-CB37-4506-A7EA-2473B7451C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16b4d29c0ba31b1bc8e06218af428a76fc8ce67","datavalue":{"value":{"entity-type":"item","numeric-id":1210712,"id":"Q1210712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$046248D1-F4F3-42AD-A7E1-1E3D57032E4C","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":"Q1174181$D5BC092B-1765-4113-9E9D-41B0048B670B","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":"Q1174181$53A4E5C2-0AC2-4BC9-81E9-02D4791028B3","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":"Q1174181$F6D5DE81-BE75-4CA3-93B0-30E3D727104E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb0d74c67dc2a310002c18dbbd07aa3d14ea2edc","datavalue":{"value":{"entity-type":"item","numeric-id":4159083,"id":"Q4159083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$DCD37566-C2E8-4622-B23D-E22E2F49295A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80430fcf2695dcdcfb49b722e4deca1e5a5bc6a3","datavalue":{"value":{"entity-type":"item","numeric-id":583235,"id":"Q583235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$EAEE2605-35D2-4696-A511-186EF97211FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"428fc0655ce4fb9f45f51f46c690421b2b43487d","datavalue":{"value":{"entity-type":"item","numeric-id":1068104,"id":"Q1068104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$83421695-87C6-4CA9-9190-32E82EF12810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2cd2c99b6dc80fff911a8eb1fb1557914beb61a","datavalue":{"value":{"entity-type":"item","numeric-id":1119942,"id":"Q1119942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174181$42574B61-8CD3-41DB-BF41-E6667BBE7E44","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"dc276475f0e7f95ccc9df21c77e60a936e3fdc0a","datavalue":{"value":"Q126310991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$95366B23-28A9-4F53-AC53-E717D2E6F80A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"29fb13b8d6eb91076ad051f23c8533c42d904bba","datavalue":{"value":"https://doi.org/10.1016/0166-218x(91)90049-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1174181$E139601A-F73B-4B38-ADCE-F0697CC58E01","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d50b033d472236b77f9d1d1cfa75a2771d71c73b","datavalue":{"value":"W2003282281","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174181$40260454-DC15-4556-B4B0-57AFF3D8F82A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e71045d44c111f3067e29d89ef2088caa7f08e5","datavalue":{"value":{"entity-type":"item","numeric-id":2581244,"id":"Q2581244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44906a2d323bc7811bbd8a4366d88417b04c20d7","datavalue":{"value":{"amount":"+0.8846684694290161","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":"Q1174181$E4240C47-AF4F-4781-8B00-FED78004326E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c9199a754011b5312e4a0ec754bfe99aebd3ab7","datavalue":{"value":{"entity-type":"item","numeric-id":677814,"id":"Q677814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16c3dcd92ae442e31cc7ca2e5c25adc851d4ebe1","datavalue":{"value":{"amount":"+0.8697940111160278","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":"Q1174181$36C12161-2A8D-4BC1-B70A-5AB823DE56D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a09690421d84b59da9beb94f2c1c6a17f922b994","datavalue":{"value":{"entity-type":"item","numeric-id":2987544,"id":"Q2987544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e502ddb34971329454b9607536286f73cb132cd8","datavalue":{"value":{"amount":"+0.8409028649330139","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":"Q1174181$F3309E2B-3BB8-404F-9BE2-82BB8819F4AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df8468d6291f70373d67bbcefddf1066ed7a4563","datavalue":{"value":{"entity-type":"item","numeric-id":2993693,"id":"Q2993693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b512e97857724937948326bd83a4b7d4841ee83","datavalue":{"value":{"amount":"+0.8319495916366577","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":"Q1174181$192BF660-B0A5-405B-8C22-B5667F25EDDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e7bd55d96b1678e43812ae7e253bc58dbb8ef38","datavalue":{"value":{"entity-type":"item","numeric-id":2991746,"id":"Q2991746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5a1cd03620e10c38598cfa48b289965fc0e8bda","datavalue":{"value":{"amount":"+0.8219154477119446","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":"Q1174181$DE80C53C-E884-41ED-B325-7ADF0803B6F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1174181","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1174181"}}}}}