{"entities":{"Q1084113":{"pageid":1094865,"ns":120,"title":"Item:Q1084113","lastrevid":66698586,"modified":"2026-04-12T12:11:38Z","type":"item","id":"Q1084113","labels":{"en":{"language":"en","value":"Compatible path-cycle-decompositions of plane graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3977035"}},"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":"Q1084113$0876529D-B2BF-48CB-9F2E-16979BD90CD0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"78ce476971d7951084f2c9dc12916b205e781712","datavalue":{"value":{"text":"Compatible path-cycle-decompositions of plane graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084113$742D35C3-C7B1-4F5A-81D2-4DB55C5C3613","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dbc5c0c11c2a6df85405bb2fc7b4c58196fff5f2","datavalue":{"value":"0605.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$B277C355-AFA6-438E-B12A-441CD17CFA34","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8812a0e83d0ac9d8d05dc49041c41f4f78a8da99","datavalue":{"value":"10.1016/0095-8956(87)90066-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$C54C81E4-FA77-43C6-8BBF-31D61C605C57","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"72bb661145d847bd188af63dd7facd787002875e","datavalue":{"value":{"entity-type":"item","numeric-id":241266,"id":"Q241266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$91B41939-6F39-4829-8DF1-B09CC5DCBDC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6933def1f445e21685d50fc13bd3cfacda780e57","datavalue":{"value":{"entity-type":"item","numeric-id":273170,"id":"Q273170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$BD5A8D82-D572-4F0B-BF86-85EA5AB435A9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$8FF3F1EE-16BB-4F3A-AB93-BB2B8B88F5BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1084113$785F048A-A546-4F89-B6FE-79CEC881BF0E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5921cf178b29a86c729aaf2b7055ee3852100556","datavalue":{"value":"Let G be a (multi)graph and \\(E_ v\\) the edge incident with a vertex v of G. If \\(E_{v,0}\\subset E_ v\\) is a set with an even number of edges incident with v, then a partition \\(X_{v,0}\\) of \\(E_{v,0}\\) into 2- element subsets is called a set of transitions at v. If \\(E_{v,0}=E_ v\\), then \\(X_{v,0}\\) is called a full set of transitions at v and is denoted by X(v). For a vertex v of G with \\(d(v)>2\\) a transition t at v is called separating if G-t has more components than G. In the case where two parallel edges e, f join a pair of vertices v and w the transition \\(\\{\\) e,f\\(\\}\\) at v is considered to be distinct from the transition \\(\\{\\) e,f\\(\\}\\) at w. Let \\(X=\\cup \\{X(v)| 2<d(v)\\) and d(v)\\(\\equiv 0(mod 2)\\}\\). Then X is called a system of transitions of G. If every \\(t\\in X\\) is a nonseparating transition, then X is called nonseparating. For a connected Euler graph G and an Euler trail T (a cycle-decomposition) of G the trail T (cycle-decomposition S) induces in a natural way a system of transitions denoted by \\(X_ T\\) (respectively, \\(X_ S):\\) \\(t\\in X_ T\\) \\((t\\in X_ S)\\) if and only if e,f\\(\\in t\\) are consecutive edges in T at a vertex having degree greater than 2. Two systems of transitions X and X' are called compatible if \\(X\\cap X'=\\emptyset\\). Suppose X is a set of transitions of a plane graph G. Then X is said to be nonintersecting if for every \\(t=\\{e,f\\}\\in X\\) the edges e and f are consecutive edges (in the cyclic order induced by the embedding of G in the plane) at the vertex v at which t is defined. For a plane connected graph G and a system of transitions X of G, the transition X is defined to be suitable if (a) X is nonintersecting, and (b) whenever \\(t\\in X\\) is a separating transition of G, then every component of G-t contains an odd vertex of G. A set S of pairwise edge-disjoint paths and cycles covering E(G) is called a path-cycle-decomposition of E(G) if (a) every odd vertex of G is an end-vertex of exactly one path in S, and (b) no even vertex of G is an end-vertex of a path in S. A path-cycle-decomposition S of a graph G induces a transition \\(X_ S\\) of G where \\(t\\in X_ S\\) if and only if t is a transition at an even vertex having degree at least 4. The authors show that if G is a plane graph and X a system of suitable transitions of G, then there exists a path-cycle-decomposition S of E(G) such that \\(T_ S\\) is compatible with X.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084113$046CA04A-FCFD-4446-B6C6-AF210E3808A3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$2AC20565-624E-493A-8FA1-F9605A7CC67F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$28BECFE5-5F91-4E8B-9A31-39A68FB2F2C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$4DE27F02-780E-40CE-9566-3C759F42F209","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$39B56989-C968-494A-AFE0-9C496F61FA96","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4956f899110c809eb1f1f920eeffff4d6fcf5aa9","datavalue":{"value":"3977035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$57034597-515C-4070-844D-573ECCEE81C6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e48929a7bbe6b620e55a68558b333b0808fc8329","datavalue":{"value":"transitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084113$70C4F2D4-4809-4AA4-A3E3-93DE54C59D90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"894cbc6455e5f75bb2bdb201f0bbd5e0e5c3c288","datavalue":{"value":"Euler trail","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084113$BD2540F1-E3B8-4103-8BAF-EEDF91E5FA85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cf260837d823f7c07290e425111c101d0bc374a","datavalue":{"value":"path-cycle-decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084113$A3D689A0-1055-4183-8ECB-B7756C048CE6","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":"Q1084113$223B51CE-A000-4C49-9B8E-D6D7D4220F85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c79b89af02b4773699b01f96350d4d03a6813c4","datavalue":{"value":"https://doi.org/10.1016/0095-8956(87)90066-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084113$03C4E6C8-90BD-4199-B759-7F0FF2BE7C25","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"721938435e813dd84044f23db904bdab00fbbf81","datavalue":{"value":"W2050405728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084113$CAFE06F2-947D-4AA0-B4A7-FFEBC537CC21","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$F921659D-BF14-48A5-905C-A57F2CB2BB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"538d8fa5ed3cb10f78591c31223742407791b072","datavalue":{"value":{"entity-type":"item","numeric-id":1233877,"id":"Q1233877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$98432E40-11D3-4F0A-A8A2-1CD7BA6E916F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d698492d8f1997235ca2ccb391b98cecddc1c730","datavalue":{"value":{"entity-type":"item","numeric-id":1141658,"id":"Q1141658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$1BB9EB6C-37A7-4CDB-88E4-CBD6108FB4FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dc41503b5662ed374222574b52603b1e24df544","datavalue":{"value":{"entity-type":"item","numeric-id":3220629,"id":"Q3220629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$87AB8401-0BEE-4909-8410-C9D2A71C5753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d0af180e51c28566e86bf8a878f0a48d147a6f0","datavalue":{"value":{"entity-type":"item","numeric-id":3699722,"id":"Q3699722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$AADD079E-A545-47D3-ABC5-A8B936695F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58fb5351b288ba8ddc830d717269f91574f8b6ec","datavalue":{"value":{"entity-type":"item","numeric-id":3879265,"id":"Q3879265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$C2BC5532-80FE-4496-BB03-51BA3E0D77E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9d3ffc47b117d89309b5c0325a071751c1f9407","datavalue":{"value":{"entity-type":"item","numeric-id":3710541,"id":"Q3710541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084113$02597F36-C332-4B4C-95F9-AFFFB3CBE601","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d78950d352c036939bcef3f25434f34d556db0bc","datavalue":{"value":{"entity-type":"item","numeric-id":1814589,"id":"Q1814589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b96a6630a36c33616e8f2ae66c2c3b3730ddf567","datavalue":{"value":{"amount":"+0.8049665689468384","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":"Q1084113$F8E167C0-3190-469C-B950-3071660E36BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8be2b7bd8d97b721d5a03b2d00f4ad45652c0853","datavalue":{"value":{"entity-type":"item","numeric-id":1752690,"id":"Q1752690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6422d31d068a36e47d18906770f732c2f220ccf0","datavalue":{"value":{"amount":"+0.7805361151695251","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":"Q1084113$3E5E3963-830D-42F1-8369-662EEC1DA7AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d619cb1b3de2473b1525c420f89b540839a0d19","datavalue":{"value":{"entity-type":"item","numeric-id":3478428,"id":"Q3478428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"982fbc67bb9dafa1c43ba4725a59db30ab6c172f","datavalue":{"value":{"amount":"+0.7797096967697144","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":"Q1084113$CE7FEA82-D1E4-4CC2-8B99-2F82D5FDFB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d419907878d60d887e0fd4542218e324981bb9","datavalue":{"value":{"entity-type":"item","numeric-id":1689954,"id":"Q1689954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e970d16f86d9ae9cf1609fbbd8a9c461ebbd22ac","datavalue":{"value":{"amount":"+0.777357816696167","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":"Q1084113$1B0774C6-32F3-4F05-8967-EAD2D8416C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"271e4ec22618d435cda3b2348d0184dd7df5c05e","datavalue":{"value":{"entity-type":"item","numeric-id":2312600,"id":"Q2312600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e159de6b109acc9efcc685381d4cf0cce883b4a2","datavalue":{"value":{"amount":"+0.7759313583374023","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":"Q1084113$52E9FECC-7F2C-4836-AA88-987EAF12373A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Compatible path-cycle-decompositions of plane graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Compatible_path-cycle-decompositions_of_plane_graphs"}}}}}