Deploying Robots With Two Sensors in K1, 6Free Graphs Academic Article uri icon


  • 2015 Wiley Periodicals, Inc. Let G be a graph of minimum degree at least 2 with no induced subgraph isomorphic to K1, 6. We prove that if G is not isomorphic to one of eight exceptional graphs, then it is possible to assign two-element subsets of {1,2,3,4,5} to the vertices of G in such a way that for every i{1,2,3,4,5} and every vertex vV(G) the label i is assigned to v or one of its neighbors. It follows that G has fractional domatic number at least 5/2. This is motivated by a problem in robotics and generalizes a result of Fujita, Yamashita, and Kameda who proved that the same conclusion holds for all 3-regular graphs.

published proceedings

  • Journal of Graph Theory

author list (cited authors)

  • Abbas, W., Egerstedt, M., Liu, C., Thomas, R., & Whalen, P.

citation count

  • 10

complete list of authors

  • Abbas, Waseem||Egerstedt, Magnus||Liu, Chun‐Hung||Thomas, Robin||Whalen, Peter

publication date

  • January 2015