6p阶2度有向Cayley图的正规性

群G的Cayley有向图X=Cay(G,S)叫做正规的,如果G的右正则表示R(G)在X的全自同构群Aut(X)中正规.决定了6p(p素数)阶2度有向Cayley图的正规性,发现了一个新的2度非正规Cayley有向图.     

4p阶二面体群连通3度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)称为正规的,如果G的右正则表示R(G)在X的自同构群Aut(X)中是正规的.设G是4p阶二面体群(p为素数).考察了Cay(G,S)连通3度的正规性,并给出了这些图的全自同构群.     

一类非正规Cayley有向图

本文研究了2p2(p奇素数)阶非交换群上两度Cayley有向图的正规性,发现 了一无限族非正规的Cayley有向图.     

二面体群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图进行了分类．     

有限循环群上的Cayley有向图的哈密顿分解

本文给出了有限循环群上的Cayley有向图Cay(M,G)可哈密顿分解的一个充分条件,并证明了当|M|=2时此条件还是必要的.     

半二面体群的小度数Cayley图

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在Aut X中正规.研究了4m阶半二面体群G=〈a,b a2m=b2=1,ab=am-1〉的3度和4度Cayley图的正规性,其中m=2r且r>2,并得到了几类非正规的Cayley图.     

一类拟二面体群的四度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图的同构类型.     

2p2阶3度Cayley图

Cayley图Cay(G,S)称之为正规的,如果G的右正则表示是Cay(G,S)全自同构群的正规子群。本文决定了2p~2(p为素数)阶群上3度连通Cayley图的正规性,作为该结果的一个应用,对每一个1(?)s(?)5,对2p~2阶3度s-正则Cayley图作了分类。     

关于4p阶3度Cayley图的正规性的一点注记

群G的Cayley图Cay(G,S)称为是正规的,如果G的右正则表示R(G)在Cay(G,S)的全自同构群中正规.设p为奇素数,相关文献决定了4p阶连通3度Cayley图的正规性.本文给出了上述文献的主要结果的一个新的简短的证明.     

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

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

双圈图的零度与其匹配数之间的关系

Let G be a graph with n(G) vertices and m(G) be its matching number.The nullity of G,denoted by η(G),is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then η(G) = n(G)-2m(G).Guo et al.[Jiming GUO,Weigen YAN,Yeongnan YEH.On the nullity and the matching number of unicyclic graphs.Linear Alg.Appl.,2009,431:1293 1301]proved that if G is a unicyclic graph,then η(G)equals n(G)-2m(G)-1,n(G)-2m(G),or n(G)-2m(G) +2.In this paper,we prove that if G is a bicyclic graph,then η(G) equals n(G)-2m(G),n(G)-2m(G)±1,n(G)-2m(G)±2or n(G)-2m(G) + 4.We also give a characterization of these six types of bicyclic graphs corresponding to each nullity.     

由圈长分布确定的二部图~$K_{n,n r}-A\ (|A|\leq 3)$

The cycle length distribution of a graph G of order n is a sequence （c1 （G）,…, cn （G））, where ci （G） is the number of cycles of length i in G. In general, the graphs with cycle length distribution （c1（G） ,…,cn（G）） are not unique. A graph G is determined by its cycle length distribution if the graph with cycle length distribution （c1 （G）,…, cn （G）） is unique. Let Kn,n＋r be a complete bipartite graph and A lohtaib in E（Kn,n＋r）. In this paper, we obtain： Let s 〉 1 be an integer. （1） If r = 2s, n 〉 s（s - 1） ＋ 2｜A｜, then Kn,n＋r - A （A lohtain in E（Kn,n＋r）,｜A｜ ≤ 3） is determined by its cycle length distribution; （2） If r = 2s ＋ 1,n 〉 s^2 ＋ 2｜A｜, Kn,n＋r - A （A lohtain in E（Kn,n＋r）, ｜A｜ ≤3） is determined by its cycle length distribution.     

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

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.     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.     

C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

完全$r$部图乘积上的Graham猜想

图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).本文证明对于一个完全γ部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立.作为一个推论,当G和H均为完全γ部图时,Graham猜想成立.     

Cycles Containing a Subset of a Given Set of Elements in Cubic Graphs

The technique of contractions and the known results in the study of cycles in $3$-connected cubic graphs are applied to obtain the following result. Let $G$ be a $3$-connected cubic graph, $X\subseteq V(G)$ with $|X| = 16$ and $e\in E(G)$. Then either for every $8$-subset $A$ of $X$, $A\cup\{e\}$ is cyclable or for some $14$-subset $A$ of $X$, $A\cup\{e\}$ is cyclable.