Signed Star Domination Numbers Of Graphs

We consider only finite and simple graph(without loops or multiple edge). Let G=(V(G), E(G)) be a graph. The set V(G) and E(G) are the set of vertices and the set of edges, respectively. If A, B(?)V(G) and A∩B=φ, we write E_G(A, B) for the set of edges joining a vertex in A to a vertex in B, E_G(A)=E_G(A, V(G)-d). The degree and the neighbourhood of x is denoted by d_G(x) and N_G(x) respectively. Occasionally one calls N_G[x]=N_G(x)∪{x} the closed neighbourhood of x. If D(?)V(G), then N(D)=∪_v∈DN(v) is said to be the neighbourhood of D, and N[D]=N(D)∪D is said to be the closed neighbourhood of D. P_n denotes the path of order n. If S(?)V(G), then G[S] denotes the subgraph induced by S in G. If x, y∈V(G), x is adjacent to y, then xy denotes the edge incident with x and y. G×H denotes the cartesian product G and H. V(G)×V(H) is the set of vertices, (x, a) is adjacent to (y, b) if and only if x=y and ab∈E(H), or a=b and xy∈E(G) when x, y∈V(G), a, b∈V(H).Let u, v∈V(G), if v∈N[u], then we say that u dominates v. For D(?)V(G) and v∈V(G), if v∈N[D] we say that D dominates v. If D dominates all vertices of a graph G, i.e., N[D]=V(G), then D is said to be a dominating set of G. the order of minimal dominating set is the domination number of graph. The study of domination is initiated by Ore[1]. The growing area with graph theory is the bibliographr revealed an impressive increase([2]-[12]). Applications of minimum dominating sets is an NP-complete problem, see[13]. Now, the domination number of only some special graphs is known to us, so people focus on others parameters for the domination number. Some results on it cound be found in[14]-[17]. Recently, the field of domination number is steadily growing. There are variaties of domination numbers, but those are mostly vertice domination numbers.As to edge domination number, Xu baogen introduced the signed edge domination number of graphs in[18].Definition [19] Let G be a graph without isolated vertices. A function f:E→{+1, -1} is called the signed star domination function of G if (?) f(e)≥1 for every v∈V(G). The signed star domination number of G is defined asγ_ss^'(G)=min{(?) f(e)|f is a signed star domination function of G}.In[19][20], Xu have some properties of signed star domination numberγ_ss^'(G).Lemma 2 For any graph G of order n≥4, thenγ_ss^'(G)≤2n-4, and this bound is sharp.Lemma 3 For all graphs G of order n, ifδ(G)≥1, thenγ_ss^'(G)≥n/2.As to signed star domination number of bipartite graph, Xu obtainedLemma 6[21] If m, n is integers and m≥n≥1, thenFor this paper, we research signed star domination number of graph, Xu gives the upper and lower bounds. We characterize graphs for which the signed domination numbers are the upper and lower bounds in chapter 3.Theorem 1 If G is a graph of order n≥4, thenγ_ss^'(G)=2n-4, if and only if(1)for n≥6, G≌K_{2, n-2}.(2)for n=5, G≌K_2,3,K₁+2K₂ or K₅.(3)for n=4, G≌C₄ or K₁+(K₁∪K₂).Theorem 2 If G is a graph withγ_ss^'(G)=n/2, then G=G₁∪G₂, forδ(G)≥3, V(G₁)=V(G₂)=V(G). forδ(G)=1 and m vertices of degree 1, V(G₁)=V(G)-m, V(G₂)=V(G). And G₁, G₂ are characterized by these graphs.(1) G₁ is the union of edge-disjiont cycles C₁, C₂,…, C_t.(2) G₂ is the union of edge-disjiont trails W_e1(u₁, v₁), W_e2(u₂, v₂),…, W_el(u_l, v_l) and l=n/2, V(G)={u₁, v₁, u₂, v₂,…, u_l, v_l}.Xu have determined the signed star domination number of the complete 2-partite graph, we gives the signed star domination number of the complete 3-partite graph.Theorem 3 For any integers m, n, s and m≥n≥s≥1, then(1) for m, n, s parity same,(2) for n, s parity same and m, n parity contrary (3) for n, s parity contrary and m, n parity same(4) n, s parity contrary and m, s parity sameWe gives some properties of signed star domination number in chapter 4Theorem 4 for m≥4 and n≥3,Theorem 5 for m≥3 and n≥3,Theorem 6...