Paper Menu >>
Journal Menu >>
Intelligent Information Management, 2010, 2, 143-148 doi:10.4236/iim.2010.22017 Published Online February 2010 (http://www.scirp.org/journal/iim) Copyright © 2010 SciRes 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 Email: akhodkar@westga.edu, s.m.sheikholeslami@azaruniv.edu 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 kn 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 d12n 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 Copyright © 2010 SciRes IIM 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 2nm =()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 ()fvb 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 Copyright © 2010 SciRes IIM 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 8nm 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 ()GeEuv 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 0n 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 Copyright © 2010 SciRes IIM 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 1n G G1m1 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, }uvvweE 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 4k 9 2, ()2 kGnk 10n 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 3k 2, 3m )3) (3)9 k Gn k n 18k. 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( )}3uv { 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 1n2m1 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. nk 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 3k={ 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, 2k )9 = 2213. kGn f2,(2) () k kn 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 kn 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 1k 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. Gk k Gf EG 2, () 29 gEn Hence, kGnk , as desired. Case 4. ()4 G. Copyright © 2010 SciRes IIM A. N. GHAMESHLOU ET AL. Copyright © 2010 SciRes IIM 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)”. |