Intelligent Information Management, 2010, 2, 143-148
doi:10.4236/iim.2010.22017 Published Online February 2010 (http://www.scirp.org/journal/iim)
Signed (b,k)-Edge Covers in Graphs
A. N. Ghameshlou1, Abdollah Khodkar2, R. Saei3, S. M. Sheikholeslami*3
1Department of Mathematics, University of Mazandaran Babolsar, I.R., Iran
2Department of Mathematics, University of West Georgia, Carrollton, USA
3Department of Mathematics, Azarbaijan University of Tarbiat MoallemTabriz, I.R., Iran
Abstract
Let be a simple graph with vertex set and edge set . Let have at least vertices of
degree at least , where and b are positive integers. A function is said to be a
signed -edge cover of G if
G()VG
()eEv
()EG G
:( fE
k
b k) {1,1}G
(, )
bk ()
f
eb


for at least vertices of , where
. The value
kvG
()={ uvE(()EvG uNv)| }() min( )
GeE
f
e


, taking over all signed -edge covers (, )bk
f
of G
is called the signed -edge cover number of and denoted by (, )bk G,bk()G


. In this paper we give some
bounds on the signed -edge cover number of graphs. (,bk)
Keywords: Signed Star Dominating Function, Signed Star Domination Number, Signed -edge Cover,
Signed -edge Cover Number
(, )bk
(, )bk
1. Introduction
Structural and algorithmic aspects of covering vertices
by edges have been extensively studied in graph theory.
An edge cover of a graph G is a set C of edges of G such
that each vertex of G is incident to at least one edge of C.
Let b be a fixed positive integer. A b-edge cover of a
graph G is a set C of edges of G such that each vertex of
G is incident to at least b edges of C. Note that a b-edge
cover of G corresponds to a spanning subgraph of G with
minimum degree at least b. Edge covers of bipartite
graphs were studied by König [1] and Rado [2], and of
general graphs by Gallai [3] and Norman and Rabin [4],
and b-edge covers were studied by Gallai [3]. For an
excellent survey of results on edge covers and b-edge
covers, see Schrijver [5].
We consider a variant of the standard edge cover
problem. Let G be a graph with vertex set and
edge set . We use [6] for terminology and notation
which are not defined here and consider only simple
graphs without isolated vertices. For every nonempty
subset of , the subgraph of G whose vertex
set is the set of vertices of the edges in
()VG
()EG
E()EG
E
 and whose
edge set is E

, is called the subgraph of induced by G
E

and denoted by []GE

. Two edges of
are called adjacent if they are distinct and have a
common vertex. The open neighborhood of an
edge
12
,ee
()
G
Ne
G
() GeE

is the set of all edges adjacent to . Its
closed neighborhood is . For a
function and a subset of we
define
e
)
[]=Ne
G
R
()
(){}e
(EG
G
Ne
S:(fE
()
) G
eS
=
f
S
fe

. The edge-neighborhood
of a vertex
()v
G
E(vV )G

is the set of all edges
incident to vertex v. For each vertex , we
also define
(vV )G
()eE v
G
()= ()
f
vf
e

. Let be a positive
integer and let have at least vertices of degree at
least . A function is called a
signed -edge cover (SbkEC) of G, if
b
{1
G k
)
G b
(,bk
:(fE ,1}
)()
f
vb
for at least vertices of . The signed
-edge cover number of a graph G is
k
)
()=G
vG
(,bk
,bk min


{()| }
eE
f
efis an SbkEC onG


. The
signed -edge cover (, )bk
f
of with G
,
=bk (()) ()
f
EG G


is called a ,bk()G

-cover. For any
signed -edge cover
(, )bk
f
of we define G
*Corresponding author

A. N. GHAMESHLOU ET AL. 144
={|( )=1}PeEfe
={ |( )}VvVfv

=1b=k
, ,
and .
={|( )=1}MeEfe
= {|()<}VvVfvb

(, )bk
'( )
SS G
b
If and , then the signed -edge
cover number is called the signed star domination
number. The signed star domination number was intro-
duced by Xu in [7] and denoted by
n

. The signed
star domination number has been studied by several
authors (see for example [7,10]).
If and 1, then the signed -edge
cover number is called the signed star -subdomination
number. The signed star -subdomination number was
introduced by Saei and Sheikholeslami in [11] and
denoted by .
=1 b
()
k
SS G

b
(, )bk
b
()
bG
kn
k
(, )bk
k
= kn
If is an arbitrary positive integer and , then
the signed -edge cover number is called the
signed -edge cover number. The signed b-edge cover
number was introduced by Bonato et al. in [12] and
denoted by


(, )bk
.
The purpose of this paper is to initiate the study of the
signed -edge cover number ,()
bk G


'( )
SS G
. Here are
some well-known results on

, and ( )
k
SS G

()
bG


1, '( )24 nGn
.
Theorem 1 [10] For every graph G of order , 4n

.
Theorem 2 [11] For every graph of order
without isolated vertices,
Gn 
'( )4.
kGnk
4
1,


Theorem 3 [10] For every graph G of order
without isolated vertices,
n
1,
 '( )2
n
n
G 
G n
.
Theorem 4 [11] For every graph of order
without isolated vertices,
2
1, '() kG


G
b
(()1)()
2
GknG
n
.
Theorem 5 [12] Let b be a positive integer. For
every graph of order and minimum degree at
least ,
,bn
'( ).
2
bn
G  
We make use of the following result in this paper.
Theorem 6 [7] Every graph G with () 3G


contains an even cycle.
2. Lower Bounds for SbkECN of Graphs
In this section we present some lower bounds on
terms of the order, the size, the maximum degree and the
degree sequence of . Our first proposition is a gene-
ralization of Theorems 3, 4 and 5.
G
Proposition 1 Let be a graph of order without
isolated vertices and maximum degree . Let
be a positive integer and let be the number of
vertices with degree at least . Then for every positive
integer
Gn
=()G
b01n
b
0
1kn

,
0
,
()( 1)(1
() .
2
bk
kbn bnb
G 
)



Proof. Let
f
be a ,()
bk G


-cover. We have
,
()() ()
() ()
00
0
1
() =()=()
2
11
=()
22
()()(1)
22
()(1)(1)
=.
2
bk
eEG vVGeEv
eEv eEv
vV vV
Gfefe
()
f
ef
nk nnb
kb
kbn bnb


 



 

 

 e
Theorem 2 Let be a graph of order , size ,
without isolated vertices and with degree sequence
, where
Gn m
12
(, , ,)
n
dd d12n dd d


01n
. Let b be a
positive integer and let be the number of vertices
with degree at least . Then for every positive integer b
0
1kn

,
2
=1
,
()
() .
2
k
jj
j
bk
n
bd d
Gm
d




Proof. Let
g
be a ,()
bk G


-cover of G and let
()
g
vb
{,,v
for distinct vertices v in k()=BG
()=
1}
jj
k
v. Define by :(fEG) {0,1}
f
e
(()1)/2ge

for each ()eEG

. We have
()= ()
([])deg()deg()1
([])= 2
G
G
eEG euvEG
gN euv
fN e


 .
(1)
,bk


in Since

A. N. GHAMESHLOU ET AL. 145
()
(( [])())=(())deg()
G
eEG vV
g
Ne gegEvv



and
2
=()
(deg()deg()) =deg(),
euvEG vV
uv v



by (1) it follows that
()
()
\{, ,}
1
2
,
=1
2
,
=1
2
,
=1
([])
11
deg( )((( ))deg( ))()
222
1deg( )((( ))deg( ))
2
11
()()
222
11
()()
222
11
()().
222
G
eEG
vV eEG
vV vv
jj
k
k
jj bk
ii
i
k
jj bk
ii
i
k
jj bk
j
fN e
m
vgEv vge
vgEv v
m
bd dG
m
bd dG
m
bd dG









 











(2)
On the other hand,
() ()
()
() ()
()
([])= (())deg()()
(()) ()
=(2 ())()
=(2 1)().
G
eEG vVeEG
n
vVe EG
n
eEG eEG
n
eEG
f
NefEv vfe
fEvdfe
dfe fe
dfe














(3)
By (2) and (3)
2
,
=1
()
11
()()
22
() .
21
k
jj bk
j
eEG n
m
bd dG
fe d






2
(4)
Since (())=2(())
g
EGf EGm

, by (4)
,
()
()= ()
bk
eEG
Gge 



2
,
=1
1(()()) .
21
k
jj bk
j
n
bddGm m
d





Thus,
2
=1
,
()
() ,
2
k
jj
j
bk
n
bd d
Gm
d




as desired.
An immediate consequence of Theorem 2 is:
Corollary 3 For every
r
-regular graph G of size , m
,
()
() .
2
bk
kb r
Gm



Furthermore, the bound is sharp
for -regular graphs with and . r=br =kn
Theorem 4 Let G be a graph of order , size ,
without isolated vertices, with minimum degree
2nm
=()G


0
1kn
and maximum degree . Let b be a
positive integer and be the number of vertices
with degree at least b. Then for each positive integer
=()G
01n


,'( ) bk G


222 22
0
()2()( 1)(( 1)).
2
bkm bnbn 

 (5)
Furthermore, the bound is sharp for -cycles when
and .
n
=2b=kn
Proof. Let ()={()|deg()}BGvV Gvb


)
and let
be a
f
,( bk G


-cover. Since for each , ,
it follows that
vV

()fvb
deg( )
|()|2
vb
MEv 

 . Thus
=
=
([ ])
2
2
(21) ||
(deg()deg( )1)
|| (deg()deg())
||| ()|deg()
||| ()|deg()| ()|deg()
deg( )
||deg()deg()
2
deg( )
|| 2












 
 
 

 
 






euvM
euvM
vVGM
vV vV
vV vV
vV v
M
uv
Muv
MMEvv
M
MEv vMEv v
vb
Mvv
v
M2 deg( )deg( )
2




VvV
b
vv

A. N. GHAMESHLOU ET AL. 146
222
2
()
22
\()
22 2
22 2
00
deg( )deg( )
||| |
222
deg( )deg( )
|| 22
deg( )||
22
(1)
|||()|| \()
22 2
(1)
||( )( )
22 2
vV vV
vV vV BG
vV BG
vvb
MV
vv
M
vb
V
bb
|
M
mk VBGVBG
bb
Mm knknn









 
 


 

 



Hence,
222 22
0
1
||((1)((1)) ())
24
m.
M
bnbnbk



Now (5) follows by the fact that ,()=2| | bk Gm M



.
3. An Upper Bound on SbkECN
Bonato et al. in [11] posed the following conjecture on
()
bG

.
Conjecture 5 Let be an integer. There is a
positive integer so that for any graph G of order
with minimum degree b,
2b
b
n
b
nn
() (1)(1).
bGbnb

 
Since 1, 1
()=(1)(
bbnb
Kbnb1),



the upper bo-
und would be the best possible if the conjecture were
true. They also proved that the conjecture is true for
. In this section we provide an upper bound for =2 b
,'( bk G)

, where and 1=2 bkn

. The proof of the
next theorem is essentially similar to the proof of
Theorem 5 in [11].
Theorem 6 Let G be a graph of order , size
and without isolated vertices. Let be the number
of vertices with degree at least 2. Then for and
,
n
n
m
0>0n
7 
0
1kn
2, ()29. kGnk


Proof. The proof is by induction on the size m of G.
By a tedious and so omitted argument, it follows that
2, ()5 kGk

 if . We may therefore assume that
. Suppose that the theorem is true for all graphs G
without isolated vertices and size less than . Let G be
a graph of order , size and without isolated
vertices. We will prove that
=7n
8n
m
2Gn
8nm
2, () 9 kk


for
each 0 kn1


()G
. We consider four cases.
Case 1. =1

.
Let be a vertex of degree 1 and . First s-
uppose . Then the induced subgraph [Gu
2
u
deg()=v
(vN)u
,v
1] is
K
. It is straightforward to verify that 2, 29
knk


ence, we assume that 9n. Let
=Gv
when =8n. H
Gu
may


. Then G

is a graph ofrder 27n o

,
size m1

and without isolated vertices. By the induc-
tive hypothesis, 2, ()
kG




2(2)9 = 213nk nk .
Let f be a 2,k


()
-
1 and ()=
G

cover. Define
1,1} by ()=guv (): (gE ){G
g
efe
uv if ()eEG

. Obviously,
g
is a S2kEC and so
2, ()2, 1 2 kk
( )GG 14<2 9.nknk





 
r two subcases.
Gu, ()Gu
Now suppose
i
deg( )v
( )v
hypothesis
2. Conside
on ve
Subcase 1.1 deg3 .
By the induct2,k



2(1)9 = 211nk nk

 . Lf2, et be a k


()Gu

-cover a
=1
nd define by :({1,1}gEG )
()gu v and ()=()
g
efe . if ()GeEuv
Obviously,
g
is a
()1 2G nk
S2kEC and so
2, ()G2,kk 10<2 9.nk






Subcase 1.2 de2 . g() =v
{} u. If e =1 defin
( )=vw
k, then Let ()wNv


by : (EG ()= 1guv g and ()=){ 1,1}g
g
e
1

if ()eEG\{ ,uvvw}. Obviously,
g

is a S2k
2 9.
EC
of G and we ha
2, ()
ve
(())=4



 mn
2. By the inductive
k
k
Let 2 k. It
hesis
GgE
follows that
G
0n
hypot on {}

Gu, { })2(1)
2,1 (


k

un
(1)9=2
G
12

knkf be a . Let 2, 1



k
({})

Gu
()guv
-cov
=(gv
er by. Define :){ 1,1}gE (G
))=1w and ()=(
g
e
ly,
fe if ()\G eE
{,uv vw}. Obviou
g
and sosis a S2kE
})
C
3 29.
2, ()2,1 ( {






u k n
kk
GG

A. N. GHAMESHLOU ET AL. 147
Case 2. ()=2

G.
Let be a vertex of degree 2 and .
Consider two subcases.
w()={,}Nw uv
Subcase 2.1 . Let be the graph
obtained from by adding an edge uv . Then
has order , size and at least
()

uvE G
{}Gw
1n

G

G1m1

k
vertices with degree at least 2. By the inductive
hypothesis,
(1),2
()2(1)(1)9 = 212.



 
kGn knk
Let be a f2, ()


kG-cover. Define :()gEG
{1,1} by and ()=()=1guw gvw()=()
g
efe if
. Obviously, ()\{G, }uvvweE
g
is a S2kEC and so
2, ( )(())( ())329.


 
kGgEG fEGnk

Subcase 2.2 . First let both and
have degree 2. Then the induced subgraph
is an isolated triangle. If 1, then define
by
()uvEG
1,1}
u
[{Gu
v
}]w,,v
3 k
:(){fEG
()=()=()=1a( )=1o.fuv fvw fuwndfetherwise
Then
2, ()(())=629.


kGfEG mnk

Now suppose that . It is not hard to show that 4k
9
2, ()2


kGnk
10n
when or 9. Hence, we may
assume that . Let . Then
=8n
=\

GG{,,}uvw

G
= 2
is
a graph of order , size and has at least
vertices with degree at least 2. By the inductive
hypothesis,
3
(3) (
7
2(
n
3k
2,
3m
)3) (3)9



k
Gn  k n 
18k. Let be a f2,(3) ()




kG-cover. Define
by : (gE ){G1,1}
()=( )=()=1a()=()i().


g
uvg vwg uwndgefefeE G
Obviously,
g
is a S2kEC of and G
2, ()=(()) (())3(218)3.



kGgEG fEGnk
Now let . If , define
by and
min{deg(),deg( )}3uv
{ 1,1} ()=(guw gv
=1k
=1:( )gEG )w()=
g
e
1 otherwise. Obviously,
g
is a S2kEC and so
2, ()(( ))=4<29.


kGgEGm nk

}
If , then is a graph of order
, size and has at least vertices with
degree at least 2. By the inductive hypothesis, we have
that
2 k={
GGw
1n2m1 k
2,(1) ()2 12






kGnk
()
. Let be a f
2,( 1)




G
k-cover. We can obtain a S2kEC
g
of by
assigning for each
G
)()=1ge () (\

eEG GE and
()=()
g
efe (

for each )

eEG
2,(
())=(())2=
. Then we have
1) ()2(<2 9.





nk
k
Gf EG
2, ()<2 9
gEG
Hence,




kGnk
min{deg( ),
g() = 2
u
){ 1,1}G()guw
= 1
, as desired.
Finally, assume . Let without
loss of generality de . If 1, define
by and
deg()} =2uv
2
=()= ) gvw

