图的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=(V,E)是一个图,对于图G的-个函数f:E→{-1,1},如果对任意e∈E(G),均有∑f(e')≤1,则称,为图G的一个逆符号边控制函数.图G的逆符号边控制数(～γ's)(G)=e'∈N[e]max{∑,(e)|f,为图G的一个逆符号边控制函数}.本文在定义了逆符号边控制数的基础上,得到了图e∈E的逆符号边控制数的几个上界.     

一类联图的符号边控制数

设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是一个图,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-哈密尔顿的和哈密尔顿连通的相关结果.     

Petersen图的Hamilton性和边色数

对简单图G(V,E),定义图G的关联图I(G)为V(I(G))={(ve)|v∈V(G)且e∈E(G)和v与e关联},E(I(G))={(ue,vf)Iu=v或e=f或uv=e或uv=f}.本文证明了Petersen图可被分解为边不交的Hamilton-圈和一个1-因子的并.     

广义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相似文献   

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

无爪图的次与Hamilton连通性

本文证明了：设G是n阶、k（≥3）连通无爪图，且不含同构于B的导出子图，若存在点v_0∈V（G），使d（v_0）≥n-2k＋4，则G是Hamilton连通的．     

关于梅花图的优美性

<正> 对于一个简单图 G=(V,E),若对每一个 v∈V,存在一个整数 l(v)(称为顶点 v的标号)使满足:(1)(?)u,v∈V,若 u≠v,,则 l(u)≠l(v);(2)max{l(v)|v∈V}=|E|;(3)(?)e′,e″∈E,若 e′≠e″,则 l′(e′)≠l′(e″),这里 l′(e)定义为|l(u)-l(v)|,此时若 e=uv,则称 G 为优美图(graceful graph).     

直径为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的树的奇强协调标号.     

NASH EQUILIBRIUM OF TWO GAME MODELS ON THE RANDOM SOCIAL NETWORK

A graph $G$ is $k$-triangular if each of its edge is contained in at least $k$ triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1 T_2\cdots T_k$ in $G$ such that for $1\leq i\leq k-1, |E(T_i )\cap E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ if $j>i+1$. Two edges $e,e''\in E(G)$ are triangularly connected if there is a triangle-path $T_1,T_2,\cdots, T_k$ in $G$ such that $e\in E(T_1)$ and $e''\in E(T_k)$. Two edges $e,e''\in E(G)$ are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph $G$ is ${\mathbb Z}_3$-connected, unless it has a triangularly connected component which is not ${\mathbb Z}_3$-connected but admits a nowhere-zero 3-flow.     

单圈图的最大特征值的上界的改进

Let G（V, E） be a unicyclic graph, Cm be a cycle of length m and Cm G, and ui ∈ V（Cm）. The G - E（Cm） are m trees, denoted by Ti, i = 1, 2,..., m. For i = 1, 2,..., m, let eui be the excentricity of ui in Ti and ec = max{eui ： i = 1, 2 , m}. Let κ = ec＋1. Forj = 1,2,...,k- 1, let δij = max{dv ： dist（v, ui） = j,v ∈ Ti}, δj = max{δij ： i = 1, 2,..., m}, δ0 = max{dui ： ui ∈ V（Cm）}. Then λ1（G）≤max{max 2≤j≤k-2 （√δj-1-1＋√δj-1）,2＋√δ0-2,√δ0-2＋√δ1-1}. If G ≌ Cn, then the equality holds, where λ1 （G） is the largest eigenvalue of the adjacency matrix of G.     

完全多部图的符号边控制数的界

$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

Zeros of Monomial Brauer Characters

Let G be a finite group and p be a fixed prime. A p-Brauer character of G is said to be monomial if it is induced from a linear p-Brauer character of some subgroup(not necessarily proper) of G. Denote by IBr_m(G) the set of irreducible monomial p-Brauer′characters of G. Let H = G′O~p′(G) be the smallest normal subgroup such that G/H is an abelian p′-group. Suppose that g ∈ G is a p-regular element and the order of gH in the factor group G/H does not divide |IBr_m(G)|. Then there exists ? ∈ IBr_m(G) such that ?(g) = 0.     

关于完全三部图色唯一性的一个注记

Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.     

有向跳图的生成欧拉子有向图

一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.     

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

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_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

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

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

具有两个p''维非线性不可约特征标的非可解群

McKay猜想是有限群表示理论中的一个重要问题.本文考虑了具有两个p'维不可约特征标的非可解群群G,并证明了McKay猜想对此类群成立.更进一步,当p为奇素数时,下面结果成立:p=3,G≌PSL_2(7)或存在一个正规2-群N,满足G/N≌PSL_2(5).