关于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)是奇优美图.     

几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(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的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

一类4-正则平面图的邻点可区别关联色数

所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数.     

关于哈密顿线图的一个注记

一、 引言令 G 是顶点集合为 V(G)且边集合为 E(G)的简单图.图 G 的线图 L(G)是顶点集合为 E(G)的图,L(G)的两个顶点,e_1和 e_2是相邻接的当且仅当 e_1和 e_2在 G中有一个公共顶点.图 G 的一条通道是点与边的一个交替序列 v_0,e_1,v_1,…,v_(n-1),e_n,v_n 其中 e_i(i=     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

结盟结构对策的准核和伪核的结构

设N={1,2,…,n}为局中人集,N上的对策υ是2~N上的实值集函数,满足υ(ф)=0。N上的一个分类■={B_1,B_2,…,B_p}称为N上结盟结构。(N,υ,■)称为结盟结构对策。     

具有确定正对角元个数的本原矩阵的指数集

§1.引言一个n阶非负矩阵A称为是本原的,如果存在某个自然数k,使A~h>0。这样的自然数中的最小者称为A的本原指数,记作γ(A)。设A是n阶非负矩阵,定义A的伴随有向图D(A)=(V,E)为以V={1,2,…,n}为顶点集,以E={(i,j)|a_(ij)≠0}为弧集合的一个有向图。显然,D(A)完全刻划了A的零位模式(即A的零元素位置分布),从而完全反映了矩阵A的各种组合性质——     

在对称群中一类正则图所确定的极大子群

对称群的极大子群之确定,在多值逻辑理论和有限自动机理论中都有着重要而广泛的应用,同时也是置换群理论中的一个基本问题.本文提出了 k 次对称群中一类新的极大子群,k=h~m,m≥3,h≥7.设Γ=(Ω,E)是一个无向正则图,其中顶点集Ω={(α_1,…,α_m)|β_i∈Ω_h={10,1,…,h-1},i=1,…,m},边集 E={α,β〉|α=(α_1,…,α_m),β=(β_1,…,β_m)∈Ω,α_i≠β_i,i=1,….m}:G 是Γ的所自同构作成之群.于是,(1)G 是本原群,且G={g|g(x)=g(x_1,…,x_m)=(g_1(x_σ(1)),…,g_m(x_σ(m))),σ∈S_m(集合{1,…,m}上的对称群),g,∈S_h(Ω_h 上的对称群),i=1,…,m};(2)若 h 为奇数 h=2_n+1且 n 为偶数或 h-1>m,则 G 是 k 次对称群 S_k 中的极大子群;(3)若 k 为偶数且2(k-1)>m,则 G 是 k 次交代群 A_k 中的极大子群.     

若干图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u|vu∈E(G)}∪{v}.并且vχsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数.本文得到了一些特殊图的点强全色数χvTs(G),并提出猜想:对于简单图G,有k(G)≤χvTs(G)≤k(G)+1,这里k(G)表示图G中所有顶点间距离不超过2的点集的最大顶点数.     

均衡二部图中含2k条指定边的k个独立圈及2-因子

得到了对于二部图G=(V_1,V_2;E),当|V_1|=|V_2|=n≥2k+1时的结果:对G中任意2k条独立边e_1,e_1~*,…,e_k,e_k~*,G中一定存在k个独立的4-圈C_1,C_2,…,C_k,使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i).并在此基础上进一步证明了当|V_1|=|V_2|=n≥3k时若对任意两顶点x∈V_1,y∈V_2,都有d(x)+d(y)≥2n-k+1成立,则G有一个2-因子含有k+1个独立圈C_1,C_2,…,C_(k+1)使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i)且|C_i|=4.     

广义Peterson图的邻点可区别的全染色

设P_(n,k)是一个简单图,其顶点集和边集分别为:V(P_(n,k))={u_0,u_1,…u_(n-1),v_0,v_1,…v_(n-1)},E(P_(n,k))={u_iu_(i+1),u_iv_i,v_iv_(1+k)},则称P_(n,k)为广义Peterson图,其中n≥5,0相似文献   

C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.     

Pansystems Whole-Part Relation Analysis and Triple Covering Systems