( guv
k
: (gE
()
=1

ge otherwise. Obviously,
g
is a S2kEC and so
2, ()(())=629.



mn
}
k
kGgEG
3k={
If , then

GGw is a graph of order
1

n, size 2

m
2,(2) ()2(1) (
and has at least vertices with
degree at least 2. By the inductive hypothesis,
2k
)9 = 2213.






kGn
f2,(2) ()
 k kn
Let be a




kG
}
-cover. Define :()GgE
{1,1

by
()=()= ()=1a(())=
g
uvg vwg uw
i(

nd g ee
)\{}.
f

feEGuv
Obviously,
g
is a S2kEC of and G
)) 4
2, ()(())= ((29.




G kn
kGgEG fE
()=3 Case 3.

G
w
){ 1,1}G()guw
= 1
.
Let be a vertex with degree 3. If , define
by if and
=1k
uN: (gE
()
=1 ()
w

ge otherwise. Obviously,
g
is a S2kEC and so
2, ()(())=6<29.



mn
}
kGgEG
2 k={
k
If , then


GGw is a graph of order
1

n, size 3

m
2,(1) ()2 12
and has at least vertices with
degree at least 2. By the inductive hypothesis, we have
that
1k






kGnk. Let be a f2,( 1)



k
()

G-cover. We can obtain a S2kEC
g
of by
assigning for each
G
)()=1ge () (\

eEG GE and
()=()
g
efe (

for each )

eEG
2,(
())=(())3=
. Then we have
1) ()3(2 9.





 Gk
k
Gf EG
2, () 29
gEn
Hence,




kGnk
, as desired.
Case 4. ()4

G.

A. N. GHAMESHLOU ET AL. 148
5. References
Then has an even cycle by Theorem 6. Let G
12
,=(,,)
s
Cv v
=()
GG C
v
E
be an even cycle in G. Obviously,
is a graph of order , size n|()|

mEC
and has at least vertices with degree at least 2. By the
inductive hypothesis,
k
2, ()2 9




kGnk. Let be a f
2, ()


kG
-cover. Let and define
11
=
s
vv :()gEG
[1] D. König, “Über trennende knotenpunkte in graphen
(nebst anwendungen auf determinanten und matrizen),”
Acta Litterarum ac Scientiarum Regiae Universitatis
Hungaricae Francisco-Josephinae, Sectio Scientiarum
Mathematicarum [Szeged], Vol. 6, pp. 155–179, 1932–
1934.
{1,1} by [2] R. Rado, “Studien zur kombinatorik,” Mathematische
Zeitschrift, German, Vol. 36, pp. 424–470, 1933.
1
() =(1)i=1,,a()=() f

i
ii
g
vvf isnd gefeor
[3] T. Gallai, “Über extreme Punkt-und Kantenmengen
(German),” Ann. Univ. Sci. Budapest. Eötvös Sect. Math.,
Vol. 2, pp. 133–138, 1959.
()\().eEGEC
Obviously,
g
is a S2kEC and hence 2, ()=


kG
[4] R. Z. Norman and M. O. Rabin, “An algorithm for a
minimum cover of a graph,” Proceedings of the American
Mathematical Society, Vol. 10, pp. 315–319, 1959.
2, ()2 9.

 
kGnk This completes the proof.
4. Conclusions [5] A. Schrijver, “Combinatorial optimization: Polyhedra and
Efficiency,” Springer, Berlin, 2004.
[6] D. B. West, “Introduction to graph theory,” Prentice- Hall,
Inc., 2000.
In this paper we initiated the study of the signed
-edge cover numbers for graphs, generalizing the
signed star domination numbers, the signed star k-
domination numbers and the signed b-edge cover
numbers in graphs. The first lower bound obtained in this
paper for the signed -edge cover number conc-
ludes the existing lower bounds for the other three pa-
rameters. Our upper bound for the signed -edge
cover number also implies the existing upper bound for
the signed b-edge cover number. Finally, Theorem 6
inspires us to generalize Conjecture 5.
(, )bk
(, )bk
(, )bk
[7] B. Xu, “On signed edge domination numbers of graphs,”
Discrete Mathematics, Vol. 239, pp. 179–189, 2001.
[8] C. Wang, “The signed star domination numbers of the
Cartesian product,” Discrete Applied Mathematics, Vol.
155, pp. 1497–1505, 2007.
[9] B. Xu, “Note on edge domination numbers of graphs,”
Discrete Mathematics, Vol. 294, pp. 311–316, 2005.
[10] B. Xu, “Two classes of edge domination in graphs,” Discr-
ete Applied Mathematics, Vol. 154, pp. 1541–1546, 2006.
Conjecture 7 Let be an integer. There is a
positive integer so that for any graph G of order
with vertices of degree at least b, and for
any integer ,
3 b
,


bk
b
n
1
 k
b nn 0 n
10 n2 ()( 1). Gbnkb
[11] R. Saei and S. M. Sheikholeslami, “Signed star k-sub-
domination numbers in graph,” Discrete Applied Mathe-
matics, Vol. 156, pp. 3066–3070, 2008.
[12] A. Bonato, K. Cameron, and C. Wang, “Signed b-edge
covers of graphs (manuscript)”.