{"entities":{"Q1640209":{"pageid":1650950,"ns":120,"title":"Item:Q1640209","lastrevid":68237877,"modified":"2026-04-12T22:21:32Z","type":"item","id":"Q1640209","labels":{"en":{"language":"en","value":"Nonempty intersection of longest paths in \\(2K_2\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6888446"}},"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":"Q1640209$47956E5D-54EA-487D-955A-CFD12E3E2D4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e7fbc7f1f7eece6cc2bf046e94ede999200a5d24","datavalue":{"value":{"text":"Nonempty intersection of longest paths in \\(2K_2\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1640209$4DE0217F-A645-497C-BD17-88C1AE24A0DA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae06a59351e3209332838b23ec67200c15f7f386","datavalue":{"value":"1388.05099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640209$E6FA02A5-CC6E-468C-86B2-593FBEC0551E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"42d46e45aa60a1b39366747710da293af1143c91","datavalue":{"value":{"entity-type":"item","numeric-id":329565,"id":"Q329565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$54B359AA-9344-4644-8D18-F7FB9F7CCCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f312e00acc1947270ff9dd670df2a632a917a4a3","datavalue":{"value":{"entity-type":"item","numeric-id":463283,"id":"Q463283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$C3A4C8DF-5F7E-4605-B0B1-42F6A78887D3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$D64C8506-1C15-4505-B25F-ADAF5DAD950D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b559bb800700d5ba2a45f57085de6ba33131f78","datavalue":{"value":{"time":"+2018-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1640209$AB1D230C-0889-4762-A67F-D3B69486436A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fce0e0ec20d9b4772892fa14e2fcec9ccd3a249e","datavalue":{"value":"https://arxiv.org/abs/1611.05967","type":"string"},"datatype":"url"},"type":"statement","id":"Q1640209$9FD10722-39C3-4D60-B131-9E07C4364036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"63fa174d5b35762db0624e51835bf4f9d06b1a18","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p37","type":"string"},"datatype":"url"},"type":"statement","id":"Q1640209$98020F12-BE1E-42C8-94FA-F33C7BCFB188","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a146be153f566cad86fb040302888c8d18997292","datavalue":{"value":"Summary: \\textit{T. Gallai} [``Problem 4'', in: P. Erd\u0151s and G. Katona (eds.), Theory of graphs. Proceedings of the Colloquium held at Tihany, Hungary, September 1966. New York: Academic Press (1966)] asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallai's question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, and series-parallel graphs. A graph is \\(2K_2\\)-free if it does not contain two independent edges as an induced subgraph. In this short note, we show that, in nonempty \\(2K_2\\)-free graphs, every vertex of maximum degree is common to all longest paths. Our result implies that all longest paths in a nonempty \\(2K_2\\)-free graph have a nonempty intersection. In particular, it strengthens the result on split graphs, as split graphs are \\(2K_2\\)-free.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640209$FB8EC4BC-3EA6-43DF-926B-DBBEF7DE22EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640209$8EFF576C-F60D-4C84-9909-F4C8F9526F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640209$B5785E0A-05AC-4625-BED0-A17F6AE4A3F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c4f7c9283b8d60c09816bb95c85f2cb967dcf97","datavalue":{"value":"6888446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640209$28DB3EA4-EDBC-43F4-BFF7-FC157F910CC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f0c78b211942dea02da1a190c0e8920eafc8081","datavalue":{"value":"\\(2K_2\\)-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640209$E825B221-3E29-464C-94B0-0880FCE3A976","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cc951a9043dcbba9aead96d41fcb49240f8cbd6","datavalue":{"value":"longest paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640209$804108B8-E3D0-49D9-95C3-028AE0E5BC7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a38fca8c67c117665c0b89ed038b8bb4c0836ce","datavalue":{"value":"dominating paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640209$4FD4E506-638C-4CA3-B3E9-D1EFDED938C5","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":"Q1640209$C34BA7D0-0371-4E2F-81A3-641F4E1CADD7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"665e8fc12dc1cfc6a1b4fb6e056f4da0d4cd83b3","datavalue":{"value":{"entity-type":"item","numeric-id":4819244,"id":"Q4819244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$F6AA2A33-0FEC-4532-8305-2E19BB5569B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b6214dde2be3289bdf38db9febacb730fcc0cbd","datavalue":{"value":{"entity-type":"item","numeric-id":729758,"id":"Q729758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$BFAAD609-AEBD-4BBF-A6C5-8E1FDAC4823B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0f73be776408be252e6928c1d0ae615a65f3aa6","datavalue":{"value":{"entity-type":"item","numeric-id":912124,"id":"Q912124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$85EE3778-76F6-4583-BA88-38DA76599D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"681289ad8b1f03e35a7a8a2845b83e4ce6c8c259","datavalue":{"value":{"entity-type":"item","numeric-id":2857437,"id":"Q2857437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$C8AF3A53-1D81-405A-AEC9-AF1B8F93E214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"792256c8873840b120296a2204bed3b33a18cdae","datavalue":{"value":{"entity-type":"item","numeric-id":5537559,"id":"Q5537559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$529BD496-F070-41D2-9109-153D950AE46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43c7108c17cc46edf028972e4a923996218fd5ad","datavalue":{"value":{"entity-type":"item","numeric-id":2516667,"id":"Q2516667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$FDB55C5F-EEAC-468D-91CE-AA209C1BF046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5f4572babb513ca7f3c8ffa84ff7c9cb7b35636","datavalue":{"value":{"entity-type":"item","numeric-id":3199444,"id":"Q3199444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$286FA00F-CF95-44BA-8629-B1AA0484473D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77d9efa4f65ab174c5e6306a34e1421930667e0","datavalue":{"value":{"entity-type":"item","numeric-id":856888,"id":"Q856888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$C6FE506C-D7F1-44EF-9E73-D650937F35D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a68b3177d1bc9f7ac9317a14ed42649b1c652939","datavalue":{"value":{"entity-type":"item","numeric-id":1196569,"id":"Q1196569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$CAED1A0B-9C00-4CC6-AB08-8DDD197E45D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f5a03a0a245f92eb74f84ad60bef5a0a635fd34","datavalue":{"value":{"entity-type":"item","numeric-id":5177022,"id":"Q5177022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$112A3E28-891E-42B2-894B-0CC89CCC43C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78342f68e81b42f25e4d7a444a50a351a4513840","datavalue":{"value":{"entity-type":"item","numeric-id":1223315,"id":"Q1223315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$C8256EC5-226D-4A1E-B7FE-431DD6C389FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2950aa169477d7dd470a961dce96eef7dedb75a","datavalue":{"value":{"entity-type":"item","numeric-id":5576237,"id":"Q5576237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640209$A122DD3C-6FB8-4B96-ADF5-5737E33677B7","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"abce1a5bb6b49e1591ddd50884160bc508a873ef","datavalue":{"value":"bafkreihauaiiscmp4m5dkv754a3hizkeyoebw7l2z3776fzysmdl54fywi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640209$5C40E832-71AE-478A-BD86-47509B524FF2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d812eb9218c6a5cb795ce5872fd8440322d1454c","datavalue":{"value":{"entity-type":"item","numeric-id":2231747,"id":"Q2231747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"073b656af6f28afdf829b39d4f19d8ac866efd27","datavalue":{"value":{"amount":"+0.8845887780189514","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":"Q1640209$B4C16645-86FC-4D2A-B672-2A50907FEC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a6b9dec8b7431126138f4a70a7bb0edeaad5ec5","datavalue":{"value":{"entity-type":"item","numeric-id":729758,"id":"Q729758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"582084f47bddde88992a99ed60ae4277672d47e6","datavalue":{"value":{"amount":"+0.8516589999198914","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":"Q1640209$F1B8BCF8-B918-4DE3-9581-8722257DF3C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ecb8c15678b423a92230c8c366edb471a706da4","datavalue":{"value":{"entity-type":"item","numeric-id":2692169,"id":"Q2692169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9dc44c8ce528b832400a39c7adcd3b6a258e9bf","datavalue":{"value":{"amount":"+0.8184926509857178","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":"Q1640209$75BF8C67-0152-4D6F-9C00-14D1A8487CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"727e9f1a485cf680275f2058a6f9d4d90a24bbdd","datavalue":{"value":{"entity-type":"item","numeric-id":2857437,"id":"Q2857437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"627055f997a9a682b4c0cabc75b68df4ed6a4315","datavalue":{"value":{"amount":"+0.8139727115631104","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":"Q1640209$00A941EE-15F7-4546-8A92-B4823E8364FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bbbf5c897b364fef51db3a00b51d63d36d7b0f2","datavalue":{"value":{"entity-type":"item","numeric-id":389499,"id":"Q389499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d297893ba2412c77244287469ad8e016663fa2f","datavalue":{"value":{"amount":"+0.8045877814292908","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":"Q1640209$9D330DCA-B952-4160-A80A-203F03025A9F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonempty intersection of longest paths in \\(2K 2\\)-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonempty_intersection_of_longest_paths_in_%5C(2K_2%5C)-free_graphs"}}}}}