Let A_n={1,2,…,n} and let ％={B_1,B_2,…,B_r} where B_1、B_2,…, B_r are subsets of A_n each of size m. is said to cover all the triples (i, j, k), 1≤i2/3, then V(m, n) is a function of the fraction m/n only and the values of V(m, n) are determined for all m, n with m/n≥2/3. The value of V(m, n) for m/n<2/3 is also discussed.     

一道以二进制为背景的高考题

(2010年湖北文)若规定E={a1,a2,...,a10}的子集{ai1,ai2,...,ain}为E的第k个子集,其中k=2i1-1+2i2-1+...2in-1,则(1){a1,a2}是E的第__个子集; (2)E的第211个子集是__.     

在对称群中一类正则图所确定的极大子群

对称群的极大子群之确定,在多值逻辑理论和有限自动机理论中都有着重要而广泛的应用,同时也是置换群理论中的一个基本问题。本文提出了k次对称群中一类新的极大子群,k=h~m,m≥3,h≥7。 设Г=(Ω,E)是一个无向正则图,其中顶点集Ω={(α_1,…,α_m)|α_i∈Ω_h={0,1,…,h-1},i=1,…,m},边集E={<α,β>|α=(α_1…,α_m),β=(β_1,…,β_m)∈Ω,a_i≠β_i,i=1,…。m};G是Г的所自同构作成之群。于是,(1)G是本原群,且 G={g|g(x)=g(x_1,…x_m)=(g_1(x_(σ(1))),…,g_m(x_(σ(m))),σ∈S_m (集合{1,…,m}上的对称群),g_i∈S_h(Ω_h上的对称群),i=1,…,m};(2)若h为奇数h=2n+1且n为偶数或h-1>m,则G是k次对称群S_k中的极大子群;(3若h为偶数且2(h-1)>m,则G是k次交代群A_k中的极大子群。     

实 Clifford 分析中的一个边值问题

考虑以 e_A=e_(α1)…e_(αh)(A={α_1,α_2,…,α_h)(?){1,2,3,…,n),1≤α_1<α_2<…<α_h≤n)为基底元素的实 Clifford 代数 A_n(R),其中 e_1=1,e_k~2=-1(k=2,3,4,…,n),e_ke_m e_me_k=0(k≠m,k,m=2,3,4,…,n).并用 V_n 表示由向量组 e_1,e_2,…,e_n 所张成的 A_n(R)的子空间,V_n 中元素为 x=(?)x_ke_k,A_n(R)中的     

5-一致超图的全横贯

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.     

具次约束的最优树形图问题

给定一有向图G_0,其某一结点v_s称为特定结点,它共有p条出弧:α_1,α_2,…,α_p,分别指向结点v_1,v_2,…,v_p,这p个结点称为(v_s的)邻点。令T为G_0的一个支撑树形图,若其结点v_s有且仅有k条出弧,则T称为(k)支撑树形图。设对G_0的每一条弧α,均给以一弧长w_0(α),则弧长之和最小的支撑树形图称为最优树形图。若在一个最优树形图中,其结点v_s有且仅有k条出弧,则此最优树形图称为最优(k)树形图。而在所有(k)支撑树形图中,其弧长之和最小者称为(k)最优树形图。显然,一个最优(k)树形图必为     

一类Boussinesq方程的整体解的存在性与不存在性

主要考察Boussinesq方程v_(tt)-v_(xx)+v_(xxx)=σ(v)_(xx),x∈R的整体解的存在性和blow-up问题,当σ(v)=-β(|v|~p v),β0,p0时,通过采用构造稳定集(位势井)W={v∈H~1(R)|||v_x||~2+||v||~22(p+2)/p d}和不稳定集V={v∈H~1(R)|||v_x||~2+||v||~22(p+2)/p d}的方法,得到了W和V在上述方程的流下是不变的,并证明了如果初始能量E(0)≤d,那么当初值v_0∈(?)时,问题存在惟一整体解;当初值v_0∈V时,问题的解在有限时刻T_1∈(t_1,t_1+4φ(t_1)/pφ′(t_1))发生爆破.     

二部图上完美匹配的正交匹配分解

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。