几乎无爪图的叶子数较少的生成树

A spanning tree with no more than 3 leaves is called a spanning 3-ended tree.In this paper, we prove that if G is a k-connected(k ≥ 2) almost claw-free graph of order n and σ_(k+3)(G) ≥ n + k + 2, then G contains a spanning 3-ended tree, where σk(G) =min{∑_(v∈S)deg(v) : S is an independent set of G with |S| = k}.     

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.     

和图、整和图与模和图的几个结果

Let N denote the set of positive integers. The sum graph G^＋（S） of a finite subset S belong to N is the graph （S, E） with uv ∈ E if and only if u ＋ v ∈ S. A graph G is said to be a sum graph if it is isomorphic to the sum graph of some S belong to N. By using the set Z of all integers instead of N, we obtain the definition of the integral sum graph. A graph G = （V, E） is a mod sum graph if there exists a positive integer z and a labelling, λ, of the vertices of G with distinct elements from {0, 1, 2,..., z - 1} so that uv ∈ E if and only if the sum, modulo z, of the labels assigned to u and v is the label of a vertex of G. In this paper, we prove that flower tree is integral sum graph. We prove that Dutch m-wind-mill （Dm） is integral sum graph and mod sum graph, and give the sum number of Dm.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

树的L(3,2,1)-标号问题

An L(3,2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all non-negative integers(labels) such that |f(u)-f(v)|≥3 if d(u,v)=1,|f(u)-f(v)≥2 if d(u,v)=2 and |f(u)-f(v)|≥1 if d(u,v)=3.For a non-negative integer k,a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k.The L(3,2,1)-labeling number of G,denoted by λ_(3,2,1)(G), is the smallest number k such that G has a k-L(3,2,1)-labeling.In this article,we characterize the L(3,2,1)-labeling numbers of trees with diameter at most 6.     

Constructive characterizations of (γp,γ)- and (γp,γpr)-trees

Let G = (V,E) be a graph without isolated vertices.A set S V is a domination set of G if every vertex in V - S is adjacent to a vertex in S,that is N[S] = V.The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S C V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S V is a power domination set of G if all vertices of V can be observed recursively by the following rules: (i) all vertices in N[S] are observed initially,and (ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed (by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G =(V,E) be a graph without isolated vertices.A set S  V is a domination set of G if every vertex in V -S is adjacent to a vertex in S,that is N[S] = V .The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S  V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S]has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S  V is a power domination set of G if all vertices of V can be observed recursively by the following rules:(i) all vertices in N[S] are observed initially,and(ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed(by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

关于H-cordial图和semi-H-cordial图的若干结论（英文）

I. Cahit calls a graph H-cordial if it is possible to label the edges with the numbers from the set{1,-1} in such a way that, for some k, at each vertex v the sum of the labels on the edges incident with v is either k or-k and the inequalities |v(k)-v(-k)| ≤ 1 and|e(1)-e(-1)| ≤ 1 are also satisfied. A graph G is called to be semi-H-cordial, if there exists a labeling f, such that for each vertex v, |f(v)| ≤ 1, and the inequalities |e_f(1)-e_f(-1)| ≤ 1 and |vf(1)-vf(-1)| ≤ 1 are also satisfied. An odd-degree(even-degree) graph is a graph that all of the vertex is odd(even) vertex. Three conclusions were proved:(1) An H-cordial graph G is either odd-degree graph or even-degree graph;(2) If G is an odd-degree graph, then G is H-cordial if and only if |E(G)| is even;(3) A graph G is semi-H-cordial if and only if |E(G)| is even and G has no Euler component with odd edges.     

Frequency Assignment through Combinatorial Optimization Approach

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)|(?)2 if d(x, y)=1 and |f(x)-f(y)|(?)1 if d(x,y)=2. The L(2,1)-labeling numberλ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v) : v∈V(G)}=k. We study the L(3,2,1)-labeling which is a generalization of the L(2,1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds ofλs(G) of the graph.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

树的导出匹配覆盖

The induced matching cover number of a graph G without isolated vertices,denoted by imc(G),is the minimum integer k such that G has k induced matchings M1,M2,…,Mk such that,M1∪M2 ∪…∪Mk covers V(G).This paper shows if G is a nontrivial tree,then imc(G) ∈ {△*0(G),△*0(G) + 1,△*0(G)+2},where △*0(G) = max{d0(u) + d0(v) :u,v ∈ V(G),uv ∈ E(G)}.     

图的邻点可区别全色数的一个上界

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.
Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.     

完全图的Cantesian积的L(2,1)-圆标定

For positive integers j and k with j ≥ k, an L（j, k）-labeling of a graph G is an assignment of nonnegative integers to V（G） such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L（j, k）-labeling of a graph G is the difference between the maximum and minimum integers it uses. The λj, k-number of G is the minimum span taken over all L（j, k）-labelings of G. An m-（j, k）-circular labeling of a graph G is a function f ： V（G） →{0, 1, 2,..., m - 1} such that ｜f（u） - f（v）｜m ≥ j if u and v are adjacent; and ｜f（u） - f（v）｜m 〉 k ifu and v are at distance two, where ｜x｜m = min{｜xl｜, m-｜x｜}. The minimum integer m such that there exists an m-（j, k）-circular labeling of G is called the σj,k-number of G and is denoted by σj,k（G）. This paper determines the σ2,1-number of the Cartesian product of any three complete graphs.     

环状硅酸盐图的友好指数集

Let G be a graph with vertex set V(G) and edge set E(G). A labeling f : V(G) →Z2 induces an edge labeling f*: E(G) → Z2 defined by f*(xy) = f(x) + f(y), for each edge xy ∈ E(G). For i ∈ Z2, let vf(i) = |{v ∈ V(G) : f(v) = i}| and ef(i) = |{e ∈ E(G) : f*(e) =i}|. A labeling f of a graph G is said to be friendly if |vf(0)- vf(1)| ≤ 1. The friendly index set of the graph G, denoted FI(G), is defined as {|ef(0)- ef(1)|: the vertex labeling f is friendly}. This is a generalization of graph cordiality. We investigate the friendly index sets of cyclic silicates CS(n, m).     

一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.     

L7（3）与GL7（3）的OD-刻画

对于任意一个有限群G,令π（G）表示由它的阶的所有素因子构成的集合.构建一种与之相关的简单图,称之为素图,记作Γ（G）.该图的顶点集合是π（G）,图中两顶点p,g相连（记作p～q）的充要条件是群G恰有pq阶元.设π（G）={P₁,p2,…,p_x}.对于任意给定的p∈π（G）,令deg（p）:=|{q∈π（G）|在素图Γ（G）中,p～q}|,并称之为顶点p的度数.同时,定义D（G）:=（deg（p₁）,deg（p₂）,…,deg（p_s））,其中p₁2<…相似文献   

Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.