{"entities":{"Q2848728":{"pageid":2859448,"ns":120,"title":"Item:Q2848728","lastrevid":42266407,"modified":"2025-06-03T22:23:19Z","type":"item","id":"Q2848728","labels":{"en":{"language":"en","value":"Even time constraints on the watchman's walk"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6212179"}},"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":"Q2848728$FEE5D58C-EFCA-45F3-8002-386E6CD17E50","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2664a910116410b84836d72c2ef4e776f2dee6bc","datavalue":{"value":"1294.05096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$22C4427D-1859-4313-879C-5094A371D5C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"43e878d8f753446abefa1b1ceb0637b91afae47a","datavalue":{"value":{"time":"+2013-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2848728$2528A662-C8E9-4575-8D9B-A778ECE69A2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$D93ED378-04AC-4595-9D7E-DAD4D1A45423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$0F9A8FEE-010A-44AD-816F-46332A09FC4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$2532CE37-48C3-4C75-8C77-85BFC19D03FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$ED6E0469-1D4E-4408-A51F-51CCE6FE247B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b02a47bb3e6ffda6ae8940845178eca3854c8d36","datavalue":{"value":"05D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$A722B165-601E-41E6-BBE2-A09C3BC264B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6cb186f7c907ca60893d849df7e69a98dd343f1b","datavalue":{"value":"90B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$562BA312-44BF-4A37-AD1C-7C4B816C5063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$F899B276-3F1E-44B5-A500-8EA4EB8C7914","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97478f7f73215f1579e3e76d6643c718e7b36757","datavalue":{"value":"6212179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848728$4A4FE7E0-0E80-409B-9CE7-28EB224134FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62f0a460613792c7b1d98ca7c82b87b4b903b963","datavalue":{"value":"rooted tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848728$22EA65AE-FD0F-4610-B7CA-689F24BB461D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848728$4CB06A02-7D53-4219-A609-95914ED4BB94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a369f8ad164245ac9ca87a2d0cf5ed0c7841597","datavalue":{"value":"dominating walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848728$7B985F45-C41B-4EE8-B3A3-A6D604261EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6319975fe5c06908e7aa95c318ae12e00be61b77","datavalue":{"value":"watchman's walk problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848728$E37961FC-581D-4FC9-843D-011952D8FA13","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":"Q2848728$01F7F784-2B43-44F6-AC22-94FF6440778E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edbfd23daf34571c9d871814329d64c9f966f66e","datavalue":{"value":{"entity-type":"item","numeric-id":2906847,"id":"Q2906847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ffb2e9dc4b11ac2b9983cf585cddf6556c937b3","datavalue":{"value":{"amount":"+0.82966095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$DE7982D4-3361-4E62-B47E-CA37B2E5658E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f9e3195bcd1e363333ba9e29fb12710efb704c7","datavalue":{"value":{"entity-type":"item","numeric-id":2062673,"id":"Q2062673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04bbd063c4e7cf4ae60ad15d95f63ed86c9ced99","datavalue":{"value":{"amount":"+0.81956255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$B6611E59-258F-4A49-9E08-6332FFA9A9A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18d947f7b015c255a0dbcf8d81d490ab52b6352f","datavalue":{"value":{"entity-type":"item","numeric-id":5000299,"id":"Q5000299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4a580d950864f0159badd5d37835986ae849fed","datavalue":{"value":{"amount":"+0.75626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$81B44C8D-2581-4056-B5B8-188FD104055B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2687aa5df97f2a0dd6c164abd4c9037b659bd3bc","datavalue":{"value":{"entity-type":"item","numeric-id":5461685,"id":"Q5461685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5b3c25e59eee06bb53c8fd9ddc229e1a31f8e25","datavalue":{"value":{"amount":"+0.74329793","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$B5AFABF1-A23A-497F-95ED-E45C6E3F93AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"823ff897b0249209cee57833b3b9912948f22feb","datavalue":{"value":{"entity-type":"item","numeric-id":496659,"id":"Q496659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d39fae86b6db9311390560cd4e841fc29293519","datavalue":{"value":{"amount":"+0.7376913","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$A020280E-C570-4E9D-972C-CCE4862A967E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c5db885547b1815db385c539c7ca10729acbc8d","datavalue":{"value":{"entity-type":"item","numeric-id":2971261,"id":"Q2971261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e1467aa685cf82c7aa7b0433757835dd9c562b3","datavalue":{"value":{"amount":"+0.73555994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$6F0A184C-1A9C-40D8-A0AB-AA1F49A2CE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d60202ea256d63d100f3ae35bb2ee8ae514a33e6","datavalue":{"value":{"entity-type":"item","numeric-id":4826173,"id":"Q4826173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50698f4903a867c4cec61375ee7d3ca3fffc594b","datavalue":{"value":{"amount":"+0.7353058","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$2DF6F093-8995-4464-BD3B-325E1A76D160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e9bb833c580eac5437270ccf1930b1ddaa0677a","datavalue":{"value":{"entity-type":"item","numeric-id":4800271,"id":"Q4800271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c95fafd01891d72f9391689be1a1c387261ce877","datavalue":{"value":{"amount":"+0.72246295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$973D42EA-8A86-4E12-8F21-433F22B7E42C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5e75b7ef2b11e0e0a93bbb42603f44d64c1a88e","datavalue":{"value":{"entity-type":"item","numeric-id":3514293,"id":"Q3514293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d66a4bdfeacb84035ec64ca43d9c93af46f9a95e","datavalue":{"value":{"amount":"+0.7198413","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$D25D552D-EDB8-4CC5-A3CF-8A68D5AB731E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63237e06d21b48a10631fb40b2d8710aeca5df05","datavalue":{"value":{"entity-type":"item","numeric-id":3424010,"id":"Q3424010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"686f1fcc80aef15a5cdfcf566c1ebf531cfdf33c","datavalue":{"value":{"amount":"+0.71523976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848728$4CA018C4-C564-4925-958E-2241155204AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34200479e43908aaa895f0f54f4521a446290b2c","datavalue":{"value":{"entity-type":"item","numeric-id":2227986,"id":"Q2227986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848728$1585954D-A940-4F14-8E0E-29A76261D565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"694592c307693f62345c3350ae938818c8badb8d","datavalue":{"value":{"entity-type":"item","numeric-id":6772912,"id":"Q6772912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848728$4D26B233-77FF-48D0-9411-949B28E56271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3eab4d497d196ed3677a17590fd949caf867373","datavalue":{"value":{"entity-type":"item","numeric-id":244921,"id":"Q244921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848728$2D0CE07F-6403-4E3A-908A-7C7E8A340C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b856bc7c612cbe99d014974b8179f54114e4a5e9","datavalue":{"value":{"entity-type":"item","numeric-id":494426,"id":"Q494426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848728$DDE41B62-0987-4B59-A3D4-7EAFDBCC2C61","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c4addecb2045be6a208aeae3c00f1bae7101557","datavalue":{"value":{"text":"Even time constraints on the watchman's walk","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2848728$B191ECB7-E275-4CBB-9FB5-F33BE399810F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4475e942e511a8e1762a91638eb522e6040025ba","datavalue":{"value":{"entity-type":"item","numeric-id":6562416,"id":"Q6562416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848728$4E67BF79-7DF4-4632-B3DA-BF53CCEB0EA9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ddb256501d22dc24ae073bafdbe764481c8a0ff","datavalue":{"value":"The watchman's walk problem for a given graph \\(G\\) (representing a building) is stated as follows. At time \\(i=0\\), a number of guards are initially placed on vertices of \\(G\\) (representing the rooms of the building), more than one guard allowed on a vertex at a time. With each increment \\(i:=i+1\\) of discrete time, each guard either stays on the same vertex, or shifts onto an adjacent (neighboring) vertex. The guards are said to \\(t\\)-monitor \\(G\\) provided that for each vertex \\(v\\) of \\(G\\), and any nonnegative integers \\(k\\) and \\(t\\), some guard shows up in the close neighborhood of \\(v\\) at some time \\(i \\in \\{ k, k+1, \\ldots, k+t \\}\\). The watchman's walk problem is the problem of finding the least number of guards, denoted \\(W_t(G)\\), sufficient for \\(t\\)-monitoring of \\(G\\). It is easy to observe that \\(W_0(G)\\) is equal to the domination number \\(\\gamma(G)\\), which is at most half of the order of \\(G\\).NEWLINENEWLINEThe main result of the paper under review is that \\(W_t(T) \\leq \\lfloor \\frac {2n+t-2}{t+3} \\rfloor\\) for any even integer \\(t > 0\\) and any tree \\(T\\) on \\(n \\geq 3\\) vertices. This proves in the affirmative a recent conjecture due to \\textit{D. Dyer} and \\textit{R. Milley} [Australas. J. Comb. 53, 97--108 (2012; Zbl 1256.05167)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848728$048584A8-CBDE-4238-BB47-8C7F1E742BB4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d954a68edf0d8701e0810168bf45596d167285bb","datavalue":{"value":{"entity-type":"item","numeric-id":917980,"id":"Q917980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848728$6CA99CA0-0467-4793-A29E-6E23682C7DEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2848728","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2848728"}}}}}