{"entities":{"Q5931418":{"pageid":8108220,"ns":120,"title":"Item:Q5931418","lastrevid":97626860,"modified":"2026-06-05T15:07:13Z","type":"item","id":"Q5931418","labels":{"en":{"language":"en","value":"On homotopy of connected graphs having the same degree function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1591070"}},"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":"Q5931418$D8173E97-0314-4FC3-AA85-E9CC4945908C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e2ea1d479fd991dec1cea60c455d6dbf99e8a60a","datavalue":{"value":{"text":"On homotopy of connected graphs having the same degree function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5931418$D304D43E-2FB2-4FDC-B564-72ADD8237701","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"34fd085eccccfa8e4c31415c2e336b9215411324","datavalue":{"value":"0977.05034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931418$8DB3D11D-1984-4A7D-8B15-7A95DEE4B470","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"412433ada4c8b10574529c32ba5c777c2cac005b","datavalue":{"value":"10.1016/S0012-365X(00)00079-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931418$6DF80712-9D1A-47FE-B5A1-E19AFD29D870","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e69a48ea199c743f802d96df074ea6e6ee6e4ad","datavalue":{"value":{"entity-type":"item","numeric-id":1367031,"id":"Q1367031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931418$87FE5BC6-D119-4AE2-8EDF-07D016D20F58","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":"Q5931418$A887010E-AC63-4D6E-89E2-3EC57890213B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9e418580f2b70ce6849ba62f9449722e930b0d2","datavalue":{"value":{"time":"+2002-01-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5931418$44FF0F5C-7446-452B-B8C4-F8BBE704F598","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2420d8bcf60fc74d0291a3c59f694629f273e260","datavalue":{"value":{"entity-type":"item","numeric-id":426905,"id":"Q426905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931418$52F38840-66E8-46A5-B458-397A13560DA6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931418$F794E27D-6FDE-4FB1-A04D-BEC4346F7F35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931418$618B914A-6F23-43B8-AFAC-1B870A47E5FD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5709d30fac6c416a2c285c32cf0f1625f3f432c9","datavalue":{"value":"1591070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931418$C05FEAD5-17A2-426D-AD67-1F30C274A94D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a048c41dcad8259f1ed36a382506d0c806c795","datavalue":{"value":"degree function","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931418$76A0E9DB-040E-469F-9B64-7BAD680E9192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9853bfbafcce8835b3c48c27918c23003cd23a6","datavalue":{"value":"switch","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931418$66AE40AA-43F4-4D53-9D1D-9E6DF80B0A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931418$D4B34A0E-CE45-43F1-B30F-CE819FE78338","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":"Q5931418$46D34B3A-8556-45E4-8BE1-9C43E89F972D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ae44c486bcac9238f19708f9317a5cabf87f1ec3","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00079-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q5931418$58C749E1-92FE-426B-94BA-4DA0936A194B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"84d2daaa8db963a1815731e6206b9e6f8aed83f6","datavalue":{"value":"W2156901254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931418$60BD00B8-9DF1-4E7B-858F-92176D552850","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"385067e441d66f73f155f5e7b2b84e66f09c9fbb","datavalue":{"value":"Let \\(G\\) be a simple graph with complement \\(G'\\). Suppose that \\(e_1=x_1y_1\\) and \\(e_2=x_2y_2\\) are edges of \\(G\\) while \\(e_x=x_1x_2\\) and \\(e_y=y_1y_2\\) are edges of \\(G'\\). The replacement in \\(G\\) of \\(\\{e_1,e_2\\}\\) by \\(\\{e_x,e_y\\}\\) is called a switch. The switch is a \\(II\\)-, \\(\\Pi\\)-, or \\(O\\)-switch according to whether neither, exactly one, or both of \\(x_1y_2\\) and \\(x_2y_1\\) are edges of \\(G\\), respectively. If \\(G\\) and \\(H\\) are two simple graphs with the same vertex set, write \\(G=^d H\\) if every vertex has the same valence in each of the two graphs. For \\(X\\in\\{II,\\Pi,O\\}\\), we say that \\(G\\) is \\(X\\)-equivalent to \\(H\\) if there exists a sequence of simple graphs \\(G=F_1,\\dots,F_k=H\\) such that \\(F_{i+1}\\) is obtained from \\(F_i\\) by a single \\(X\\)-switch for \\(1\\leq i\\leq k-1\\). NEWLINENEWLINENEWLINETheorem 3.2: If \\(G\\) and \\(H\\) are trees such that \\(G =^d H\\), then they are \\(\\Pi\\)-equivalent. NEWLINENEWLINENEWLINETheorem 4.10: If \\(G\\) and \\(H\\) are simple graphs such that \\(G =^d H\\) having cycle spaces of dimension \\(\\leq 2\\), and if they are not isomorphic to the graph consisting of a pair of 3-circuits with one common vertex, then there exists a sequence of simple graphs \\(G=R_1,\\dots,R_k=H\\) such that \\(R_{i+1}\\) is obtained from \\(R_i\\) \\((1\\leq i\\leq k-1)\\) by a \\(\\Pi\\)- or a \\(O\\)-switch and each graph \\(R_i\\) also has dimension \\(\\leq 2\\). NEWLINENEWLINENEWLINETheorem 5.1: If \\(G\\) and \\(H\\) are simple graphs such that \\(G =^d H\\) having the same number \\(c\\) of components, then there exists a sequence of simple graphs \\(G=F_1,\\dots,F_k=H\\) such that \\(F_{i+1}\\) is obtained from \\(F_i\\) \\((1\\leq i\\leq k-1)\\) by a single switch and each graph \\(F_i\\) has \\(\\leq c\\) components. NEWLINENEWLINENEWLINEAll proofs provide polynomial time algorithms for finding an appropriate sequence of switches.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931418$A1AAF8B1-E036-4E1C-BDF2-E4DA67537B8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"894f2bc53f544fecce448a4285a1bf0262d97ce8","datavalue":{"value":{"entity-type":"item","numeric-id":2172397,"id":"Q2172397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8064fc17ddc6447342b2df4893d9f018c887b0a","datavalue":{"value":{"amount":"+0.8454084992408752","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":"Q5931418$55A43712-4172-4EFF-9590-93002BCC738C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fa4a1b6a36042516214089a05848fd755e5a3de","datavalue":{"value":{"entity-type":"item","numeric-id":5863476,"id":"Q5863476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60489be72fe9124896ae8bccf8a7ea50152a9c50","datavalue":{"value":{"amount":"+0.8390495181083679","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":"Q5931418$005AE55A-4077-4AD0-8282-058BDED4418D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8338d8680ae839ba18015b660c0dbecdecc5eef9","datavalue":{"value":{"entity-type":"item","numeric-id":4699158,"id":"Q4699158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2132d2edd8aa25204415875d66328a54d68cc59","datavalue":{"value":{"amount":"+0.8128560185432434","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":"Q5931418$E388E75C-803F-4866-B15A-E84BEA471B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cde3ab73c9af8e26d176e2720ffab70afedeb9e","datavalue":{"value":{"entity-type":"item","numeric-id":704278,"id":"Q704278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87df94bd88d1bace00a72023e7900a09ee81db14","datavalue":{"value":{"amount":"+0.8093177676200867","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":"Q5931418$BAF50F1D-A4AD-437E-AF5D-0779D98B8028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ce582e5131f2a7044ec664763208f19d13e2765","datavalue":{"value":{"entity-type":"item","numeric-id":3689217,"id":"Q3689217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68361985e1f18ef171659318b7ca83c666b14c05","datavalue":{"value":{"amount":"+0.7886182069778442","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":"Q5931418$1EE3AB01-8CA7-4FC3-BECF-C0EC3178BAD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On homotopy of connected graphs having the same degree function","badges":[]}}}}}