{"entities":{"Q1108291":{"pageid":1119040,"ns":120,"title":"Item:Q1108291","lastrevid":49202971,"modified":"2026-01-06T18:28:36Z","type":"item","id":"Q1108291","labels":{"en":{"language":"en","value":"On bridged graphs and cop-win graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4066940"}},"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":"Q1108291$490F817A-3327-4562-BC91-36E089821D3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53a8df3a7b0f70b635dbff2697d89b776a87bbb8","datavalue":{"value":{"text":"On bridged graphs and cop-win graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108291$FC3E3211-8A47-4779-9A9A-4F8BE3BCC8BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bf9b6fe063f43529b80b6503f249462415792aa9","datavalue":{"value":"0654.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108291$9B9944B6-DE74-461F-877D-E023F0AA4FA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7753f4292414e24c2425b1b39c95f0b3e20291b9","datavalue":{"value":"10.1016/0095-8956(88)90093-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108291$2F47D218-D2B1-41AF-8A73-017AD1ED01B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4279505aca0e053329b78fa731a2e6a34ac80564","datavalue":{"value":{"entity-type":"item","numeric-id":686242,"id":"Q686242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$5EE1507D-05A4-403A-A44C-BB6B16169A3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c7a09266880b9246b87f74318f3fac418e3fcad","datavalue":{"value":{"entity-type":"item","numeric-id":489296,"id":"Q489296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$F520D29F-00D6-4A27-9F3A-670687EEDEC5","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":"Q1108291$3C90C7CA-EAA5-4B10-A747-5A09409F646B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1108291$AD89F4A6-0A64-48E2-A2B8-F92BD4CD5CC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f04421d072535498e87654ebaf6c92b51147b416","datavalue":{"value":"A graph is bridged if each its cycle of length \\(n\\geq 4\\) contains a shortcut. It is possible to play on graphs a game of a cop and robber. The cop begins by selecting and occupying a vertex and then the robber does likewise. They then move alternately. Either one can remain in his place or move to any adjacent vertex. The cop wins when both players occupy the same vertex. A graph is cop-win [a definition of R. Nowakowski and P. Winkler, 1980; see also the paper of \\textit{R. Nowakowski} and \\textit{P. Winkler} in Discrete Math. 43, 235-239 (1983; Zbl 0508.05058] if the cop has a winning strategy.    The main result gives the theorem: Every nontrivial component of a bridged graph contains a pair of vertices such that the neighborhood of the first vertex is a subset the neighborhood of the second one. The relationship between bridged graphs and cop-win graphs gives e.g. the statement: A connected graph \\({\\mathcal G}\\) is bridged iff every isometric subgraph of \\({\\mathcal G}\\) (including \\({\\mathcal G}\\) itself) is cop-win.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$8F1B9F8B-DAFC-40CA-9293-CCFDA5F628C9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebe4d44a08a58073803722e37fc039de15c45af0","datavalue":{"value":{"entity-type":"item","numeric-id":761465,"id":"Q761465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$0EB028C5-F908-40F5-82B6-1A7E9DDF3341","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108291$B66D3BD3-FD90-46DE-87C5-8AAA7B49A6E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"35c761fe28b3b8cffa37d43933bc40cd900ea62e","datavalue":{"value":"4066940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108291$06948C79-CCB2-4D15-810C-A4054D948583","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d50f97acb9e65c8ab69f67e672bd46ef49bd3023","datavalue":{"value":"universal vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$3D426940-5BEA-46BB-9358-BBE4AE50DF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"853bd0b31f9734652041500f2e432a6c8df42e70","datavalue":{"value":"chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$A3D605C8-4CB3-40FF-9FF4-236781E55222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac7a4ed381aa033efc2d2f60e143bbae022b2b56","datavalue":{"value":"modular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$1F0A4D1F-54C3-4CC8-9A70-1BD0A3ABB264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5b44d50b09e6195fc107c4288d1b6ec25fd05d","datavalue":{"value":"simplicial vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$557CF3AD-8908-4A63-8AB1-3EDCB238123B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5c1eae037b0d94549c1a0c983a4f1dd312d7d5b","datavalue":{"value":"geodesically convex set in graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$8185AB1E-9030-4C61-A23A-C0E2BD4D43D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18a18d72fc0a7767680b56415fccedd4f844fa62","datavalue":{"value":"bridged graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$A6282EBD-0775-4885-B695-40F1CAEB3940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86ee83de8facebb65102c790fd64020df9a6320a","datavalue":{"value":"cop-win graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$5C23EC4C-6CEA-4311-AAE4-2AE180B574D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"691c6079d895a302c8561fe33ccaf06d10bb18fa","datavalue":{"value":"isometric subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108291$9B12E824-1B6D-4CC6-B300-44C29F474C3C","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":"Q1108291$0C5353B1-2160-42B1-B33D-5C0A2D103D25","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f81c2944a0574af3e9ed204de28b81dbf4786029","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90093-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108291$D8E67603-D05C-4B4F-80FD-6D8550E61D7A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a318f25a09833afa289ed609bfb647265019905d","datavalue":{"value":"W2987990768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108291$2ADFC100-B8F4-4C22-9AEF-787F445CC252","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"131ad416a91c23576445cd8e6bad8f29c3529ef5","datavalue":{"value":{"entity-type":"item","numeric-id":1106237,"id":"Q1106237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$A0E57C20-7FCA-41EE-92D1-C82EAB53980D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1fc23e3fdbc14d592d2bb540feda88d75a3ba44","datavalue":{"value":{"entity-type":"item","numeric-id":3718757,"id":"Q3718757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$9A5E3D86-E84F-4B6B-B61E-154CA4771557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8405aa904e38bb5fa3399eea83335480ed434943","datavalue":{"value":{"entity-type":"item","numeric-id":1089354,"id":"Q1089354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$2AFECC67-8302-4658-8337-281CB47FB6AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e343f5aacbf9986c327c937a46218eb6d8e8361","datavalue":{"value":{"entity-type":"item","numeric-id":1099187,"id":"Q1099187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$CF514A58-8E21-4EC9-9641-5ADB9E86540E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd7542caac5915c8f63a224b76605abf20c2235","datavalue":{"value":{"entity-type":"item","numeric-id":1837707,"id":"Q1837707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$EDE17245-4269-4301-BCF3-E133097B1759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"428f44a83195b6a9223bfdab9ba2b957eb63e886","datavalue":{"value":{"entity-type":"item","numeric-id":3677791,"id":"Q3677791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108291$AA0DC800-A0B7-4D6A-AF6D-2673AC859AB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe15bef3eaabfb4dadcc64e0d6f7f3a267126c29","datavalue":{"value":{"entity-type":"item","numeric-id":1354123,"id":"Q1354123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"669ddcc7aac0142b95e645fbf9a2e95d8826a58e","datavalue":{"value":{"amount":"+0.9202628135681152","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":"Q1108291$D4895D24-F2E8-40CB-9FF6-D16733273566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2086b13f6a1f22f9695513e1953c723932a7a7ed","datavalue":{"value":{"entity-type":"item","numeric-id":1325748,"id":"Q1325748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7010facfa20620fe18109084befd3e1ed470c7c","datavalue":{"value":{"amount":"+0.9187287092208862","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":"Q1108291$7CD5B17A-E38E-425F-BF72-731DE524EC5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3d19627555a46c7a7da795d901c3ec4305a17d3","datavalue":{"value":{"entity-type":"item","numeric-id":1850039,"id":"Q1850039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e421fd3deccf58763671d99b9cae246eefb87eb6","datavalue":{"value":{"amount":"+0.8704689145088196","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":"Q1108291$665A58C5-D6D0-4E8F-8CF1-604B15960FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf74a69d5d59ffe0348f27cef2f87d44dff1f0e6","datavalue":{"value":{"entity-type":"item","numeric-id":1586757,"id":"Q1586757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74bdda62625634c7efcfbe14e9ef08c78f68a313","datavalue":{"value":{"amount":"+0.8199875354766846","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":"Q1108291$7EC94B07-CB05-46A4-A63F-7C604732FDAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01515666dd1649175a6b40946766c4a292551be8","datavalue":{"value":{"entity-type":"item","numeric-id":1827690,"id":"Q1827690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6565530738922e0c4cd6285e7594ff94185be89","datavalue":{"value":{"amount":"+0.809856116771698","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":"Q1108291$2DC6E915-C5FD-4454-BC3E-AEDF134B5BC1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1108291","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1108291"}}}}}