{"entities":{"Q1900523":{"pageid":1911265,"ns":120,"title":"Item:Q1900523","lastrevid":47361388,"modified":"2026-01-01T12:30:34Z","type":"item","id":"Q1900523","labels":{"en":{"language":"en","value":"Independent sets, cliques and hamiltonian graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 811348"}},"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":"Q1900523$81ED926E-3DFE-480E-996F-67024D873C13","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c83a3ef2747d8949ae4e5d4d21db947637ac4357","datavalue":{"value":{"text":"Independent sets, cliques and hamiltonian graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1900523$06E3423B-E921-44C1-98AF-BCC35407EC0E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8634704595c600c955644d6f2789b1a0c2818fad","datavalue":{"value":"0835.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900523$A7E1B0A2-CA65-45B5-870A-2F23610EF82A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa0925b3cbb2318c3d296089cd66cf2c98a30fdf","datavalue":{"value":"10.1007/BF01793014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900523$D218313B-07CC-4CBC-BF02-FBD1D56298EE","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":"Q1900523$86E48622-4105-4A88-AC2C-CA1550BC15D7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900523$B7A8D0FB-CC7A-4230-8735-349137520C0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df778dfa1d6f480f71e5d278ca30a57130511b0b","datavalue":{"value":{"time":"+1996-04-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1900523$17D40479-208B-40DB-92B3-F5000934B779","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c73810ba1952640c1c2c2f1b886d07780aea0e81","datavalue":{"value":"The author proves the following theorem: If \\(G\\) is a \\(k\\)-connected graph \\((k \\geq 2)\\) on \\(n\\) vertices, \\(V\\) is a clique in \\(G\\) and if for every essential independent set \\(S\\) (i.e. there are two vertices in \\(S\\) having a common neighbor in \\(G)\\) having \\(k + 1\\) vertices the intersection of \\(S\\) and \\(V\\) is nonempty then \\(G\\) is hamiltonian, or \\(G \\backslash \\{u\\}\\) is hamiltonian for some \\(u \\in V\\), or \\(G\\) is in one of three classes of exceptional graphs.   This theorem generalizes some results of Liu and Wei, Fan, Bondy, and Egawa and Saito. The proof breaks down into two stages. In the first stage the author proves that under the assumptions of the theorem having edges at certain places implies the absence of edges in other places (Lemmas 1, 2 and 3). In the second stage he uses the lemmas to show a number of claims leading to the results. These claims are globally proven as follows: first assume the contrary, then show that this invokes edges at some places, next use the lemmas to obtain non-edges in other places, and finally use these to construct large essential independent sets having empty intersection with \\(V\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900523$032BF3DD-984D-421D-8C12-1FF88AD13AF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900523$536FAB0C-3EF2-4C78-9C2F-725BF76A0C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900523$8686F84C-8235-4D67-84E0-A0209213934C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b4edea5834f9228f6951b7416b85869c0ab98634","datavalue":{"value":"811348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900523$81EEB033-6622-43DB-B52B-FF59F1D71424","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fb01ce46347c6a53a8a239241ecbaadc6180e80","datavalue":{"value":"hamiltonian graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900523$2578E9A4-1FA0-4EAE-98B1-E0E5CEA93DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7db98ba1ff0ce09c53ed23425466d036c9886140","datavalue":{"value":"essential independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900523$99670C03-E6CC-4E41-86D3-6EA85DC6E968","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"82ee0e57d3fff232270389401ab1bbddfcf580b6","datavalue":{"value":{"entity-type":"item","numeric-id":592369,"id":"Q592369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900523$D8B37904-468E-4694-9E8B-E46A4AAFC639","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":"Q1900523$D122F52F-AA39-4F25-ACEF-C98823B29B85","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"554ad17cb48f9b597e940e21315e69534da9251a","datavalue":{"value":{"entity-type":"item","numeric-id":4196453,"id":"Q4196453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900523$03E9CC5B-ECFB-4506-9555-EF368C01E9AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ee4b5aec7c57f1369b27ad508e8d6185d4489d","datavalue":{"value":{"entity-type":"item","numeric-id":2551113,"id":"Q2551113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900523$FE2562D8-2B39-4F60-A77F-FB307B22BC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0af97c5d1309395cd1a0cc77b905a28027b1e02d","datavalue":{"value":{"entity-type":"item","numeric-id":801082,"id":"Q801082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900523$D27ABC34-A7A0-4863-A0FC-A7D0B3185025","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"58693af6e9fa8e9566b6ae4db7390d59c499ced9","datavalue":{"value":"https://doi.org/10.1007/bf01793014","type":"string"},"datatype":"url"},"type":"statement","id":"Q1900523$B109BD37-7272-4990-AA56-7F16A212354B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"19ba5019691d4de587777028d88fd8df462b1647","datavalue":{"value":"W2052598659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900523$4B80B51E-F0D0-4090-A04E-0403FF377AA4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa22bf924d7f33957354f127239f221dfcf53254","datavalue":{"value":{"entity-type":"item","numeric-id":4865533,"id":"Q4865533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15eefc5f51291ea5451d7240d76e7d831de5cdbf","datavalue":{"value":{"amount":"+0.8406788110733032","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":"Q1900523$431D120B-67F6-47B9-94FF-5667DB2AD974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51b896bc7747c33dee919a0666a77524f25bf9fb","datavalue":{"value":{"entity-type":"item","numeric-id":4374722,"id":"Q4374722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdb8ecea779deba4eaaae6638598d8025a516295","datavalue":{"value":{"amount":"+0.8401469588279724","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":"Q1900523$48B35282-0D98-4ECA-AF1D-EC7DFC057EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99c9cff24d1effb9a5c0417297ca884c093bb861","datavalue":{"value":{"entity-type":"item","numeric-id":4940092,"id":"Q4940092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eca87422cea849cc9dbf2c15e10f8b45ddc9171","datavalue":{"value":{"amount":"+0.837989091873169","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":"Q1900523$84B556A5-96E3-4892-B228-C5AA73F4329B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"164e8d16ef958c6bff321c4a65d30ae85ff1a940","datavalue":{"value":{"entity-type":"item","numeric-id":4830390,"id":"Q4830390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa812ae23d37c7fad67db0b98b8c57d48c6012b0","datavalue":{"value":{"amount":"+0.8246315121650696","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":"Q1900523$6639C6A9-9E19-4D00-975F-33B79D8C8CB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b2a8258e3bb0b63fcc7ecf9f7a6b465015c26c8","datavalue":{"value":{"entity-type":"item","numeric-id":1357748,"id":"Q1357748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0952da200bf0319dd9f871d6a9b59667953ee2f7","datavalue":{"value":{"amount":"+0.820946455001831","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":"Q1900523$0E30D8F3-3696-4D9C-954D-69ED933E52F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1900523","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1900523"}}}}}