循环图的连通度

设Ｇ＝Ｇｎ（ｉ１,ｉ２,…,ｉｒ）是连通循环图,且ｘ（Ｇ）〈δ（Ｇ）,本文得到了其连通度的明确表达式：ｘ（Ｇ）＝ｍｉｎ（ｍ／Ｍ（ｎ／ｍ,Ｋ）／：ｍ是ｎ的真因子,且／Ｍ（ｎ／ｍ,Ｋ）／〈ｎ／ｍ－１）。     

循环图的Adam同构的性质

本文得到了任意两个连通循环图是(?)d(?)m同构的充要条件,并且还得到两个连通循环图是(?)d(?)m同构的另一必要条件。     

随机有向循环图的连通度

In this paper, we prove that almost all circulant digraphs are strongly connected. Furthermore, for any given positive integer m, we show that almost every circulant digraph C has connectivity at least m/1 m(d(C) 1), where d(C) is the vertex degree of C.     

循环图的1—因子化

本文证明了任意偶数阶连通循环图是1-可因子化的。 根据前两个定理这两个定理立即得证.     

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下:     

4连通图的可去边与4连通图的构造

本文引进了４连通图的可去边的概念,,并证明了４连通图Ｇ中不存在可去边的充要条件是Ｇ＝Ｃ５或Ｃ６,同时给出了ｎ阶４连通图的一个新的构造方法．     

循环图Cn〈j1,j2,…,jr,n／2〉的连通性

本文得到了奇数度循环图C_n是连通的充要条件及C_n不连通的情形.证明了三度连通循环图C_n同构于C_n<1,n/2>或C_n<2,n/2>.这一结果颇有意义.     

Star图互连网络的容错性分析

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数。当考察这两个参数时，总假设网络中和一台计算机相连接的所有计算机不会同时出现故障。该文证明了Star图互连网络的极小分离集和极小限制分离集的唯一性，然后得到了Star图的限制连通度是2n-4，当n=3,5和n≥7时，它的限制容错直径是|_3(n-1)/2_|+2，对于n =4, 6，限制容错直径是|_3(n-1)/2_|+3，即限制容错直径只比它的容错直径大1。     

h连通图中非临界点的个数

设Ｇ是ｈ连通的简单非完全图，ｖ中Ｇ的顶点，若ｋ（Ｇ－ｖ）≥ｋ（Ｇ），则称ｖ是Ｇ的非临界点，关于Ｇ中非临界点的个数，Ｖｅｌｄｍａｎ和苏健基分别给定了在不同条件下的下界，本文推广了他们的结果，得到了更一般的下界。     

循环圈的连通度

设G＝C_n（i₁,i₂,…,i_r）是连通循环圈,且k（G）＜δ（G）．本文得到了其连通度的明确表达式κ(G)=min{m|M(n/m,K)|:m是n的真因子,且|M(n/m,K)|相似文献   

小度数循环图的计数

循环图已被用于平行计算，网络等方面．循环图研究的一个基本问题是对互不同构的循环图进行计数．对于给定的一个正整数ｎ，用Ｃ（ｎ，ｋ）表示互不同构的具有几个顶点，度数为ｋ的连通循环图的个数．文中给出了度数为 ４和５的循环图的一般结构，并对ｎ＝ｐａｑｂ（ｐ，ｑ皆为素数，ａ，ｂ＞０），给出了Ｃ（ｎ，４）的计算公式．     

一类循环图中的Eulerian定向数

一般的图中Eulerian定向数的计数是#P-完全问题,但对于某些特殊图中的Eulerian定向数给出精确计数是完全有可能的.通过拆分解构的方法可以找到与一类循环图中Eulerian定向数有关的递推关系,从而给出该数的精确计数.前人的工作在于给出了一些近似估计.     

Constructing a Family of 4‐Critical Planar Graphs with High Edge Density

A graph is a k‐critical graph if G is not ‐colorable but every proper subgraph of G is ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.     

通过增强型萨格勒布指数对图排序

Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index(AZI index) of a graph G, which is defined as AZI(G) =∑uv∈E(G)( d_u d_v/d_u + d_v-2)~3,where E(G) is the edge set of G, d u and d v are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest(resp., the first two smallest) AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.     

On Edge-Colored Graphs Covered by Properly Colored Cycles

We characterize edge-colored graphs in which every edge belongs to some properly colored cycle. We obtain our result by applying a characterization of 1-extendable graphs. Received: April, 2003     

On Characterizations of Rigid Graphs in the Plane Using Spanning Trees

We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G. A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice.     

Calculating Ramsey Numbers by Partitioning Colored Graphs

In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for , in every edge coloring of with the colors red and blue, it is possible to cover all the vertices with k disjoint red paths and a disjoint blue balanced complete ‐partite graph. When the coloring of is connected in red, we prove a stronger result—that it is possible to cover all the vertices with k red paths and a blue balanced complete ‐partite graph. Using these results we determine the Ramsey number of an n‐vertex path, , versus a balanced complete t‐partite graph on vertices, , whenever . We show that in this case , generalizing a result of Erd?s who proved the case of this result. We also determine the Ramsey number of a path versus the power of a path . We show that , solving a conjecture of Allen, Brightwell, and Skokan.     

几何随机图大连通分支覆盖面积及其在传感器网络中的应用

随机网络中的大连通分支能体现一个网络的连通情况,是几何随机图研究的-个热点,具有重要的理论意义和应用价值.本文利用渗流理论,研究了几何随机图大连通分支覆盖面积所具有的性质,并将理论结果应用到大型无线传感器网络中,研究了无线传感器网络覆盖的性质.研究结果表明,对于节点服从泊松分布的大型无线传感器网络,其大连通分支覆盖区域大小与总区域大小的比值趋于-个常数,且并估计出了2维空间中没有被大连通分支所覆盖的连通区域(本文称为空洞)的大小.这些结果为衡量无线传感器网络性能提供了理论基础,对实际布网和网络优化等具有一定的指导意义.     

Graphs generated by Sidon sets and algebraic equations over finite fields

We study the spectra of several graphs generated by Sidon sets and algebraic equations over finite fields. These graphs are used to study some combinatorial problems in finite fields, such as sum product estimates, solvability of some equations and the distribution of their solutions.