消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

一般图的哈密顿图的研究进展

1991年刘振宏和李明楚在南京大学召开的首届哈密顿图研讨会的综述文章中说"要给出一个一般图具有哈密顿圈的充分条件是一件非常不容易的事"。因哈密顿图是含哈密顿圈的图类,如此哈密顿图主要有六个方向:哈密顿圈、哈密顿连通、泛圈图、点泛圈图、泛连通图、最短路径泛圈图。本文中,我们就给出一般图的这些领域新进展的小综述。     

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

随机映射图的局部图

讨论了当n趋向无穷大时,n个顶点的随机映射图的k-局部图收敛于随机生长过程时刻k的二叉图,这儿,k-局部图是随机映射图前k个顶点{1,2,…,k}所生成的最小图.在这种意义下,称随机映射图为渐近二叉的.     

随机映射图的局部图

讨论了当n趋向无穷大时,n个顶点的随机映射图的k-局部图收敛于随机生长过程时刻k的二叉图,这儿,k-局部图足随机映射图前k个顶点{1,2,…,k}所生成的最小图.在这种意义下,称随机映射图为渐近二叉的.     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

2pq阶Cayley图是Hamilton图

一、引言对Cayley图的Hamilton性的研究近几年有所突破[1]现最好的结果是[2]的主要定理:若群G上的换位子群C′是p~n(p是素数,n是正整数)阶循环群时,G上的每个Cayley图皆为Hamilton图。1987年D.Marusic还证明了2p~2(p是素数)阶Cayley图为Hamilton图[4]。本文用群的构造理论证明:2pq(p,q是素数)阶Cayley图是Hamilton图。本文中所提到的群G皆指有限群;群的有关术语和记号同于文献[3];图的有关术     

准模糊图拟阵基图

在准模糊图拟阵的基础上,提出准模糊图拟阵的基图,并讨论准模糊图拟阵基图的性质和特征。     

正规Cayley图

综述了自１９９０年以来１２－传递图研究的一些新成果，正规Ｃａｙｌｅｙ图的相关结论。     

Reaction Graphs

Chemical reaction graphs (for a fixed type of rearrangement) are orbital graphs for transitive permutation representations of symmetric groups, so algebraic combinatorics and group theory are effective tools for studying such properties as their connectivity and automorphisms. For example, we construct orbital graphs (and, hence, reaction graphs) from Cayley diagrams by contracting edges, and use graph-embeddings in surfaces to determine the automorphism groups of these graphs. We apply these ideas to the rearrangements of the P ₇ ^3- -ion and of bullvalene, together with some purely mathematical examples of reaction graphs.     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Biclique-Helly Graphs

A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs.     

图的因子和因子分解的若干进展

本文综述了图的的因子和因子分解近年来的一些新结果。主要有图的因子与各种参数之间的关系,图有某种因子的一些充分必要条件,特别是图有ｋ－因子的一些充分条件以及关于图的因子分解和正交因子分解的一些新结果。文中提出了一些新的问题和猜想。     

龙图的奇优美性

根据复杂网络研究的需要,定义(k,m)-奇优美龙图和一致(k,m)-龙图作为复杂网络的模型.这些龙图的奇优美性得到研究,其中证明方法可算法化.     

Transitive,Locally Finite Median Graphs with Finite Blocks

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. Sandi Klavžar: Supported by the Ministry of Science of Slovenia under the grant P1-0297. The author is also with the Faculty of Mathematics and Natural Sciences, University of Maribor, Slovenia and the Institute of Mathematics, Physics and Mechanics, Ljubljana.     

A Generalization of Strongly Regular Graphs

Motivated from an example of ridge graphs relating to metric polytopes, a class of connected regular graphs such that the squares of their adjacency matrices are in certain symmetric Bose-Mesner algebras of dimension 3 is considered in this paper as a generalization of strongly regular graphs. In addition to analysis of this prototype example defined over (MetP₅)^*, some general properties of these graphs are studied from the combinatorial view point.AMS Subject Classification: 05E30.     

蛛网图及渔网图的邻点可区别I-全染色

通过揭示完全蛛网图和渔网图的结构特点,研究了它们的邻点可区别I-全染色问题,并运用构造法给出了其邻点可区别I-全染色,从而获得了它们的邻点可区别I-全色数.     

Half-Transitive Graphs of Prime-Cube Order

We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p ³ and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p ³ and exponent p ², and up to isomorphism there are exactly (p – 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.     

On Balanced Graphs

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Received: April, 2004