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

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

书本图Bm的协调和相继标号

本文给出了书本图Ｂ２ｍ的ｍ种不同的相继标号和Ｂ４ｍ＋１的ｍ种不同的相继标号。因而，书本图Ｂｍ是相继图的充分条件为：ｍ＞１且ｍ≠（３ｍｏｄ４）。这一条件也是书本图Ｂｍ是协调图的充要条件。     

关于n-可扩图的一些结果

本文讨论了关于m-可扩图的两个极值问题；并考查了下述图类的n-可扩性；正则偶图，单位区间图和分裂图。     

（a,b,k）—临界图

设Ｇ是一个图且设ａ，ｂ是非负整数，ａ〈ｂ。如果消去Ｇ的任意ｋ个顶点剩下的图有〔ａ，ｂ〕因子，则称图Ｇ是（ａ，ｂ，ｋ）－临界图。本文给出了一个图是（ａ，ｂ，ｋ）－临界图的一个充分必要条件。讨论了该条件的一些应用，研究了（ａ，ｂ，ｋ）－临界图的性质。     

One-step模糊图及相关的分解定理

主要研究一种特殊的模糊图(即one-step模糊图)的性质。提出了one-step模糊图、Hamiltonian模糊图、r-正则模糊图、二部模糊图、连通模糊图等概念,给出了强one-step Hamiltonian模糊图、强one-step r-正则模糊图、强one-step二部模糊图、强one-step连通模糊图的构造、强one-step模糊图在笛卡尔积、合成、补运算下的的简易表达式、one-step模糊图的分解定理以及强one-step模糊图在笛卡尔积运算下保持不变的一些性质,证明了任意模糊图可以分解为one-step模糊图。     

(g,f)-消去图的若干充分条件

设 G是一个图 ,用 V(G)和 E(G)表示它的顶点集和边集 ,并设 g和 f是定义在 V(G)上的两个整数值函数且 g 相似文献   

紧图的两个结果及其应用

双随机矩阵有许多重要的应用, 紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值． 确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果：任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图． 利用这两个结果,从已知紧图可构造出无穷多个紧图族．     

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

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

平面对偶图哈密顿性的一个充分条件

提出了平面单图的对偶图是哈密顿图的一个充分条件     

广义联图的正则性

讨论了两个图的广义联图的End-正则性,给出了当图X、Y的广义联图G（y1,…ym）End-正则时,图X也End-正则应满足的条件。     

Two sufficient conditions for non-normal Cayley graphs and their applications

A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in the full automorphism group of Cay(G, S). In this paper, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, five infinite families of connected non-normal Cayley graphs are constructed. As an application, all connected non-normal Cayley graphs of valency 5 on A5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A5, while Xu et al. have proved that As is a 4-CI group.     

Graphically abelian groups

We define a group G to be graphically abelian if the function g?g⁻¹ induces an automorphism of every Cayley graph of G. We give equivalent characterizations of graphically abelian groups, note features of the adjacency matrices for Cayley graphs of graphically abelian groups, and show that a non-abelian group G is graphically abelian if and only if G=E×Q, where E is an elementary abelian 2-group and Q is a quaternion group.     

Normality of Tetravalent Cayley Graphs of Odd Prime-cube Order and Its Application

Let p be an odd prime. In this paper we prove that all tetravalent connected Cayley graphs of order p^3 are normal. As an application, a classification of tetravalent symmetric graphs of odd prime-cube order is given.     

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．     

p~2阶弧传递循环图的正规性条件

群G关于S的有向Cayley图X=Cay(G,S)称为pk阶有向循环图,若G是pk阶循环群.利用有限群论和图论的较深刻的结果,对p2阶弧传递(有向)循环图的正规性条件进行了讨论,证明了任一p2阶弧传递(有向)循环图是正规的当且仅当(|Aut(G,S)|,p)=1.     

On the Classification of Arc-transitive Circulant Digraphs of Order Odd-Prime-Squared

A Cayley graph F = Cay（G, S） of a group G with respect to S is called a circulant digraph of order pk if G is a cyclic group of the same order. Investigated in this paper are the normality conditions for arc-transitive circulant （di）graphs of order p^2 and the classification of all such graphs. It is proved that any connected arc-transitive circulant digraph of order p^2 is, up to a graph isomorphism, either Kp2, G（p^2,r）, or G（p,r）[pK1], where r｜p- 1.     

Normal Cayley graphs of finite groups

LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ₄×ℤ₂ orG≅Q ₈×ℤ ₂ ^r (r⩾0) and that every finite group has a normal Cayley digraph, where Z_m is the cyclic group of orderm and Q₈ is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.     

THE NORMALITY OF CAYLEY GRAPHS OF SIMPLE GROUP A5 WITH SMALL VALENCIES

Let G be a finite group and S a subset of G not containing the identity element 1. We define the Cayley (di)graph X = Cay(G, S) of G with respect to S by V(X) = G,E(X) = {(g, sg) [ g ∈ G, s ∈ S}. A Cayley (di)graph X = Cay(G, S) is called normal if GR A = Aut(X). In this paper we prove that if S = {a, b, c} is a 3-generating subset of G = A5 not containing the identity 1, then X = Cay(G, S) is a normal Cayley digraph.     

一类拟二面体群的四度Cayley图的正规性

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了4m阶拟二面体群G=a,b|a~(2m)=b~2=1,a~b=a~(m+1)的4度Cayley图的正规性,其中m=2~r,且r2,并得到拟二面体群的Cayley图的同构类型.     

On isomorphisms of circulant digraphs of bounded degree

C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n₁n₂ and degree m, where gcd(n₁,n₂)=1, n₁ divides 4k, where k is odd and square-free, and every prime divisor of n₂ is greater than m, or, if Γ is a circulant graph, every prime divisor of n₂ is greater than 2m. Then Γ is a CI-digraph of Z_n. In this paper we verify that this conjecture is true.