图的三种符号星控制数

引入了图的符号星k限定控制的概念,从而求出了星图和轮图的符号星k控制数.还刻画了满足γ′_(ss)(G)=1/2(2r+s)的图,基中γ′_(ss)(G)表示图G的符号星控制数.最后对图的符号星部分控制的已有结果作了改进.     

关于给定符号圈控制数的图的刻画（英文）

设G=(V,E)是简单图.称一个函数f:E→{+1,-1}为图G的符号圈控制函数,若对G的每一导出圈C,有Σ_(e∈)E(C)f(e)≥1.G的符号圈控制数被定义为γ′_(sc)(G)=min{∑_(e∈E)f(e)|f是G的符号圈控制函数}.本文刻画了所有具有γ′_(sc)(G)=|E|-4的连通图G.     

图的逆符号边全控制数

设γ_(st)(G)是图G的逆符号边全控制数,p(n,k)是广义Petersen图.得到了γ_(st)(G)的两个上界,并且确定了γ_(st)(p(n,k)).     

图的k符号边控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)^/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)^/(G)的若干新下限,并确定了路和圈的k符号边控制数.     

关于图的符号边全控制数

引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想.     

一类联图的符号边控制数

设G=(V,E)是一个简单图,一个函数f:E→{-1,1},若满足∑_(e′∈N[e])f(e)≥1对E(G)中的每个边e都成立,则称f是图G的一个符号边控制函数,图G的符号边控制数定义为γ′_s(G)=min{∑_(e∈E)f(e)|f是G的符号边控制函数}.给出了联图C_(2k)+C_(2k)的符号边控制数.     

图的符号星部分控制数

引入了图的符号星部分控制的概念.设G=(V,E)是一个简单连通图, M是V的一个子集.一个函数f:E→{-1,1}若满足∑e∈E(v)f(e)≥1对M中的每个顶点v都成立,则称f是图G的一个符号星部分控制函数,其中E(v)表示G中与v点相关连的边集.图G的符号星部分控制数定义为γM(85)(G)=min{∑e∈Ef(e)|f是G的符号星部分控制函数}.在本文中我们主要给出了一般图的符号星部分控制数的上界和下界,并确定了路、圈和完全图的符号星部分控制数的精确值.作为我们引入的这一新概念的一个应用,求出了完全图的符号星k控制数.     

关于图的强符号全控制数

图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了：（1）一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;（2）确定了圈、轮图、完全图、完全二部图的强符号全控制数的值.     

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

On the Characterization of Maximal Planar Graphs with a Given Signed Cycle Domination Number

Let G =(V, E) be a simple graph. A function f : E → {+1,-1} is called a signed cycle domination function(SCDF) of G if ∑_(e∈E(C))f(e) ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ'_(sc)(G) = min{∑_(e∈E)f(e)| f is an SCDF of G}. This paper will characterize all maximal planar graphs G with order n ≥ 6 and γ'_(sc)(G) = n.     

Signed domination numbers of directed graphs

The concept of signed domination number of an undirected graph (introduced by J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater) is transferred to directed graphs. Exact values are found for particular types of tournaments. It is proved that for digraphs with a directed Hamiltonian cycle the signed domination number may be arbitrarily small.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

Hamiltonian threshold for strong products of graphs

We prove that the strong product of any at least non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ?(ln 2)D? stars K_1,D is not even hamiltonian. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 314–328, 2008     

Graceful signed graphs: II. The case of signed cycles with connected negative sections

In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Z_k, of admissible length k 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph.     

Edge Domination in Graphs of Cubes

The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the n-dimensional cube Q _n.     

Shorter signed circuit covers of graphs

A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.