Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.     

SOME RESULTS ON UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTION

1. IntroductionLet G = (V, E) be an undirected graph. The open neighborhood N(v) of vertex v E Vis given by N(v) = {u E V: tv E E}. A total dominating function (TDF) of G is afunction f: V - [0, 11 such that Z f(u) 2 1 for each vertex v. A TDF f is minimaladN(~)(MTDF) if no function g < f is also a TDF of G. The illteger valued TDFs are preciselythe characteristic functions of total dominating sets of G (i.e., subset X G V such that anyv is adjacellt to at leajst one x E X). T…     

乘积图的Fractional控制

Let G =(V,E) be a simple graph.For any real function g :V-→ R and a subset S V,we write g(S) =∑v∈Sg(v).A function f :V-→ [0,1] is said to be a fractional dominating function(F DF) of G if f(N [v]) ≥ 1 holds for every vertex v ∈ V(G).The fractional domination number γf(G) of G is defined as γf(G) = min{f(V)|f is an F DF of G }.The fractional total dominating function f is defined just as the fractional dominating function,the difference being that f(N(v)) ≥ 1 instead of f(N [v]) ≥ 1.The fractional total domination number γ0f(G) of G is analogous.In this note we give the exact values ofγf(Cm × Pn) and γ0f(Cm × Pn) for all integers m ≥ 3 and n ≥ 2.     

符号混合控制问题的某些NP-完全性结果

Let G =(V, E) be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(x). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.     

单圈图的无符号狄利克雷谱半径

Let G be a simple connected graph with pendant vertex set ?V and nonpendant vertex set V_0. The signless Laplacian matrix of G is denoted by Q(G). The signless Dirichlet eigenvalue is a real number λ such that there exists a function f ≠ 0 on V(G) such that Q(G)f(u) = λf(u) for u ∈ V_0 and f(u) = 0 for u ∈ ?V. The signless Dirichlet spectral radiusλ(G) is the largest signless Dirichlet eigenvalue. In this paper, the unicyclic graphs with the largest signless Dirichlet spectral radius among all unicyclic graphs with a given degree sequence are characterized.     

A lower bound on the total signed domination numbers of graphs

Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.     

Heavy cycles in 2-connected triangle-free weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex v is called the weighted degree of v, denoted by dw(v). The weight of a cycle is defined as the sum of the weights of its edges. Fujisawa proved that if G is a 2-connected triangle-free weighted graph such that the minimum weighted degree of G is at least d, then G contains a cycle of weight at least 2d. In this paper, we proved that if G is a2-connected triangle-free weighted graph of even size such that dw(u) + dw(v) ≥ 2d holds for any pair of nonadjacent vertices u, v ∈ V(G), then G contains a cycle of weight at least 2d.     

A conjecture on k-factor-critical and 3-γ-critical graphs

For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The domination number γ(G) of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,if γ(G-v) γ(G) for any vertex v in G.A graph G is domination edge critical,if γ(G ∪ e) γ(G) for any edge e ∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical) if it is domination vertex critical(resp.domination edge critical) and γ(G) = k.Ananchuen and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is k-factor-critical.In this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

关于图的减控制与符号控制

给定一个图G=(V,E),一个函数f:V→{-1,0,1}被称为G的减控制函数,如果对任意v∈V(G)均有∑_μ∈N[v]f(μ)≥1。G的减控制数定义为γ^-(G)=min{∑_v∈Vf(v)|f是G的减控制函数}。图G的符号控制函数的正如减控制函数,差别是广{-1,0,1}换成{-1,1}。符号控制数γ_s(G)是类似的。本文获得γ^-G)和γ_s(G)的一些下界。同时也证明并推广了 Jean Dunbar等提出的一个猜想,即对任意 n阶 2部图 G,均有γ^-(G)≥ 4(n+1^1/2-1)-n成立。     

完全二部图的符号星控制数

近年来,研究图的符号星控制数颇引人注目,研究了完全二部图的符号星控制数.     

控制数与星独立数

本文，我们讨论星独立数、分数星独立数、分数控制数和控制数间的关系，利用规划理论给出了上述参数的一些性质。     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

Some Notes on Signed Edge Domination in Graphs

The closed neighborhood N_G[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge dominating function of G. The signed edge domination number γ_s^′(G) of G is defined as . Recently, Xu proved that γ_s^′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γ_s^′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γ_s^′(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.     

Domination number of cubic graphs with large girth

We show that every n‐vertex cubic graph with girth at least g have domination number at most 0.299871n+ O(n/g)<3n/10 + O(n/g) which improves a previous bound of 0.321216n+ O(n/g) by Rautenbach and Reed. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:131‐142, 2012     

极大全控点临界图

图G的点集S如果满足:VG-S(或VG)中每个点相邻于S中的某个点(或而不是它本身),则称点集S是一个控制集(或全控制集).图G的所有控制集(或全控制集)中最小基数的控制集(或全控制集)中的点数,称为控制数(或全控数),记为γ(G)(或γt(G)).在这篇文章中我们特征化γt-临界图且满足γt(G)=n-Δ(G)的图特征,这回答了Goddard等人提出的一个问题.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.