{"entities":{"Q1175986":{"pageid":1186735,"ns":120,"title":"Item:Q1175986","lastrevid":47042464,"modified":"2025-12-31T11:53:34Z","type":"item","id":"Q1175986","labels":{"en":{"language":"en","value":"Stable properties of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 13099"}},"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":"Q1175986$57F7837D-532D-4DCF-8263-EB63FE2AB867","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14eb48cdada95d2837605bd93b68046700d4fe01","datavalue":{"value":{"text":"Stable properties of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1175986$FE6B69BA-BBB6-4B00-BD53-0497CF087004","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09eb2e17eebc61e26b83106300b6a736e64d52de","datavalue":{"value":"0749.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$EA9C5EE4-5B8F-4BBE-B6F4-28D2D787BAA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9122e3b3be12059eed96341175ec0ac80dd9c4f1","datavalue":{"value":"10.1016/0012-365X(91)90352-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$BFCF7F4F-7368-48E9-B55F-7D3D26AF3FE8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b17683dd2eedd3f1d821a1087aa218b2b31d17","datavalue":{"value":{"entity-type":"item","numeric-id":1160451,"id":"Q1160451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$4BA125E0-85B0-4EF3-A004-743E7EC781FC","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":"Q1175986$4322B0D3-01FE-468D-8AD3-FC94192F0AEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1175986$77DDBD30-15A9-449F-A208-7B977D15C9F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"499449ef073295eb2d0dbaa9c7ecf0a3d42c642a","datavalue":{"value":"Local generalizations of some results obtained by \\textit{J. A. Bondy} and \\textit{V. Chvatal} in [Discrete Math. 15, 111-135 (1976; Zbl 0331.05138)] are presented.   Let \\(d_ G(u,v)\\) be the distance between vertices \\(u\\) and \\(v\\) in a graph \\(G\\). Then for any \\(u\\in V(G)\\) we denote by \\(N^ k_ G(u)\\) and \\(M^ k_ G(u)\\) the sets of all \\(v\\in V(G)\\) with \\(d_ G(u,v)=k\\) and \\(d_ G(u,v)\\leq k\\), respectively. The property \\(P\\) is \\((k,r)\\)-stable, \\(k\\geq 2\\), if whenever \\(G+uv\\) has property \\(P\\) and  \\[ d_ G(u)+d_ G(v)\\geq| M^ k_ G(u)|+| N_ G^{k+1}(u)\\cap N^ 1_ G(v)|+r\\tag{1} \\]  then \\(G\\) itself has property \\(P\\).   Theorem 1. The property of containing of a hamiltonian cycle is (2,0)- stable.   \\(A (k,r)\\)-closure of \\(G\\) is a graph obtained from \\(G\\) by recursively joining pairs of nonadjacent vertices satisfying the condition (1). A graph is constructed in which the \\((k,r)\\)-closure is not unique.   Theorem 2. For every \\(n\\geq 6\\) there is a graph \\(G\\) such that \\(| V(G)|=n\\), \\(| E(G)|=2n-3\\) and \\(K_ n\\) is a (2,0)-closure of \\(G\\).   Theorem 3. Let \\(G\\) be a 2-connected graph of order \\(n\\), \\(n\\geq 3\\), and let \\(u\\) and \\(v\\) be distinct vertices of \\(G\\). If \\(d_ G(u,v)=2\\) implies \\(\\max\\{d_ G(u),d_ G(v)\\}\\geq{n\\over 2}\\), then \\(K_ n\\) is a (2,0)- closure of \\(G\\).   Furthermore, it is shown that the property of containing a cycle \\(C_ s (C_{2t})\\) is \\((2,n-s)\\)-stable \\(((4,n-s-1)\\)-stable), the property of containing a path \\(P_ s\\) is \\((4,-1)\\)-stable and \\((2,0)\\)-stable, the property of being \\(s\\)-edge-hamiltonian is \\((2,s)\\)-stable, the property of being \\(s\\)-hamiltonian is \\((2,s)\\)-stable, the property of being \\(s\\)- hamiltonian-connected is \\((2,s+1)\\)-stable, the property of containing \\(K_{2,s}\\), the property of being \\(s\\)-connected and the property of being \\(s\\)-edge-connected are \\((2,s-2)\\)-stable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1175986$0A4F9E10-6741-496C-9613-94E917E05256","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$C86F3149-2AF1-4DB1-A770-188F6C2BE6F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$DAC06244-F3FC-477D-A628-A96C77F3F94F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$40F571C4-8324-4039-B8DA-29E988308EC3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"723745e8f90f6e891db49a5f27dad4c5ff73048c","datavalue":{"value":"13099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$938A3AF3-3933-40D7-B1D2-9E5D23F0F237","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34b44e7b40021effdee26093512bde7058814281","datavalue":{"value":"stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1175986$C19149D8-6D67-477C-9249-F7F3180D75EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2955d3dde9a15e46dba801e05da2cd70a0c42a19","datavalue":{"value":"closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1175986$64A312E2-6997-4A6F-BDD1-64F521FC598F","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":"Q1175986$A4E6AA89-8EB9-4BDF-AAF3-21812368EA4C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$E5298622-DB85-4CC6-A5A1-B7CAC8FB7373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd492719f080c59c4dd23730fc178cf5a672a45","datavalue":{"value":{"entity-type":"item","numeric-id":1227760,"id":"Q1227760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$024C6DD7-3C94-434E-9C3E-C2C232B8D69B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5318786b6f6e3e7c3a90aeb58ebfd7f262125c23","datavalue":{"value":{"entity-type":"item","numeric-id":5604410,"id":"Q5604410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$6C8FFD21-1894-484B-848D-1F18AAD1C35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fbb5ee59c3c5fba8b68dc26e64c473270f6227","datavalue":{"value":{"entity-type":"item","numeric-id":2545100,"id":"Q2545100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$66431635-D6C4-4521-8902-D2C020C580D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca23bc5873f26659a0a5615436b9ce100c705e81","datavalue":{"value":{"entity-type":"item","numeric-id":1146691,"id":"Q1146691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$A1567341-3C15-451C-9ED0-A9CF010FBBB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$8AA4DE2C-323A-4CB6-9BBF-99AD1AEA2882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$895D6EC8-0F61-44C5-B02B-C1B23C4ACD96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98e94f48f484608988ed586f06f8fbc5355f15ae","datavalue":{"value":{"entity-type":"item","numeric-id":5578810,"id":"Q5578810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$CC17A46F-67ED-4580-B9D6-77BD90AEE791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"154fa6844acbd96e37acafcf8bea29137f7943c8","datavalue":{"value":{"entity-type":"item","numeric-id":5625199,"id":"Q5625199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$F5410290-A232-45D8-84FB-CABD37220D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0d9c586ef9cf53af881c9950417cc5b66679aa","datavalue":{"value":{"entity-type":"item","numeric-id":3264678,"id":"Q3264678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1175986$740EADE0-9284-4353-A84C-F657E842702B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d2260c2b43071bed3f2a4e06a1661677ed314bf9","datavalue":{"value":"https://doi.org/10.1016/0012-365x(91)90352-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1175986$6CC4E2AC-320C-4F58-AD29-C734E21C2ACA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a6e52ef8f8fb6a127a9f56cd276874703db8c112","datavalue":{"value":"W2069885079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1175986$494D2B98-ECB6-45E6-B99D-9D165F9E88D7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c78038f3dfc0085f3bcc5a18dbe4bc0b063e7e74","datavalue":{"value":{"entity-type":"item","numeric-id":1174165,"id":"Q1174165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d8c1e2065913c8329c1d00a7bee226618b386ad","datavalue":{"value":{"amount":"+0.8398950695991516","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":"Q1175986$0E814971-3883-4FC7-86DA-89331DC63368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eb2174a6418ca8a3988b97123c8fb4e2da22470","datavalue":{"value":{"entity-type":"item","numeric-id":1422413,"id":"Q1422413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"176ee03fc5105c94fd0b00da25accc4903718dd4","datavalue":{"value":{"amount":"+0.8362200856208801","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":"Q1175986$D2E38780-82A2-444B-B993-328657860010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad281f43e9f01c3e45ab29d65e60906196008dbf","datavalue":{"value":{"entity-type":"item","numeric-id":3474676,"id":"Q3474676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0198a22407b9cc9afcb1ff345caf960f90a87be7","datavalue":{"value":{"amount":"+0.8360146880149841","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":"Q1175986$27F5D71D-5D3D-4B13-A008-AEBBE85D41A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60649c5c3b95687a31d07808836c7d6a012babd0","datavalue":{"value":{"entity-type":"item","numeric-id":3137765,"id":"Q3137765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05ee12b531df8499d332053397df053b53b27443","datavalue":{"value":{"amount":"+0.8277391791343689","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":"Q1175986$4C03837C-94F3-4C49-BC20-CEE9E169B47A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"174ac2d8ad78061f45573dbfa1ba14a2569dca17","datavalue":{"value":{"entity-type":"item","numeric-id":1972320,"id":"Q1972320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13643add3049237b34778ad483a03af3989eff06","datavalue":{"value":{"amount":"+0.8208544254302979","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":"Q1175986$2C41949A-5874-41E2-8885-E718720086D3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1175986","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1175986"}}}}}