Deploying robots with two sensors in K1, 6-free graphs

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

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

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 {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 v∈V(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.

Original languageEnglish (US)
Pages (from-to)236-252
Number of pages17
JournalJournal of Graph Theory
Volume82
Issue number3
DOIs
StatePublished - Jul 1 2016

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • K-free
  • domination
  • fractional domatic number

Fingerprint

Dive into the research topics of 'Deploying robots with two sensors in K1, 6-free graphs'. Together they form a unique fingerprint.

Cite this