Pushpa Publishing House

Journal Menu

Content

Volume 42 (2025)

Volume 41 (2024)

Volume 40 (2023)

Volume 39 (2023)

Volume 38 (2023)

Volume 29 (2022)

Volume 28 (2021)

Volume 27 (2021)

Volume 26 (2021)

Volume 25 (2020)

Volume 24 (2020)

Volume 23 (2020)

Volume 22 (2019)

Volume 21 (2019)

Volume 20 (2019)

Volume 19 (2018)

Volume 18 (2017)

Volume 17 (2016)

Volume 16 (2015)

Volume 15 (2015)

Volume 14 (2014)

Volume 13 (2014)

Volume 12 (2013)

Volume 11 (2013)

Volume 10 (2012)

Volume 7 (2011)

Volume 6 (2010)

Volume 5 (2010)

	Volume 5, Issue 2 Pg 85 - 169 (April 2010)
	Volume 5, Issue 1 Pg 1 - 83 (January 2010)

Volume 4 (2009)

Volume 3 (2009)

Volume 2 (2008)

Volume 1 (2008)

-->

Advances and Applications in Discrete Mathematics

of a graph G is the smallest number of searchers required to clear G. A search strategy is connected if the set of clear edges always forms a connected graph. Let

denote the minimum number of searchers required to use a connected search strategy to clear a graph G. A graph is unicyclic if it contains at most one cycle. Barriére et al. [1] posed an open problem: there exists a constant

such that

for a graph G. In this paper, we prove that

for any unicyclic graph, which extends Barriére et al. [1] result. Next, one naturally asks how to characterize

for a graph G. In this paper, we investigate trees and unicyclic graphs and prove that for a tree, there exists one obstruction and for a cyclic graph, there exist four obstructions.

Advances and Applications in Discrete Mathematics
Volume 5, Issue 1, Pages 37 - 50 (January 2010)

CONNECTED GRAPH SEARCHING FOR UNICYCLIC GRAPHS
Brian Alspach, Denis Hanson and Xiangwen Li

Abstract:
The graph searching problem was introduced by Parsons. A graph searching consists of a sequence of operations: place a searcher, move a searcher along an edge and remove a searcher from a vertex. The purpose of graph searching is to reach a state in which all the edges are simultaneously clear. The search number

of a graph G is the smallest number of searchers required to clear G. A search strategy is connected if the set of clear edges always forms a connected graph. Let

such that

for a graph G. In this paper, we prove that

for any unicyclic graph, which extends Barriére et al. [1] result. Next, one naturally asks how to characterize

for a graph G. In this paper, we investigate trees and unicyclic graphs and prove that for a tree, there exists one obstruction and for a cyclic graph, there exist four obstructions.

Keywords and phrases: graph searching, graph minor, search number.

Number of Downloads: 276 | Number of Views: 1037