共查询到20条相似文献,搜索用时 109 毫秒
1.
一个图的边染色称为是点可区别的,如果任意两个不同的顶点的关联边的颜色的集合不同.设Kn^-t表示从n阶完全图中删去t条彼此不相邻的边后所得到的图.本文对Kn^-t的点可区别正常边染色进行了讨论. 相似文献
2.
拟正则完全二部图的局部最可靠性 总被引:1,自引:0,他引:1
王应前 《高校应用数学学报(A辑)》2003,18(3):365-370
用P(G,ρ)表示顶点完全可靠,而边则以概率ρ∈(0,1)相互独立地出现故障的图G的全终端不可靠度,即G因边故障而变得不连通的概率.本文证明了边故障率ρ充分小时,拟正则完全二部图在具有相同点数和相同边数的图类中是惟一具有最小全终端不可靠度的图. 相似文献
3.
关于K-tn的点可区别正常边染色 总被引:1,自引:0,他引:1
一个图的边染色称为是点可区别的,如果任意两个不同的顶点的关联边的颜色的集合不同. 设K-tn表示从n阶完全图中删去t条彼此不相邻的边后所得到的图. 本文对K-tn的点可区别正常边染色进行了讨论. 相似文献
4.
一个图的边染色称为是点可区别的 ,如果任意两个不同的顶点的关联边的颜色的集合不同 .设K-tn 表示从 n阶完全图中删去 t条彼此不相邻的边后所得到的图 .本文对 K-tn 的点可区别正常边染色进行了讨论 . 相似文献
5.
6.
王彬 《数学物理学报(A辑)》2014,(6)
固定α_0∈[0,1)及β∈[0,1/2).该文引入如下随机图过程(G_t)t≥1:设在时刻1及2已存在图G_1=G_2,其中G_1的顶点为v_1,v_2且它们之间有2条边相连.当t≥3时,G_t定义如下:(i)G_(t-1)中任意顶点v不活跃的概率为α_0.顶点不活跃意味着其不能与t时刻新增加的顶点相连.此概率独立于自己以及其他顶点t-1之前的状态;(ii)以概率1-β增加一个新顶点v_t.在G_(t-1)中以概率dw(t-1)/∑vdv(t-1)选一顶点w,其中d_w(t-1)表w在G_(t-1)中的度.若w是活跃的则在v_t与w之间连1条边,否则在v_t上加个环;(iii)以概率β在G_(t-1)中删去一顶点u,其中u被选中的概率为(1-du(t-1)/∑vdv(t-1))/(n_(t-1)-1).此处,n_(t-1)是G_(t-1)的顶点个数.令N_k(t)表G_t中度为k的顶点个数.该文证明了G_t度分布的期望在2β/1-α_0=1附近存在一相变:当2β/1-α_01时,N_k(t)/t的期望是呈指数衰减的;当2β/1-α_01时,N_k(t)/t的期望是呈幂律衰减的. 相似文献
7.
黄煦艳 《数学的实践与认识》2005,35(6):206-210
假设n点m边的简单无向图G=(V,E)的每个顶点完全可靠,各边相互独立地以同一概率q(0q1)发生故障,则用G不连通的概率P(G,q)作为衡量网不可靠程度的指标.如果对于充分接近q0的所有q都有P(G,q)P(H,q),则称在边故障概率q~q0时,网络G比H可靠.证明了当q~0时,Kn,n(n4)是2n点n2边图中局部最优可靠的. 相似文献
8.
9.
10.
11.
We define the graph G1 recursively from Gt?1 by adding a point or a line with probability ? and q, respectively, if Gt?1 is not complete; if Gt?1 is complete we always add a point. By using recursions we investigate the probability distribution of the order and size of G? of the minimum and maximum orders for a fixed size, and of the minimum and maximum sizes for a fixed order. Expected values and generating functions are determined. 相似文献
12.
On bipartite zero-divisor graphs 总被引:1,自引:0,他引:1
A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3. 相似文献
13.
图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q1≥q2≥…≥qn.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤(n2).如果对于任意的G∈C(n,m)都有q1(G*)≥q1(G)成立,图G*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n... 相似文献
14.
A nonempty simple connected graph G is called a uniquely determined graph, if distinct vertices of G have distinct neighborhoods. We prove that if R is a commutative ring, then Γ(R) is uniquely determined if and only if either R is a Boolean ring or T(R) is a local ring with x2 = 0 for any x ∈ Z(R), where T(R) is the total quotient ring of R. We determine all the corresponding rings with characteristic p for any finite complete graph, and in particular, give all the corresponding rings of Kn if n + 1 = pq for some primes p, q. Finally, we show that a graph G with more than two vertices has a unique corresponding zero-divisor semigroup if G is a zero-divisor graph of some Boolean ring. 相似文献
15.
斯钦 《数学的实践与认识》2008,38(8):151-157
图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题. 相似文献
16.
Stefanie Gerke Dirk Schlatter Angelika Steger Anusch Taraz 《Random Structures and Algorithms》2008,32(2):236-261
We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n2) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008 相似文献
17.
OD-CHARACTERIZATION OF ALMOST SIMPLE GROUPS RELATED TO U6(2) 总被引:1,自引:0,他引:1
Let G be a finite group and π(G) = { p 1 , p 2 , ··· , p k } be the set of the primes dividing the order of G. We define its prime graph Γ(G) as follows. The vertex set of this graph is π(G), and two distinct vertices p, q are joined by an edge if and only if pq ∈π e (G). In this case, we write p ~ q. For p ∈π(G), put deg(p) := |{ q ∈π(G) | p ~ q }| , which is called the degree of p. We also define D(G) := (deg(p 1 ), deg(p 2 ), ··· , deg(p k )), where p 1 < p 2 < ··· < p k , which is called the degree pattern of G. We say a group G is k-fold OD-characterizable if there exist exactly k non-isomorphic finite groups with the same order and degree pattern as G. Specially, a 1-fold OD-characterizable group is simply called an OD-characterizable group. Let L := U 6 (2). In this article, we classify all finite groups with the same order and degree pattern as an almost simple groups related to L. In fact, we prove that L and L.2 are OD-characterizable, L.3 is 3-fold OD-characterizable, and L.S 3 is 5-fold OD-characterizable. 相似文献
18.
DU Beiliang WANG Jian Department of Mathematics Suzhou University Suzhou China Nantong Vocational College Nantong China 《中国科学A辑(英文版)》2004,47(3)
Let K_(m,n) be a complete bipartite graph with two partite sets having m and nvertices, respectively. A K_(p,q)-factorization of K_(m,n) is a set of edge-disjoint K_(p,q)-factorsof K_(m,n) which partition the set of edges of K_(m,n). When p=i and q is a prime number,Wang, in his paper "On K_(1,k)-factorizations of a complete bipartite graph" (Discrete Math,1994, 126; 359-364), investigated the K_(1,q)-factorization of K_(m,n) and gave a sufficientcondition for such a factorization to exist. In the paper "K_(1,k)-factorizations of completebipartite graphs" (Discrete Math, 2002, 259: 301-306), Du and Wang extended Wang'sresult to the case that q is any positive integer In this paper, we give a sufficient conditionfor K_(m,n) to have a K_(p,q)-factorization. As a special case, it is shown that the Martin's BACconjecture is true when p: q=k: (k+1) for any positive integer k. 相似文献
19.
20.
INVERSE MONOIDS OF GRAPHS 总被引:1,自引:0,他引:1
李为民 《应用数学学报(英文版)》2000,16(1):93-99
. IntroductionGraph endomorphism and its regularity property have been investigated in some literatures (of. [1--41 for examples). The invertibility is a stronger algebraic property thanregUlarity in semigroup theory. It is commonly agreed that inverse semigroups are the mostpromising class of semigroups for study. In this paper we first present a combinatorial characterization of an inverse monoid of a graph (Theorem 2.3). Then using this we prove thata bipartite graph with an inverse monoi… 相似文献