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 journalArticle

6 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 K<sub>1, 6</sub>-free graphs'. Together they form a unique fingerprint.

  • Cite this

    Abbas, W., Egerstedt, M., Liu, C. H., Thomas, R., & Whalen, P. (2016). Deploying robots with two sensors in K1, 6-free graphs. Journal of Graph Theory, 82(3), 236-252. https://doi.org/10.1002/jgt.21898