Home » Keyword index

domination


Graph Theory » Basic G.T.

Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph $ G $ satisfy $ \gamma(G) \le \lceil |G|/3 \rceil $ ?

Keywords: cubic graph; domination

Posted by mdevos
updated August 19th, 2009
add new comment
Graph Theory » Topological G.T.

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation $ G $ has a dominating set of size $ \le \frac{1}{4} |V(G)| $.

Keywords: coloring; domination; multigrid; planar graph; triangulation

Posted by mdevos
updated May 4th, 2009
add new comment
Syndicate content