Deploying Robots With Two Sensors in K1, 6‐Free Graphs
Abstract
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 to the vertices of G in such a way that for every and every vertex 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 07, 2015
- Source ID
- 10.1002/jgt.21898
Entities
People
- Chun‐Hung Liu
- Magnus Egerstedt
- Peter Whalen
- Robin Thomas
- Waseem Abbas
Organizations
- Georgia Tech
- National Science Foundation