{"entities":{"Q1849906":{"pageid":1860648,"ns":120,"title":"Item:Q1849906","lastrevid":74247843,"modified":"2026-04-14T19:10:31Z","type":"item","id":"Q1849906","labels":{"en":{"language":"en","value":"Minimum multiplicities of subgraphs and Hamiltonian cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1838904"}},"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":"Q1849906$7AE836B4-3BFA-4FC1-8F66-B73A4A1D9DDD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6879407c7eeeb8e24338f0fee895265a185acad7","datavalue":{"value":{"text":"Minimum multiplicities of subgraphs and Hamiltonian cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1849906$E9C36C20-6997-4747-9399-28F986E2691E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d18035482bacaf2545c48999bbab35deee592b67","datavalue":{"value":"1010.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849906$5C52F0F6-478E-494E-AC9A-AEBE24C7E202","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"437bd1d26f295b0da6c0ab742af904d7edf89492","datavalue":{"value":"10.1016/S0012-365X(01)00411-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849906$B5712CC9-F7D4-4AF0-A9F8-A48D6A308021","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a10015d8dc84d50c1e5f084a7e3b6881a3686835","datavalue":{"value":{"entity-type":"item","numeric-id":420624,"id":"Q420624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849906$A8A81BC4-3D97-4C93-9F60-320F0AC47A4C","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":"Q1849906$1AD6113A-A6A0-4DDA-BF13-4C1872B509AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82ac30fadc544187fd268bb88e1da4be75a5ee8c","datavalue":{"value":{"time":"+2002-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1849906$59B8384C-F1C1-4E55-99EE-51E0FBD986CE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"775104e410ad8d11ed7128dc9947fcf92c66ffbd","datavalue":{"value":"https://arxiv.org/abs/math/0012258","type":"string"},"datatype":"url"},"type":"statement","id":"Q1849906$92D616A5-11FB-40A8-B4A6-B900FF4BF556","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ae218be8f3697f4736d6e1f2ac578673a3f45117","datavalue":{"value":"If \\(G\\) is a finite simple graph and \\(U\\) is a spanning subgraph of \\(G\\), then there are at least \\({|A(G)|} \\over {|A(U) \\cap A(G)|}\\) distinct subgraphs of \\(G\\) which are isomorphic to \\(U\\) (here, \\(A(G)\\) denotes the automorphism group of \\(G\\)). \\(U\\) is called a fixing subgraph if there are exactly this number of subgraphs of \\(G\\) which are isomorphic to \\(U\\), and a strong fixing subgraph if, in addition, \\(A(U) \\subseteq A(G)\\) (that is, each automorphism of \\(U\\) extends to an automorphism of \\(G\\)).    The author proves that each Hamiltonian cycle of \\(G\\) is a strong fixing subgraph of \\(G\\) if and only if \\(G\\) is one of \\(C_n\\), \\(K_n\\) or \\(K_{n,n}\\). He also studies the question of which generalized Petersen graphs \\(G(n,k)\\) have the property that each Hamiltonian cycle is a fixing subgraph (the generalized Petersen graph \\(G(n,k)\\), \\(1 \\leq k \\leq n/2\\), has vertices \\(a_1, \\ldots, a_n, b_1, \\ldots, b_n\\), and edges \\(a_ia_{i+1}\\), \\(a_ib_i\\) and \\(b_ib_{i+k}\\) for each \\(i\\), where all indices are understood mod\\ \\(n\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849906$47CE03A1-BE6E-49F9-9D97-936B56AC6C32","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dd63a294e6572609e555f008f990edc4325ef5e0","datavalue":{"value":{"entity-type":"item","numeric-id":579411,"id":"Q579411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849906$A9C26B74-B73E-4D8E-AD3A-E0EE3BF636B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849906$AF978285-361D-4176-9F3F-DC56FF5411C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849906$9EE432BB-AA4D-46E2-A964-551D9E1C1A08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"08b781f035031e63fb2d35ba8903d6686039efb4","datavalue":{"value":"1838904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849906$647F62C1-E089-414D-B999-E326C0F4810A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"622eae487f8222428cc7d71368939b9ee00a0192","datavalue":{"value":"fixing subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849906$054E120F-9EEB-4B75-9155-6A0FC289D2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849906$BEDE32FF-D6E0-46B9-9FAE-E01D98280533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"479e6203ed88abffe10fdca6b6c390a47cf3a96c","datavalue":{"value":"generalized Petersen graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849906$0DA2AA29-FF2C-4A83-903F-728F4FAC41F9","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":"Q1849906$023C25F8-F4B4-4706-A224-60980A86B642","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ddd5b92973aa56e155eae43ea3ea9bd3a14b0454","datavalue":{"value":"W2066789311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849906$14CD5BAF-07C6-402F-8F65-31ACA1951568","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a75f9cc6f27973e5da392fc9a9b09b1a0b17410","datavalue":{"value":{"entity-type":"item","numeric-id":1077429,"id":"Q1077429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab959cfd592623fb66a77d7e35f6c34ba0c1b506","datavalue":{"value":{"amount":"+0.7736741304397583","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":"Q1849906$DC032D4E-F34B-4AA8-A597-0659EF691636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04841948fb0c4e4680c3701b8dd37023b5caec48","datavalue":{"value":{"entity-type":"item","numeric-id":3469119,"id":"Q3469119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2001df1a0a289b17dc9921f4254c2448e36f13c","datavalue":{"value":{"amount":"+0.7621735334396362","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":"Q1849906$BD5566F6-0C61-484C-A328-B8C8C2299A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0afd3b0500e88af83403b0f9c331bdc08124baab","datavalue":{"value":{"entity-type":"item","numeric-id":4871162,"id":"Q4871162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"831db2eb28c4b72e24eb8465373268f5fde01c0d","datavalue":{"value":{"amount":"+0.7551422119140625","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":"Q1849906$852CF8DA-8339-4233-90BE-10DFFEE71D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b9501f7c8ca8380c005b70ccdefd9507ef1c64f","datavalue":{"value":{"entity-type":"item","numeric-id":1584370,"id":"Q1584370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"831db2eb28c4b72e24eb8465373268f5fde01c0d","datavalue":{"value":{"amount":"+0.7551422119140625","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":"Q1849906$1939DE29-F35C-43A4-9159-FEF50496CDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"589d28db5f9334b5045fe6adb5ed5205f214ed2c","datavalue":{"value":{"entity-type":"item","numeric-id":580371,"id":"Q580371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4b2a8354b121494fcf9e07dc85e2e91cf88b435","datavalue":{"value":{"amount":"+0.753239095211029","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":"Q1849906$31D5773A-925E-41EA-B383-67BDBE12ED0A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum multiplicities of subgraphs and Hamiltonian cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_multiplicities_of_subgraphs_and_Hamiltonian_cycles"}}}}}