{"entities":{"Q1850489":{"pageid":1861231,"ns":120,"title":"Item:Q1850489","lastrevid":48021097,"modified":"2026-01-03T09:34:46Z","type":"item","id":"Q1850489","labels":{"en":{"language":"en","value":"Triangles and neighbourhoods of independent sets in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1843720"}},"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":"Q1850489$E2C3B59E-1EDA-41F0-9730-EDD76D4C9600","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a09800082483cc5b1e1371a3c77ed475843189b","datavalue":{"value":{"text":"Triangles and neighbourhoods of independent sets in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1850489$E54E476A-B8E4-46C2-B9C5-330158BA5EE5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09d7d47d6d1307347a23f108fcc542b9e577ec97","datavalue":{"value":"1023.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850489$D9B1157D-9FC1-454B-ABAA-95C159ABFF20","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"373e4903359e8b2b0c33afc2e28ed272b0cfbdb0","datavalue":{"value":{"entity-type":"item","numeric-id":1598822,"id":"Q1598822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$46BA2575-FD5D-4730-B3D2-9D45FE80845D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f7f1fcbb6559f616fb43cbccc2a4fe05892fcdc","datavalue":{"value":{"entity-type":"item","numeric-id":214988,"id":"Q214988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$CEEE1E69-F4C2-4036-BCCB-9B83B5A49F1C","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":"Q1850489$D3A0E1B9-4DFF-49B0-8EF0-0E0682A4B21A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41f50e6d48cb83c0777ccfeab26a53b6ee6f8dc2","datavalue":{"value":{"time":"+2002-12-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1850489$3E299018-78F9-4229-8ACF-6AD33AD46449","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c442c0fc52f52a774b582b8e7f8af3015df2ba34","datavalue":{"value":"It is proved that a graph \\(G\\) of order \\(n\\) contains a triangle if \\(|N(X)|> {1\\over 3}(n+|X|)\\) for every nonempty independent set \\(X\\) of vertices. If, in addition, \\(G\\) is 2-connected, then \\(G\\) is pancyclic (that is, it contains cycles of all lengths \\(l\\), \\(3\\leq l\\leq n\\)). The bound \\({1\\over 3}(n+|X|)\\) is sharp in both cases, and the condition for \\(G\\) to be pancyclic is essentially the same as the known sharp condition \\((\\delta(G)\\geq{1\\over 3} (n+2)\\) and \\(|N(X)|\\geq{1\\over 3} (n+|X|- 1)\\)) for a 2-connected graph \\(G\\) to be Hamiltonian. The paper concludes with the following conjecture of Yair Caro: If \\(k\\geq 2\\) is an integer and \\(G\\) is a graph of order \\(n\\) such that \\(|N(X)|> (k-2)(n+ |X|)/k\\) for every nonempty independent set \\(X\\) of vertices, then \\(G\\) contains a copy of \\(K_k\\), the complete graph on \\(k\\) vertices. This is obvious when \\(k=2\\), and is the main result of this paper when \\(k=3\\). The Tur\u00e1n graphs show that, if true, it is sharp for all \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$CC211542-B1D5-4726-A0B3-3FB4E6968F27","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850489$99382488-BDA4-49C4-9964-846F5289220A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a4ba7dd6be707cba8a112440c779fe24aef2a771","datavalue":{"value":"1843720","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850489$B7E3DE6F-10CC-46D8-A33D-7333D19B581B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17722f49fcd88b1244cfbd7b4d85bd30cb78b38e","datavalue":{"value":"binding number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$75D5529D-A9CE-4DAB-853E-8F8AE0B85C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb021011fdb19548b7c9fddfe9e14ed1410f9ddc","datavalue":{"value":"neighbourhood condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$0CD78796-A870-419A-998C-DFC8C4583293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ce67bd27fc3ee89d8642921735100b79f0d0ab3","datavalue":{"value":"triangle-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$513D09DD-53E8-4B3B-B82C-9EFAB0A6D66D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ca75f4b64fa03d9695e7eec6d6382d3c8f4c7c5","datavalue":{"value":"pancyclic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$83C17D19-4DCF-40E7-AFCE-66CA06096518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0878c078ef175970fee44e60d9d83dc3748c6237","datavalue":{"value":"conjecture of Caro","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$23018956-BD9E-46B6-842E-EE69B5E7FE97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6fd9f5f3e826b326dc36410b2c15756819ec8165","datavalue":{"value":"Tur\u00e1n graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1850489$06590C6D-7DAA-448A-BA3F-769298E3F443","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":"Q1850489$3B5A6EBF-581D-4064-BC30-A4C1C9F364E0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"41f32be47e7d3b46f0713e6156b289685f24f720","datavalue":{"value":"https://doi.org/10.1006/jctb.2000.1974","type":"string"},"datatype":"url"},"type":"statement","id":"Q1850489$26D91CCA-2970-45E3-8AEF-E03825FEEAB7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"792fd603d6461e393af5dfe09ce9937b0755ff4d","datavalue":{"value":"W2015893985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850489$76EAAD06-9A48-48AC-BC1F-F3677412E8AF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"93f248381381e2e61770c496a6d4fdcff85a4af9","datavalue":{"value":{"entity-type":"item","numeric-id":2531805,"id":"Q2531805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$89C28D2E-AF3F-4F62-B7AB-08F1775DC168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f248880efd70b1d61e878c9684c3df4628f1dae9","datavalue":{"value":{"entity-type":"item","numeric-id":4889849,"id":"Q4889849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$B0A2C9C6-7A37-4B2A-8D7B-A60EF800A725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c40437bf83602559deb52d8e49551171dcc2465c","datavalue":{"value":{"entity-type":"item","numeric-id":4271620,"id":"Q4271620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$93A98BD3-EB2D-4E8A-A3C1-E1952C605A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36bf7019213d29f1faaa86cc5f67a03c32cb67ae","datavalue":{"value":{"entity-type":"item","numeric-id":1099191,"id":"Q1099191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$27478DF9-33D0-4F64-B1E6-85CCBB35EFCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb69fddee296cbab447eda2f0f173fca1665239c","datavalue":{"value":{"entity-type":"item","numeric-id":580376,"id":"Q580376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$E7CCB840-E864-4777-843C-67CAE100C5D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b0af54e1c50e8248a0478c03b44c05aa07b1048","datavalue":{"value":{"entity-type":"item","numeric-id":5666592,"id":"Q5666592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$924DABA3-ED86-443E-B9FE-CC2FA2767D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ad57d1d3e42d6740d4dac79ae14457015968773","datavalue":{"value":{"entity-type":"item","numeric-id":1223311,"id":"Q1223311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$892CA752-06B1-4966-AB74-07CA8A1768BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25297b8cdef485ae294ad56977187403b8954461","datavalue":{"value":{"entity-type":"item","numeric-id":3808124,"id":"Q3808124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1850489$A54598C9-1E12-4F6D-A7A4-1CC41DD6E4F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f1a6cb4640500ea0a0fce5f182c933de972d20a","datavalue":{"value":"10.1006/JCTB.2000.1974","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1850489$51680310-F537-49A1-855B-6CE7725CAFC5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2942068d96156ada7f10b80f95004b9735925d0e","datavalue":{"value":{"entity-type":"item","numeric-id":4940027,"id":"Q4940027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c592de167ea9b8d7fe7b2ab645d79d572a28360","datavalue":{"value":{"amount":"+0.8163672089576721","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":"Q1850489$BD16449B-F327-4042-9415-7A020675909C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3133247af90b6f2349b16c9addde76014ea453ec","datavalue":{"value":{"entity-type":"item","numeric-id":2721833,"id":"Q2721833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40903ee4876f6937245091fd875dc3f5b7fb84db","datavalue":{"value":{"amount":"+0.8150821328163147","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":"Q1850489$1FB0554A-DEE7-4FAE-BD74-7399CE8A7623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9e5bc0934bd50b5595404cc381d20d348160f94","datavalue":{"value":{"entity-type":"item","numeric-id":3808124,"id":"Q3808124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb98739b88bc7f6b0e5c4e3927573256a902d978","datavalue":{"value":{"amount":"+0.8029018044471741","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":"Q1850489$40E5ED69-E5EA-4D72-9AFD-40B03960B315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c7580338ac388326d1430e533aef9ac025ded2","datavalue":{"value":{"entity-type":"item","numeric-id":2276982,"id":"Q2276982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aea4d1f7f69097029dcd80863bab6519203a1d4","datavalue":{"value":{"amount":"+0.794792652130127","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":"Q1850489$CE0F49FC-82B4-4CB1-9EED-3FA2E52AF526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8419043803b307bb55ea3bc58b36d3091c3a1a65","datavalue":{"value":{"entity-type":"item","numeric-id":4545428,"id":"Q4545428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3dc3ea076bddb9a07b00892267c513ffcf46c9c","datavalue":{"value":{"amount":"+0.7903032898902893","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":"Q1850489$164A4C41-4F1F-4861-BBF9-BD818FA2331E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1850489","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1850489"}}}}}