Home » Subject » Graph Theory » Basic G.T.

Domination in cubic graphs

Importance: Medium ✭✭
Author(s): Reed, Bruce A.
Subject: Graph Theory
» Basic Graph Theory
Keywords: cubic graph
domination
Recomm. for undergrads: no
Posted by: mdevos
on: August 19th, 2009
Problem   Does every 3-connected cubic graph $ G $ satisfy $ \gamma(G) \le \lceil |G|/3 \rceil $ ?

If the girth of $ G $ is sufficiently large, then $ \gamma(G)\leq 0.2999|G| $ [KSV].

Bibliography

[KSV] Daniel Kral, Petr Skoda, Jan Volec: Domination number of cubic graphs with large girth


* indicates original appearance(s) of problem.
add new comment