dc.contributor |
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV |
dc.contributor |
Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
dc.contributor.author |
Barrière Figueroa, Eulalia |
dc.contributor.author |
Flocchini, Paola |
dc.contributor.author |
Fomin, Fedor V. |
dc.contributor.author |
Fraigniaud, Pierre |
dc.contributor.author |
Nisse, Nicolas |
dc.contributor.author |
Santoro, Nicola |
dc.contributor.author |
Thilikos Touloupas, Dimitrios |
dc.date |
2010-09-26 |
dc.identifier.uri |
http://hdl.handle.net/2117/9116 |
dc.language.iso |
eng |
dc.rights |
Attribution-NonCommercial-NoDerivs 3.0 Spain |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Seguretat informàtica |
dc.subject |
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs |
dc.subject |
Computer networks--Security measures |
dc.subject |
Graph theory |
dc.subject |
Graph searching |
dc.subject |
Cops-and-robbers |
dc.subject |
Network security |
dc.subject |
Seguretat informàtica |
dc.subject |
Grafs, Teoria de |
dc.title |
Connected graph searching |
dc.type |
info:eu-repo/semantics/draft |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
In graph searching game the opponents are a set of searchers and a fugitive in a graph.
The searchers try to capture the fugitive by applying some sequence moves that include
placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture
by moving along unguarded paths. The search number of a graph is the minimum number
of searchers required to guarantee the capture of the fugitive. In this paper, we initiate
the study of this game under the natural restriction of connectivity where we demand that
in each step of the search the locations of the graph that are clean (i.e. non-accessible to
the fugitive) remain connected. We give evidence that many of the standard mathematical
tools used so far in the classic graph searching fail under the connectivity requirement. We
also settle the question on “the price of connectivity” that is how many searchers more
are required for searching a graph when the connectivity demand is imposed. We make
estimations of the price of connectivity on general graphs and we provide tight bounds
for the case of trees. In particular for an n-vertex graph the ratio between the connected
searching number and the non-connected one is O(log n) while for trees this ratio is always
at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for
all graphs. Our combinatorial results imply a complete characterization of connected graph
searching on trees. It is based on a forbidden-graph characterization of the connected search
number. We prove that the connected search game is monotone for trees, i.e. restricting
search strategies to only those where the clean territories increase monotonically does not
require more searchers. A consequence of our results is that the connected search number can
be computed in polynomial time on trees, moreover, we show how to make this algorithm
distributed. Finally, we reveal connections of this parameter to other invariants on trees
such as the Horton-Stralher number. |