{"entities":{"Q1356754":{"pageid":1367493,"ns":120,"title":"Item:Q1356754","lastrevid":68541075,"modified":"2026-04-13T00:26:02Z","type":"item","id":"Q1356754","labels":{"en":{"language":"en","value":"Scattering number and modular decomposition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1019105"}},"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":"Q1356754$DD7E70AE-B1FF-42E8-899A-50BE61916749","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc58850c7c1bf0ea5af339dffb8c5bb5d0da8e79","datavalue":{"value":{"text":"Scattering number and modular decomposition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356754$34B95F74-1C72-4D47-9334-E97F0DE511A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54f84e3694adaafe7ceb828b29a0d4931e61f59d","datavalue":{"value":"0882.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356754$46D5A562-4506-4A78-B144-0289549695E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7fe40eee140cec980d1d29a0fb3cbb8d130c5329","datavalue":{"value":"10.1016/S0012-365X(96)00180-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356754$7C3B1148-7848-4588-B557-934CFCF3B4AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"22aa3f664517d8d06839e7d9ff7d20a21bbd7193","datavalue":{"value":{"entity-type":"item","numeric-id":412343,"id":"Q412343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$365D5937-DD91-4D8C-9CC1-23B43B227E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"86f1b1d7e02155ef29f954da5c9568d822119d6a","datavalue":{"value":{"entity-type":"item","numeric-id":190518,"id":"Q190518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$D537298B-A212-42FA-9655-A4FC439EF847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b9f640312755a9fd5215b7e331afcdec42b74b0","datavalue":{"value":{"entity-type":"item","numeric-id":592481,"id":"Q592481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$523A7238-3A24-4B82-9DF7-853570FD6955","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":"Q1356754$056E421C-E665-4DDD-8931-3938DFB0C666","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41bd464af959f1d39dcdde9372100cb844fa6305","datavalue":{"value":{"time":"+1998-03-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":"Q1356754$40169D58-4A8C-4981-AC6D-240FD12C3C1A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b435922c36e299f012986971e705f05a20fb28e0","datavalue":{"value":"The authors present a method for studying Hamiltonicity of (undirected, simple, finite) graphs, by connecting the so-called modular decomposition tree of a graph \\(G\\) with its scattering number \\(s(G):=\\max\\{s\\mid\\text{there is } S\\subseteq V(G)\\) such that \\(c(G- S)\\neq 1\\) and \\(c(G- S)-|S|=s\\}\\), where \\(V(G)\\) denotes the vertex set of \\(G\\) and \\(c(H)\\) the number of (connected) components of a graph \\(H\\). This method is applied to the class of Jung semi-\\(P_4\\)-sparse graphs. A graph \\(G\\) is said to be \\(P_4\\)-free if it does not contain any \\(P_4\\) as an induced subgraph, and \\(G\\) is a \\(P_4\\)-sparse graph if any set of five vertices induces at most one \\(P_4\\) in \\(G\\), where \\(P_k\\) denotes a chordless path on \\(k\\) vertices in \\(G\\). If, more generally, \\(G\\) does not contain any \\(P_5\\), any \\(\\widetilde P_5\\), any kite, and any 3-sun as an induced subgraph then \\(G\\) is called a Jung semi-\\(P_4\\)-sparse graph. Here, \\(\\widetilde H\\) denotes the complement of \\(H\\) in the complete graph on the vertex set \\(V(H)\\), a kite is a graph isomorphic to \\((\\{x_1,\\dots,x_5\\},\\{x_1x_3, x_1x_4, x_ix_{i+1}\\mid i=1,\\dots,4\\})\\), and a \\(k\\)-sun is a graph obtained from a chordless cycle \\((x_1,\\dots, x_k,x_1)\\) by adding \\(k\\) new vertices \\(y_1,\\dots,y_k\\) and the edges \\(x_1y_1,\\dots, x_ky_k\\). Let \\(\\varrho(G)\\) denote the minimum number of (elementary) disjoint paths which cover \\(V(G)\\) (minimum path partition number of \\(G\\)). A Jung graph is a graph \\(G\\) satisfying (1) \\(\\varrho(G)=\\max\\{1,s(G)\\}\\), (2) if \\(s(G)= 0\\) then \\(G\\) is Hamiltonian, (3) if \\(s(G)<0\\) then \\(G\\) is Hamiltonian-connected. The main result of the paper is the theorem that every Jung semi-\\(P_4\\)-sparse graph is a Jung graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$A7094784-3ADC-4E47-8399-EFBDC775F601","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356754$60134215-A86F-4B6F-A821-75DB9B1AE492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356754$6D28E43E-CF4A-4D1A-9892-3A1BD71B58F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356754$A0135046-0E79-448D-A2B9-A8E374752DC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c1127b3e8aa332054f83a2b8b63bde78888a6c8d","datavalue":{"value":"1019105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356754$75A6C933-623B-47C9-8B59-2914FFA5DE72","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453a43e7e93d9a367957c940a4dbc5498dddc3ee","datavalue":{"value":"forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$37D521D7-6091-4153-B4B7-F1F8F9800BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd53d393c376b85f274601d67e734a11b5e588d2","datavalue":{"value":"Hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$3F6D73CE-14B6-49AA-97E2-FC44B72DB6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c56dfd88929c888514f22bf242d37816dfedddd","datavalue":{"value":"modular decomposition tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$8B0D960C-9537-4CF7-885F-01050B0B1755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9a04a453e91c79c7e831d838f6c5e3a9e0859a2","datavalue":{"value":"scattering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$84535EA2-1F67-411A-A0F8-7E76AFD9CE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f88036c3e3561f9f0c7a56cd24c12ac688b07e2","datavalue":{"value":"chordless cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$AAC1A98F-6BD4-40A0-B2E9-95D233E93265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af95d87a8f6ef2ea839dfa35dcec2f4186a108ad","datavalue":{"value":"path partition number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356754$DDFF2206-81D7-49B1-A5C0-902536A5FCE0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ab25d4f22422fef1c0f819f04a582c1dc09a95d9","datavalue":{"value":{"entity-type":"item","numeric-id":878647,"id":"Q878647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$DC9318E0-5C0C-47B5-B36B-30CC17C73CE0","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":"Q1356754$44AE7A86-494B-4D61-B004-33944FC4ADB1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a13bf5ea222488a462597a035d6c581000a87a","datavalue":{"value":{"entity-type":"item","numeric-id":3665151,"id":"Q3665151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$A3004088-458E-4490-9E00-9144ED1BDE7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$7B51BD5B-50BF-4209-8A59-EF142C2447FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$6B9A4502-D71D-4987-B858-7945A7802122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edc2fe01664e7ae5dbedc60a81011b311142a1b","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$2CE4303E-6CE1-4F87-85B3-94A7043B6047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed91ed0176924a73cbecba9388f8a04535563e10","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$044C0259-D7E8-4720-BAC6-189EB4C15B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39569c210dc21beb4d8a513aef47b877fa809cf5","datavalue":{"value":{"entity-type":"item","numeric-id":1356751,"id":"Q1356751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$C35C632D-1599-4D23-A55D-A20CBC05A528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$9C4DC542-7D6C-43C4-A07A-E7C2D75E5F84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$4E74D304-4AFD-49FF-B10B-BE5518857DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3b2998788fd5c6bb689ab64483e3a026a3e293a","datavalue":{"value":{"entity-type":"item","numeric-id":1183332,"id":"Q1183332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$F79FE27B-1A58-4DE0-BBFD-D7D70A592DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aae757a56df0e1aae621c1729d15bd0c25fda68","datavalue":{"value":{"entity-type":"item","numeric-id":3990660,"id":"Q3990660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$DAFB6A5E-D265-41BB-A451-D1AAB504C127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31403449edcb685befef57967c6d318e33df55c0","datavalue":{"value":{"entity-type":"item","numeric-id":1247984,"id":"Q1247984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$F9162AFA-E4FF-43D3-B400-53996ECEDA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886ba032e540aea708d21bd27fbc92799a765ca4","datavalue":{"value":{"entity-type":"item","numeric-id":3686754,"id":"Q3686754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$18696C95-F932-4C2B-813D-C6593BD522E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93a0021bb8eb537cd0811e93c7490e7e9ba98e6d","datavalue":{"value":{"entity-type":"item","numeric-id":3683903,"id":"Q3683903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$E3AB66F2-43D0-4097-88D5-B72E6C21C70F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f0bbee70e974bce02bd0ec590b8a15aec2e7266","datavalue":{"value":{"entity-type":"item","numeric-id":3836509,"id":"Q3836509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$8AB8C69D-A01D-4A70-A5D3-009CA81169CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1ca25f33b598e553490e1213a9228decd88e954","datavalue":{"value":{"entity-type":"item","numeric-id":1130879,"id":"Q1130879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$0F9BCF7A-AA19-406F-B7EF-BB9EE6AD38AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ae6531ddd34dd32c46772f585d82684b355ed87","datavalue":{"value":{"entity-type":"item","numeric-id":4097319,"id":"Q4097319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$B773168F-4CF1-4DDF-952F-FD67CF2254DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d6ac11073d1feae5d3b5ea3b3fb57bb14591823","datavalue":{"value":{"entity-type":"item","numeric-id":1394240,"id":"Q1394240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356754$6F349841-3818-415B-BB5C-C5CDC2194F79","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"016ec3c47a72e5137aa3d495687fd97f4e726bd1","datavalue":{"value":{"entity-type":"item","numeric-id":1805009,"id":"Q1805009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3023d9a1f7fda016443f4e388cf3c0a1ab1888de","datavalue":{"value":{"amount":"+0.7630246877670288","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":"Q1356754$A9085711-1BC8-416E-9029-64CADDD187D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c7d3f23e0f125165bfebcebf6c03deae400820a","datavalue":{"value":{"entity-type":"item","numeric-id":1356751,"id":"Q1356751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b54178e0a89170fbe3deb2439f82692e93b6b915","datavalue":{"value":{"amount":"+0.7625706791877747","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":"Q1356754$9A75C004-FCC4-42B1-AA8B-0136D7D5CD6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd11a5c832577202fa537d79ac01e648caac1df6","datavalue":{"value":{"entity-type":"item","numeric-id":1109047,"id":"Q1109047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"febc769468dd20b22178fee4f843bab66346c63f","datavalue":{"value":{"amount":"+0.7407644391059875","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":"Q1356754$10156DC7-E48E-468D-9F84-0C21131BBA85","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scattering number and modular decomposition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scattering_number_and_modular_decomposition"}}}}}