Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Cubic Graphs with Large Ratio of Independent Domination Number to Domination Number
Ist Teil von
Graphs and combinatorics, 2016-03, Vol.32 (2), p.773-776
Ort / Verlag
Tokyo: Springer Japan
Erscheinungsjahr
2016
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
A
dominating set
in a graph
G
is a set
S
of vertices such that every vertex outside
S
has a neighbor in
S
; the
domination number
γ
(
G
)
is the minimum size of such a set. The
independent domination number
, written
i
(
G
)
, is the minimum size of a dominating set that also induces no edges. Henning and Southey conjectured
i
(
G
)
/
γ
(
G
)
≤
6
/
5
for every cubic (3-regular) graph
G
with sufficiently many vertices. We provide an infinite family of counterexamples, giving for each positive integer
k
a 2-connected cubic graph
H
k
with
14
k
vertices such that
i
(
H
k
)
=
5
k
and
γ
(
H
k
)
=
4
k
.