Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649136 | Discrete Mathematics | 2010 | 11 Pages |
Abstract
We consider edge critical graphs when playing cops and robber. Specifically, we look at those graphs whose copnumbers change from one to two when any edge is added, deleted, subdivided or contracted. We characterize all such sets, showing that they are empty, trees, all 2-edge-connected graphs and empty, respectively. We also consider those graphs which change from copnumber two to one when any edge is added, and give a characterization in the k-regular case.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
N.E. Clarke, S.L. Fitzpatrick, A. Hill, R.J. Nowakowski,