G aphs wi h equal domina ion
and 2-domina ion numbe s
Ad iana Hansbe g
Uni e si a Poli `ecnica de Ca alunya
Ba celona
Abs ac
Fo a g aph Ga subse Do he e ex se o Gis a k-domina ing
se i e e y e ex no in Dhas a leas kneighbo s in D.The
k-domina ion numbe γk(G) is he minimum ca dinali y among
he k-domina ing se s o G. No e ha he 1-domina ion numbe
γ1(G) is he usual domina ion numbe γ(G).
Fink and Jacobson showed in 1985 ha he inequali y γk(G)≥
γ(G)+k−2 is alid o e e y connec ed g aph G.In hispape ,
we ecompile esul s conce ning he case k=2,whe eγkcan
be equal o γ. In pa icula , we p esen he cha ac e iza ion o
diffe en g aph classes wi h equal domina ion and 2-domina ion
numbe s as a e he cac us g aphs, he claw- ee g aphs and he
line g aphs.
1 Te minology
We conside fini e, undi ec ed, and simple g aphs Gwi h e ex se V=
V(G)andedgese E=E(G). The numbe o e ices |V(G)|o a g aph
Gis called he o de o Gand is deno ed by n(G). The neighbo hood
N( )=NG( )o a e ex consis s o he e ices adjacen o and
d( )=dG( )=|N( )|is he deg ee o .Byδ(G)andΔ(G), we deno e
he minimum deg ee and he maximum deg ee o he g aph G, espec i ely.
Fo a subse S⊆V, we define by G[S] he subg aph induced by S.I xand
ya e e ices o a connec ed g aph G, henwedeno ewi hdG(x, y) he
dis ance be ween xand yin G, i.e. he leng h o a sho es pa h be ween
xand y.
285
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
Wi h Knwe deno e he comple e g aph on n e ices and wi h Cn he
cycle o leng h n. We e e o he comple e bipa i e g aph wi h pa i ion
se s o ca dinali y pand qas he g aph Kp,q. A g aph Gis a block-cac us
g aph i e e y block o Gis ei he a comple e g aph o a cycle. Gis a cac us
g aph i e e y block o Gis a cycle o a K2. I we subs i u e each edge in
a non- i ial ee by wo pa allel edges and hen subdi ide each edge, hen
we speak o a C4-cac us.Le Gand Hbe wo g aphs. Fo a e ex ∈V,
we say ha he g aph Ga ises by infla ing he e ex o he g aph Hi
he e ex is subs i u ed by a se S o n(H) new e ices and a se o
edges such ha G[S ]∼
=Hand e e y e ex in S is connec ed o e e y
neighbo o in Gby an edge.
The ca esian p oduc o wo g aphs G1and G2is he g aph G1×G2wi h
e ex se V(G1)×V(G2) and e ices (u1,u
2)and( 1,
2) a e adjacen i
and only i ei he u1= 1and u2 2∈E(G2)o u2= 2and u1 1∈E(G1).
Le ube a e ex o G1and a e exo G2. Then he se s o e ices
{(u, y)|y∈V(G2)}and {(x, )|x∈V(G1)}a e called a ow and,
espec i ely, a column o G1×G2. A se o e ices in V(G1×G2) is called
a ans e sal o G1×G2i i con ains exac ly one e ex on e e y ow and
e e y column o G1×G2.
Ase Co e ices in a g aph Gis called a co e ing o Gi e e y edge
o Gis inciden wi h a leas one e ex o C. The minimum ca dinali y o
aco e ingo Gis deno ed wi h β(G) and is called he co e ing numbe o
G.Le kbe a posi i e in ege . A subse D⊆Vis a k-domina ing se o
he g aph Gi |NG( )∩D|≥k o e e y ∈V−D.Thek-domina ion
numbe γk(G) is he minimum ca dinali y among he k-domina ing se s
o G. No e ha he 1-domina ion numbe γ1(G) is he usual domina ion
numbe γ(G). A k-domina ing se o minimum ca dinali y o a g aph Gis
called a γk(G)-se . Fo a comp ehensi e ea men o domina ion in g aphs,
see he monog aphs by Haynes, Hede niemi, and Sla e [12, 13]. Mo e
in o ma ion on k-domina ion can be ound o example in [3, 4, 5, 6, 7, 8].
2 In oduc ion
Le Gbe a g aph such ha 2 ≤k≤Δ(G) o an in ege kand le D
be a k-domina ing se o Go minimum ca dinali y. Then V−Dis no
emp y and we can ake a e ex x∈V−D.I X⊆NG(x)∩Dis a se
o neighbo s o xin Dsuch ha |X|=k−1, hen e iden ly e e y e ex
286
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
in V−((D−X)∪{x}) has a neighbo in (D−X)∪{x}and hus he
la e is a domina ing se o G. This implies he ollowing heo em o Fink
and Jacobson, which es ablishes a ela ion be ween he usual domina ion
numbe γ(G)and hek-domina ion numbe γk(G).
Theo em 1 (Fink, Jacobson [6], 1985) I k≥2is an in ege and Gis a
g aph wi h k≤Δ(G), hen
γk(G)≥γ(G)+k−2.
The inequali y gi en abo e is sha p. Howe e , he cha ac e iza ion o
he g aphs a aining equali y is s ill an open p oblem. In [9], Hansbe g
analyzed he ex emal g aphs o gene al kand ga e se e al p ope ies o
hem, among hem he nex p oposi ion.
P oposi ion 2 [9] Le Gbe a connec ed g aph and kan in ege wi h Δ(G)≥
k≥2.I γk(G)=γ(G)+k−2and Dis a minimum k-domina ing se ,
hen Δ(G[D]) ≤k−2.
In pa icula , he case k= 2 in Theo em 1 is o special in e es since
i is he only possibili y whe e γkcan be equal o γ. In his case, P oposi-
ion 2 s a es ha i γ(G)=γ2(G), hen e e y minimum 2-domina ing se
is independen . In [11], Hansbe g and Volkmann p esen ed some p ope ies
on g aphs Gwi h γ2(G)=γ(G), among hem he ollowing one.
Theo em 3 [11] I Gis a connec ed non- i ial g aph wi h γ2(G)=γ(G),
hen δ(G)≥2.
3 G aphs wi h γ=γ2
In [11], Hansbe g and Volkmann showed ha he g aphs wi h minimum
deg ee a leas 2 and equal domina ion and co e ing numbe s ulfill also
ha bo h he domina ion and he 2-domina ion numbe s a e equal.
Theo em 4 [11] I Gis a g aph wi h δ(G)≥2and γ(G)=β(G), hen
γ2(G)=γ(G).
287
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
No e ha i has been shown by Rande a h and Volkmann in [15] ha
he g aphs wi h equal domina ion and co e ing numbe s ha e minimum
deg ee δ≤2. They also cha ac e ized his amily o g aphs.
In [11], Hansbe g and Volkmann cha ac e ized he cac us g aphs wi h
equal domina ion and 2-domina ion numbe s.
Theo em 5 [11] Le Gbe a cac us g aph. Then γ2(G)=γ(G)i and only
i Gis a C4-cac us.
In [10], Hansbe g, Rande a h and Volkmann cen e ed hei a en ion
on claw- ee g aphs and cha ac e ized hose wi h equal domina ion and 2-
domina ion numbe s. A claw- ee g aph is a g aph which does no con ain
aK1,3as an induced subg aph.
Following lemma gi es wo impo an s uc u al p ope ies o claw- ee
g aphs wi h equal domina ion and 2-domina ion numbe s.
Lemma 6 [10] Le Gbe a connec ed non i ial claw- ee g aph. I γ(G)=
γ2(G), hen e e y minimum 2-domina ing se Do G ulfills:
(i) E e y e ex in V−Dhas exac ly wo neighbo s in D.
(ii) E e y wo e ices a, b ∈Da e a dis ance 2in G.
Fo me lemma se s he basis o he cha ac e iza ion o all claw- ee
g aphs wi h equal domina ion and 2-domina ion numbe s. Le Hbe he
amily o g aphs such ha G∈Hi and only i ei he Ga ises om a
ca esian p oduc Kp×Kpo wo comple e g aphs o o de p o an in ege
p≥3 by infla ing e e y e ex bu he ones on a ans e sal (we call i
he diagonal) o a clique o a bi a y o de , o Gis a claw- ee g aph wi h
Δ(G)=n(G)−2 con aining wo non-adjacen e ices o maximum deg ee
(see Fig. 1 below).
This amily o g aphs desc ibes exac ly hose claw- ee g aphs wi h equal
domina ion and 2-domina ion numbe s, as is gi en in he heo em below.
Theo em 7 [10] Le Gbe a connec ed claw- ee g aph. Then γ(G)=γ2(G)
i and only i G∈H.
I Gis a g aph, hen he line g aph o G, deno ed by L(G), is ob ained
by associa ing one e ex o each edge o G, and wo e ices o L(G)
288
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
Kn1Kn2
Kn3Kn4
Kn5Kn6
a
b
Figu e 1: Examples o g aphs om he amily H
(he e, ni∈N o 1 ≤i≤6)
being joined by an edge i and only i he co esponding edges in Ga e
inciden wi h each o he . I o a g aph G he e is a g aph Gwhose line
g aph is isomo phic o G, henGis called line g aph. In 1968, Beineke
[1] ob ained a cha ac e iza ion o line g aphs in e ms o nine o bidden
induced subg aphs. Since he claw is one o hose subg aphs, he se o line
g aphs wi h γ=γ2is con ained in H. Using he cha ac e iza ion o line
g aphs o K ausz [14] and Beineke’s o bidden induced subg aphs in line
g aphs, Hansbe g, Rande a h and Volkmann we e able o cha ac e ize he
line g aphs wi h equal domina ion and 2-domina ion numbe s.
Theo em 8 [10] Le Gbe a line g aph. Then γ2(G)=γ(G)i and only
i Gis ei he he ca esian p oduc Kp×Kpo wo comple e g aphs o he
same ca dinali y po Gis isomo phic o he g aph Jdepic ed bellow.
Figu e 2: The g aph J.
No e ha he g aphs o he amily H, as also he cac us g aphs o
Theo em 5, con ain many induced cycles o leng h 4. This is no a pa -
icula p ope y o hese bo h g aph amilies wi h equal domina ion and
289
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
2-domina ion numbe s. In ac , his accumula ion o induced C4’s can be
ound in e e y g aph ulfilling equali y in Fink and Jacobson’s bound. The
eason o his pa icula i y lies basically on he asse ion o ollowing lemma.
Lemma 9 [9] Le Gbe a connec ed g aph wi h γk(G)=γ(G)+k−2 o
an in ege ksuch ha Δ(G)≥k≥2. Then, o e e y e ex u∈V−D
and e e y se Au⊆N(u)∩Dwi h |Au|=k, he e a e non-adjacen e ices
xu,x
u∈V−Dsuch ha D∩N(xu)=D∩N(x
u)=Au.
DV−D
Au
a1
u
xu
x
u
a2
ap
Figu e 3: The e ices a1,x
u,a
p,x
uinduce a cycle o leng h 4.
Using his lemma, Hansbe g was able o p o e ha o any g aph ulfill-
ing Fink and Jacobson’s bound, e e y e ex o Glies on an induced cycle
o leng h ou :
Theo em 10 [9] Le Gbe a connec ed g aph and kan in ege wi h Δ(G)≥
k≥2.I γk(G)=γ(G)+k−2, hen e e y e ex o Glies on an induced
cycle o leng h 4.
In he same pape , he au ho p esen ed a sha p lowe bound in e ms
o he domina ion numbe o he numbe o induced cycles o leng h 4 in
his amily o g aphs.
Theo em 11 [9] Le Gbe a connec ed g aph and kan in ege wi h Δ(G)≥
k≥2.I γk(G)=γ(G)+k−2, henGcon ains a leas (γ(G)−1)(k−1)
induced cycles o leng h 4.
290
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
To show ha p e ious bound is igh , le and kbe wo posi i e in e-
ge s, whe e k≥2andle Gbe a g aph consis ing o a comple e g aph H
on k−1 e ices and o e ices ui, i,wi, o 1≤i≤ , such ha e e y ui
and wiis adjacen o e e y e ex o Hand o i(see Figu e 4). I is easy
o see ha γk(G)=k+ −1, γ(G)= +1and husγk(G)=γ(G)+k−2.
Since Gcon ains exac ly (k−1) = (γ(G)−1)(k−1) induced cycles o
leng h 4, i ollows ha he bound in Theo em 10 is sha p.
Kk−1
1
u1
w1
2
u2
w2
u
w
Figu e 4: Example o a g aph Gwi h γk(G)=γ(G)+k−2andexac ly(γ(G)−
1)(k−1) induced cycles o leng h 4. A double line connec ing a e ex uio wi o
he comple e g aph Kk−1in he middle means ha i is adjacen o all e ices o
Kk−1.
Using he inequali y γk(G)≥k
Δ+kn o any n- e ex g aph wi h maxi-
mum deg ee δ, p o ed by Fink and Jacobson in [7], he ollowing co olla y
a ises.
Co olla y 12 [9] Le Gbe a g aph and kan in ege such ha 2≤k≤
Δ(G).I γk(G)=γ(G)+k−2, henGcon ains a leas
(n
Δ(G)+1−1)(k−1)
induced cycles o leng h 4.
No e ha , i Gis a g aph wi h γk(G)=γ(G)+k−2 o an in ege k
wi h 2 ≤k≤Δ(G), γ(G) is a leas 2 and hus Δ(G)≤n(G)−2, which
implies ha he ac o ( n
Δ(G)+1 −1) abo e is always posi i e.
291
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
Re e ing he asse ion o he heo em, we gain an imp o emen o Fink
and Jacobson’s lowe bound in Theo em 1 and we ob ain, as a co olla y, a
heo em o Chellali, Fa a on, Hansbe g and Volkmann.
Co olla y 13 [9] Le Gbe a g aph wi h Δ(G)≤n(G)−2.I Ghas less
han (γ(G)−1)(k−1) induced cycles o leng h 4 o an in ege kwi h
Δ(G)≥k≥2, henγk(G)≥γ(G)+k−1.
Co olla y 14 [2] I Gis a g aph wi h a mos k−2induced cycles o leng h
4 o an in ege kwi h Δ(G)≥k≥2, henγk(G)≥γ(G)+k−1.
I emains hus as an open p oblem he cha ac e iza ion o mo e g aph
amilies a aining equali y in Fink and Jacobson’s bound and specially he
in e es ing case whe e γ2=γ.
Acknowledgemen
This esea ch was suppo ed by he Minis y o Science and Inno a ion,
Spain, and he Eu opean Regional De elopmen Fund (ERDF) unde p ojec
MTM2008-066200-C03-02/MTM; also by Ca alonian go e nmen unde p o-
jec 2009 SGR 1298; and by Fu u e Resea ch pos doc Consolide i-ma h.
Re e ences
[1] L.W.Beineke,De i ed g aphs and dig aphs, Bei ¨age zu G aphen he-
o ie,(H sg.H.Sachs,H.Voss,H.Wal he ),Teubne , Leipzig, 17–23,
1968.
[2] M. Chellali, O. Fa a on, A. Hansbe g and L. Volkmann. On he p-
domina ion, he o al domina ion and he connec ed domina ion num-
be s o g aphs. J. Combin. Ma h. Combin. Compu ., 73: 65–75, 2010.
[3] O. Fa a on. On a conjec u e o Fink and Jacobson conce ning k-
domina ion and k-dependence. J. Combin. Theo y Se ies B, 39:101–
102, 1985.
[4] O. Fa a on. k-domina ion and k-independence in g aphs. A s Combin.,
25 C:159–167, 1988.
292
G aphs wi h equal domina ion and 2-domina ion numbe s A. Hansbe g
[5] O. Fa a on, A. Hansbe g and L. Volkmann. On k-domina ion and
minimum deg ee in g aphs. J. G aph Theo y, 57:33–40, 2008.
[6] J.F. Fink and M.S. Jacobson. n-Domina ion in g aphs, G aph Theo y
wi h Applica ions o Algo i hms and Compu e Science,John Wiley
and Sons, New Yo k, 283–300, 1985.
[7] J.F. Fink and M.S. Jacobson. On n-domina ion, n-dependence and
o bidden subg aphs, G aph Theo y wi h Applica ions o Algo i hms
and Compu e Science,John Wiley and Sons, New Yo k, 301–311,
1985.
[8] A. Hansbe g. Mul iple domina ion in g aphs, Disse a ion,
RWTH Aachen Uni e si y, Aachen, 2009, h p://da win.b h. w h-
aachen.de/opus3/ oll ex e/ 2009/2912.
[9] A. Hansbe g. On he k-domina ion numbe , he domina ion numbe
and he cycle o leng h ou . submi ed.
[10] A. Hansbe g, B. Rande a h, L. Volkmann. Claw- ee g aphs wi h equal
domina ion and 2-domina ion numbe s. submi ed.
[11] A. Hansbe g and L. Volkmann. On g aphs wi h equal domina ion and
2-domina ion numbe s. Disc e e Ma h., 308(11):2277–2281, 2008.
[12] T.W. Haynes, S.T. Hede niemi, and P.J. Sla e . Fundamen als o Dom-
ina ion in G aphs, Ma cel Dekke , New Yo k, 1998.
[13] T.W. Haynes, S.T. Hede niemi, and P.J. Sla e (eds.) Domina ion in
G aphs: Ad anced Topics.Ma cel Dekke , New Yo k, 1998.
[14] J. K ausz. D´emons a ion nou elle d’une h´eo `eme de Whi ney su les
´eseaux (Unga ian). Ma . Fiz. Lapok, 50:75–85, 1943.
[15] B. Rande a h and L. Volkmann. Cha ac e iza ion o g aphs wi h equal
domina ion and co e ing numbe . Disc e e Ma h., 191:159-169, 1998.
293
