Name
Abstract | ||
|---|---|---|
A dominating set D subset of V(G) of a graph G is a set such that each vertex v is an element of V(G) is either in the set or adjacent to a vertex in the set. Matheson and Tarjan (1996) proved that any n-vertex plane triangulation has a dominating set of size at most n/3, and conjectured a bound of n/4 for n sufficiently large. King and Pelsmajer recently proved this for graphs with maximum degree at most 6. Plummer and Zha (2009) and Honjo, Kawarabayashi, and Nakamoto (2009) extended the n/3 bound to triangulations on surfaces. We prove two related results: (i) There is a constant c(1) such that any n-vertex plane triangulation with maximum degree at most 6 has a dominating set of size at most n/6 + c(1). (ii) For any surface S, t >= 0, and epsilon > 0, there exists c(2) such that for any n-vertex triangulation on S with at most t vertices of degree other than 6, there is a dominating set of size at most n(1/6 + epsilon) + c(2). As part of the proof, we also show that any n-vertex triangulation of a non-orientable surface has a non-contractible cycle of length at most 2 root n. Albertson and Hutchinson (1986) proved that for n-vertex triangulation of an orientable surface other than a sphere has a non-contractible cycle of length root 2n, but no similar result was known for non-orientable surfaces. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.26493/1855-3974.200.fbe | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Dominating set,triangulation,graphs on surfaces,non-contractible cycle,non-orientable surface | Topology,Dominating set,Combinatorics,Vertex (geometry),Vertex (graph theory),Neighbourhood (graph theory),T-vertices,Triangulation (social science),Degree (graph theory),Mathematics,Point set triangulation | Journal |
Volume | Issue | ISSN |
4 | 1 | 1855-3966 |
Citations | PageRank | References |
9 | 0.84 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hong Liu | 1 | 39 | 8.54 |
| Michael J. Pelsmajer | 2 | 189 | 20.19 |