Pm×Kn的邻点可区别全色数

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

$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积的邻点可区别全色数.     

图$P_m\times P_n, P_m\times C_n$ 和C_m\times C_n$}的邻点可区别全色数的注记

设 $G$ 是一个简单图. 设$f$是从$V(G) \cup E(G)$到 $\{1, 2,\ldots, 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)\neq C_f(v)$, 那么称 $f$ 为$k$-邻点可区别全染色 (简记为$k$-$AVDTC$). 设     

Backbone coloring for triangle-free planar graphs

Acta Mathematicae Applicatae Sinica, English Series - Let G be a graph and H a subgraph of G. A backbone-k-coloring of (G, H) is a mapping f: V(G) → {1, 2, ···, k} such that...     

On the metric dimension of barycentric subdivision of Cayley graphs

Acta Mathematicae Applicatae Sinica, English Series - In a connected graph G, the distance d(u, v) denotes the distance between two vertices u and v of G. Let W = {w 1, w 2, ···, w...     

若干笛卡尔积图的邻点可区别E-全染色

图G(V,E)的k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射,如果u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.     

关于p3n的优美性

设G(V,E)是一个简单图,对自然数k,当V(Gk)=V(G),E(Gk)=E(G)∪{uv|d(u,v)=k},则称图Gk为k-次方图.本文证明了图P3n的优美性.     

关于P_(r,(2s-1))的奇优美标号

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2 |E|-1}满足1)对任意的u,v∈V,若u≠v,则(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4){g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇优美图,f称为G的奇优美标号.Gnanajoethi提出了一个猜想:每棵树都是奇优美的.证明了图P_(r,(2s-1)是奇优美图.     

关于图P_n~k的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的.     

On the Circumference of 3-connected Graphs

Let C be a longest cycle in the 3-connected graph G and let H be a component of G - V(C) such that ¦V(H)¦≥ 3. We supply estimates of the form ¦C¦ ≥ 2d(u) + 2d(v) ? a (4 ≤ a ≤ 8), where u, v are suitably chosen non-adjacent vertices in G.     

关于图K_(2n)-E(C_4)的点可区别边色数

图G的一个k-正常边染色f被称为点可区别边染色是指任何两点的点及其关联边的色集合不同,所用最小的正整数k被称为G的点可区别边色数,记为x′_(vd)(G).用K_(2n)-E(C_4)表示2n阶完全图删去其中一条4阶路的边后得到的图,文中得到了K_(2n)-E(_4)的点可区别边色数.     

点度与图的上可嵌入性

本文证明了:(1) 设G是2-连通简单图,且不含K_3,若对任意一对距离为2的点u,u,有max{d(u),d(u)}>n/3-1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;(2) 设G是3-连通简单图,若对任意依次相邻的三点u,u,W,有max{d(u),d(u),d(w)}≥n/6+1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/6+1"是最好的.     

直径为4的树的奇强协调性

对简单图G=〈V,E〉,如果存在一个映射f:V→{0,1,2,…,2 E-1}满足1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv;3){g(e)e∈E}={1,3,5,…,2 E-1},则称G为奇强协调图,f称为G的奇强协调标号.给出了直径为4的树的奇强协调标号.     

图K_(2n)\E(F_4)(n≥12)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果.f满足:1)对任意的uv,uw∈E(G),v≠w,有.f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}.研究了图K_(2n)\E(F_4)(n≥12)的点可区别边色数.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

轮与星的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果■u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与星的多重联图的邻点可区别E-全色数.     

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

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△.     

C_m·S_n的D(2)-点可区别边色数

对阶数不小于3的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的颜色数称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点u,v之间的最短距离.得到了Cm.Sn的D(2)-点可区别边色数.     

图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,κ}的映射,κ为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的κ-点可区别边染色法,而最小的κ被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K_(2n)\E(K_(2,m))(n≥9,m≥3)的点可区别边色数.     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.