Name
Abstract | ||
|---|---|---|
Let G be a graph of minimum degree at least 2 with no induced subgraph isomorphic to K-1,K-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 is an element of {1, 2, 3, 4, 5} and every vertex v is an element of 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. (C) 2015 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/jgt.21898 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
K-1,K-6-free,fractional domatic number,domination | Artificial intelligence,Robotics,Domatic number,Topology,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Induced subgraph,Isomorphism,Fujita scale,Robot,Mathematics | Journal |
Volume | Issue | ISSN |
82.0 | 3.0 | 0364-9024 |
Citations | PageRank | References |
6 | 0.51 | 2 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Waseem Abbas | 1 | 87 | 20.68 |
| Magnus Egerstedt | 2 | 2862 | 384.94 |
| Chun-hung Liu | 3 | 389 | 42.44 |
| Robin Thomas | 4 | 457 | 35.92 |
| Peter Whalen | 5 | 14 | 2.42 |