关于紧图的一些研究结果

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图类尚且不多,介绍从某些已知的紧图出发不断构造紧图的加边法,可以构造无穷多个紧图族.     

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

任意k紧优、奇异k紧优双环网无限族的构造

双环网 (double loopnetwork)是具有n个结点和出度为2的有向循环图,它是计算机互连网络的一类重要的拓扑结构,已应用于局域网和分布系统的设计中.给定结点数n,如何构造n个结点的具有最小直径的双环网? 这个问题受到广泛的关注. 与此有关的一个久而未决的主要问题是:任意给定k≥0, 是否有所谓k紧优双环网的无限族? 本文证明了: (1) 对于任意给定的k≥0, 可构造其中一个步长为1的k紧优双环网的无限族, 其结点数n(k,e,c)(其中e充分大)是e的2次整系数多项式且系数含有参数c; (2) 对于任意给定的k≥0, 可构造一个奇异k紧优双环网的无限族.     

Stone-ech紧化的正则Wallman性质

J.van Mill曾证明了定理:多重点的集合仍为强N_1紧的强N_1紧空间的任意紧化都是正则Wallman的;特别地强N_1紧空间的Stone-Cech紧化是正则Wallman的.本文证明了可以用局部有限的强N_1紧开集族覆盖的正规空间的Stone-Cech紧化是正则Wallman的.从而就Stone-Cech紧化的情况改进了van Mill的结果.     

Stone-ech紧化的正则Wallman性质

J.van Mill曾证明了定理:多重点的集合仍为强N_1紧的强N_1紧空间的任意紧化都是正则Wallman的;特别地强N_1紧空间的Stone-Cech紧化是正则Wallman的.本文证明了可以用局部有限的强N_1紧开集族覆盖的正规空间的Stone-Cech紧化是正则Wallman的.从而就Stone-Cech紧化的情况改进了van Mill的结果.     

关于紧优双环网络的无限族

双环网络是计算机互连网络和通讯系统的一类重要拓扑结构．1993年,李乔等人提出一个系统的构造方法,构造出69类0紧优和33类1紧优双环网络的无限族,并提出研究下述问题:求k(k>1)紧优双环网络的无限族．2003年,徐俊明等人给出一个4紧优双环网络的无限族．本文首先证明从每一个具体的0紧优双环网络出发,都可以构造若干0紧优双环网络无限族;结合同余方程组理论和数论中的素数理论,给出若干求一般k(k≥0)紧优双环网络无限族(包括非单位步长双环网络无限族)的方法．     

k紧优双环网的无限族的构造

双环网是计算机互连网络和通讯系统的一类重要拓扑结构,已广泛应用于计算机互连网络拓扑结构的设计中.利用L形瓦理论,结合中国剩余定理和二次同余方程的性质,给出了不同于参考文献中的任意k紧优双环网的无限族的构造方法,证明了对任意正整数k,若n(t)=3t2 At B,A=1,3,5,对于一定的B＞(k 1)2,均存在正整数t,使得{G(n(t);s(t))}是k紧优双环网的无限族,而且这样的无限族有无穷多类.作为定理的应用,给出了多类新的k紧优双环网的无限族.     

关于紧图和超紧图的几个结果

给出了一些 新的紧图,并对 不是超紧的紧图 作了一些讨论     

具有任意伸缩因子剪切波紧框架的构造

在处理高维数据的线状奇异性时,剪切波能有效克服小波的不足而成为当前研究热点.给出了两种具有紧支撑和任意伸缩因子的剪切波紧框架构造方法.一种是利用已知的带限小波构造.另一种是利用具有两尺度关系的小波构造.最后,基于已构造出的4带小波,用给出的方法成功地构造出了相应的剪切波紧框架.     

模糊数关于紧承下方图度量的线性性质

证明了紧承下方图度量不是平移不变的.对紧承下方图度量的代数运算的连续性进行了讨论.证明了关于紧承下方图度量,模糊数空间只能是嵌入到拓扑向量空间当中,但不嵌入赋范线性空间当中.并与关于上确界度量的结果进行了比较.最后,给出了一个紧承下方图度量的下界.     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

The degree-diameter problem for circulant graphs of degrees 10 and 11

This paper considers the degree-diameter problem for undirected circulant graphs. For degrees 10 and 11, newly discovered families of circulant graphs of arbitrary diameter are presented which are largest known and are conjectured to be extremal. They are also the largest-known Abelian Cayley graphs of these degrees. For each such family, the order of every graph in the family is defined by a quintic polynomial function of the diameter which is specific to the family. The elements of the generating set for each graph are similarly defined by a set of polynomials in the diameter. The existence of the graphs in the degree 10 families has been proved for all diameters. These graphs are consistent with a conjecture on the order of extremal Abelian Cayley and circulant graphs of any degree and diameter.     

The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.     

Ring graphs and complete intersection toric ideals

We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.     

A note on compact graphs

An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs.     

Q整图新类

对于一个简单图G, 方阵Q(G)=D(G)+A(G)称为G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别为G的度对角矩阵和邻接矩阵. 一个图是Q整图是指该图的无符号拉普拉斯矩阵的特征值全部为整数.首先通过Stanic 得到的六个顶点数目较小的Q整图,构造出了六类具有无穷多个的非正则的Q整图. 进而,通过图的笛卡尔积运算得到了很多的Q整图类. 最后, 得到了一些正则的Q整图.     

Independent packings in structured graphs

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs. Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.     

Decompositions of complete multipartite graphs

This paper answers a recent question of Dobson and Maruši? by partitioning the edge set of a complete bipartite graph into two parts, both of which are edge sets of arc-transitive graphs, one primitive and the other imprimitive. The first member of the infinite family is the one constructed by Dobson and Maruši?.     

On Cubic Graphs Admitting an Edge-Transitive Solvable Group

Using covering graph techniques, a structural result about connected cubic simple graphs admitting an edge-transitive solvable group of automorphisms is proved. This implies, among other, that every such graph can be obtained from either the 3-dipole Dip₃ or the complete graph K ₄, by a sequence of elementary-abelian covers. Another consequence of the main structural result is that the action of an arc-transitive solvable group on a connected cubic simple graph is at most 3-arc-transitive. As an application, a new infinite family of semisymmetric cubic graphs, arising as regular elementary abelian covering projections of K _3,3, is constructed.