{"entities":{"Q1357727":{"pageid":1368466,"ns":120,"title":"Item:Q1357727","lastrevid":67227018,"modified":"2026-04-12T16:12:31Z","type":"item","id":"Q1357727","labels":{"en":{"language":"en","value":"Lower bounds of length of longest cycles in graphs involving neighborhood unions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1021676"}},"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":"Q1357727$18E7CCE3-CECD-49E4-997E-9D795C247173","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff54782c947b4c91837ff272cf893224bc377475","datavalue":{"value":{"text":"Lower bounds of length of longest cycles in graphs involving neighborhood unions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1357727$49D6D54B-5BF1-4BD8-B6B7-96C08DCF9595","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"efd9c80880d93e964930506a65d6a8d916996228","datavalue":{"value":"0879.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1357727$D37A136B-57BB-4D6B-8010-95AC4B25DD16","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3358ac6f8374506727ba6f5796eadd3292a1d3f0","datavalue":{"value":"10.1016/0012-365X(95)00226-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1357727$CE41833A-78B7-4403-AAF8-58971ABD4385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P27","hash":"3358ac6f8374506727ba6f5796eadd3292a1d3f0","datavalue":{"value":"10.1016/0012-365X(95)00226-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1357727$C2EC1645-3F0D-49FE-9ED0-F313215DD996","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"687235a95ab26b2e8d9084912376f7be2a335fe7","datavalue":{"value":{"entity-type":"item","numeric-id":1200108,"id":"Q1200108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1357727$3E801045-F126-4355-88F8-C1E0DB4321C6","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":"Q1357727$6049EACE-981E-46FB-8A90-2DAC1A018ED2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ad4ab8f37a90ca87e9ccd9974f355802c12e0ef2","datavalue":{"value":{"time":"+1998-01-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1357727$E2DA3E4D-D505-4278-8662-0985E5D552D5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"927ae2dbc41a469dc6a162f2070eb4ab2468326b","datavalue":{"value":"The author proves lower bounds for the circumference of 3- or 4-connected graphs in terms of their minimum neighbourhood union. Let \\(c(G)\\) be the circumference, i.e. the length of the longest cycle in \\(G\\), and let \\(\\text{NC} (G)\\) be the minimum cardinality of a neighbourhood union \\(N(x) \\cup N(y)\\), the minimum taken over all pairs of nonadjacent vertices \\(x,y\\). The author shows that if \\(G\\) is 3-connected, then \\(c(G)\\geq \\min (n,{3 \\over 2} (\\text{NC} (G)+1))\\) and if \\(G\\) is 4-connected, then \\(c(G) \\geq\\min (n,2 \\text{NC} (G))\\), thereby proving a conjecture of Faudree, Gould, Jacobson and Schelp. Both bounds are reached for infinitely many \\(G\\). The example of \\(K_{\\text{NC}, n-\\text{NC}}\\) shows that the second is sharp even for all possible pairs \\(n,\\text{NC}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1357727$B6988570-170F-498D-A67B-96466E56B384","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1357727$72D7A386-9566-4FB7-9D96-784752FCEC63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1357727$956F7620-044B-4BC3-959B-D021951B820C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2bdee5ce30444931062d7c648d105fae2314a23f","datavalue":{"value":"1021676","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1357727$A0A67045-90DC-477E-A282-0DD550766006","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47492577886a12b6d592b64b1bc764d6f0d6b391","datavalue":{"value":"degree bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1357727$8DF19C74-C666-4B2D-867E-99C33186C978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ad7f6c16e18413af432f8e820582fb2aa296646","datavalue":{"value":"hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1357727$B89DD8CC-0C46-45A9-9F75-CC1A1BF7BFFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24bb3b9099154c0f5a16d2b4a10fda71d3228c16","datavalue":{"value":"circumference","type":"string"},"datatype":"string"},"type":"statement","id":"Q1357727$7AECE63C-BCC0-4791-B20F-3466B9AC9097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7246ed7d7ae55ecb75b5f8eed2bfb076cb85ed57","datavalue":{"value":"neighbourhood union","type":"string"},"datatype":"string"},"type":"statement","id":"Q1357727$DAB3DFD1-AC0F-47DD-A858-864C07EC12BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7de25f5807e4027aac927c0536e26a3b6a8ab7f2","datavalue":{"value":"longest cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1357727$FEADFC13-0776-455C-8751-52A8C3A0B379","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"13b2797137908bf085ac37482e4ca3bd3f2ade57","datavalue":{"value":{"entity-type":"item","numeric-id":587716,"id":"Q587716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1357727$E2AA89F8-C231-4210-AF81-BEF7CC5FA9B0","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":"Q1357727$2CD21826-62EB-473E-8173-B355CADA257F","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":"Q1357727$3131DA20-9E3E-44D7-A2E5-818B5DFDE1EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c678a4d607ee7c59493765993ec168741685091b","datavalue":{"value":{"entity-type":"item","numeric-id":1313847,"id":"Q1313847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1357727$9BC7682D-5E34-42EC-B3D8-91F6323D6303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c01b126b8d9b1673d52182a74990a25669143a1c","datavalue":{"value":{"entity-type":"item","numeric-id":3353048,"id":"Q3353048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1357727$E556A5F8-1E1C-4DBB-90CD-BB9F5B3D92B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98182a04c9512ba980a243566647890aa36e6653","datavalue":{"value":{"entity-type":"item","numeric-id":3808117,"id":"Q3808117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1357727$74ECE4D8-AEB8-4229-A807-534E79DFD7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd1d495147f21f95f8fa890000fdfffb0f578052","datavalue":{"value":{"entity-type":"item","numeric-id":3680861,"id":"Q3680861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1357727$E9CB3F0E-7228-4D8F-BDDE-A5843648EE45","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b414db1a461a7668f5e3dde0fa0b3795aa784aa7","datavalue":{"value":{"entity-type":"item","numeric-id":2404386,"id":"Q2404386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7645569836fca838c3cd08c0e6bb39f7e3fae59d","datavalue":{"value":{"amount":"+0.8562759160995483","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":"Q1357727$16D46EEF-796C-413E-8A8C-446396A20033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea4e46c1ac9df2c2151f6dca25ca6b21417ca736","datavalue":{"value":{"entity-type":"item","numeric-id":5318242,"id":"Q5318242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2470bcd170144da13b90bb8e9e6c7d3a8b343be8","datavalue":{"value":{"amount":"+0.8441759347915649","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":"Q1357727$5216BBA2-B17C-4416-A8B7-D8AC1478ED8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbbd3a4758911eb452176081112f5a625faecad3","datavalue":{"value":{"entity-type":"item","numeric-id":1601399,"id":"Q1601399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"407feb35ec1343f514b4dd019a1349ffd5b43a48","datavalue":{"value":{"amount":"+0.8307108879089355","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":"Q1357727$6E40E3CA-EE02-4F05-8A8E-5FF7FCE3DBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef178fb8573bdfefd9f1a19b794d604f3e69d112","datavalue":{"value":{"entity-type":"item","numeric-id":1182981,"id":"Q1182981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ce993751c1e391206c6708f8cb483f05e04af0a","datavalue":{"value":{"amount":"+0.8306396007537842","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":"Q1357727$684F0802-E827-442B-8347-D56D9F73D930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69791e564765a38eac6afbe8893abb4b118427b9","datavalue":{"value":{"entity-type":"item","numeric-id":1309446,"id":"Q1309446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97f8e5164141eafeb3c9ce6031ec4db0669cceb7","datavalue":{"value":{"amount":"+0.8303882479667664","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":"Q1357727$07EF0CB4-E997-4E1B-A253-474434963B54","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds of length of longest cycles in graphs involving neighborhood unions","badges":[]}}}}}