二部平衡公平划分的一个下界

设V_1,V_2是图G的一个二部划分.如果一1≤|V_1|-|V_2|≤1,则称V_1,V_2是G的一个二部平衡划分.对于n个顶点m条边的简单图G,本文证明了:(1)若G是k-正则图(k≥3),则G存在一个最小二部平衡划分V_1,V_2,使得max{e(V_1),e(V_2)}≥((k-1)m)/4k;(2)如果r是大于4的实数,且当n是偶数时△(G)≤((3r-4))/(r+4)δ(G)-(2r)/(r+4),当n是奇数时△(G)≤(3r-4)/(r+4)δ(G)-(8r)/(r+4),那么G存在一个二部平衡划分,使得min{e(V_1),e(V_2)}≥m/r,这里e(V_i)表示G中两个顶点都在V_i中的边的数目.     

二部图平衡二部划分的上界

设G(V,E)是一个图,V_1,V_2是V的一个二部划分,当||V_1|-|V_2||≤1时,称V_1,V_2是V的一个平衡二部划分,用e(V_1,V_2)表示一条边的两个端点在不同划分里边的总数目.最小平衡二部划分是指寻找G(V,E)的一个平衡二部划分使得e(V_1,V_2)最小.研究了二部图和哈密尔顿二部图,得到它们的最小平衡二部划分的上界分别为[m/2]和(n+2)/2.     

哈密尔顿平面图最小平衡二部划分的上界

设G(V,F)是一个图,V_1,V_2是V的一个二部划分,用e(V_1,V_2)表示一条边的两个端点在不同划分里边的总数目,当‖V_1|-|V_2‖≤1时,称V1,V2是V的一个平衡二部划分。最小平衡二部划分是指寻找G(V,F)的一个平衡二部划分使得e(V1,V2)最小。对于哈密尔顿平面图G(V,F),研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为d时,e(V_1,V_2)最小值的上界与d之间的关系。     

平面图最小平衡二部划分的上界

关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.     

超图与图公平划分的l-元组

令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数. Fan和Hou(2017)证明了每个最大度为?的m阶图G都存在一个k部划分(V_1, V_2,..., V_k),使得对于任意1≤i j≤k,都成立e(V_i∪V_j)min≤{4/k~2×m+4?/k,m/k-1}+o(m~(7/8)).令H表示最大度为?的m阶r-一致超图,本文证明H存在一个k部划分(V_1, V_2,..., V_k),对于任意1≤i j≤k,满足e(V_i∪V_j)≤r-1/k-1×m+o(m);也证明当?=o(m)时, H存在一个k部划分(V_1, V_2,..., V_k),使得对于任意l∈[k-1]和每个l元组(V_(j1),..., V_(jl)),有e(V_(j1)∪···∪V_(jl))≤l~r/k~r/m+o(m).     

关于正则图存在平衡划分的一些结果

一个图G的划分V(G)=V1∪V2,如果满足下列条件:(1)||V1|-|V2||≤1;(2)任给u ∈V(G),当u ∈V1时,满足dG[V1](u)-dG[V2∪{u}](u)≤1;当u ∈V2时,满足dG[V2](u)-dG[V1∪{u}](u)≤1.则称V(G)=V1 ∪ V2为G的一个平衡划分.Bollobas与Scott猜想任一图都存在平衡划分.文中证明了k-正则图存在平衡划分.其中k ∈{3,n-1,n-2,n-3,n-4).对于k=3或n-4的一个特殊情形,还给出了寻找k-正则图平衡划分的算法.     

图的k部划分的一个注记

设k≥2是一个整数。本文证明了任意有m条边的图都存在一个顶点的划分V_1,V_2…,V_k,使得e(V_1,V_2…,V_k)≥k-1/k m+k-1/2k((2m+1/4)~1/2-1/2)-(k-2)~2/8k,且max{e(V_i):1≤i≤k}≤m/k~2+(k-1)/2k~2((2m+1/4)~1/2-1/2+3/8-7k-4/8k~2.我们的结果改进了[Fan G.,Hou J.,Zeng Q.,A bound for judicious k-partitions of graphs,Discrete Appl.Math.,2014,179:86—99]的主要结论.     

关于2-边连通3正则图荫度的一个注（英文）

图G的点荫度a(G)是G的使得每个子集诱导一个森林的顶点划分中子集的最少个数.我们熟知对任何平面图G,a(G)≤3,且对任何直径最大是2的平面图有a(G)≤2.文献[European J.Combin.,2008,29(4):1064-1075]中给出下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.本文证明了任何2-边连通上可嵌入的3-正则图G(G≠K_4)都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.     

均衡二部图中点不交的4-圈和6-圈（英文）

设G=(V_1,V_2,E)是一个均衡二部图满足|V_1|=|V_2|=n.令δ_(1,1)(G)=min{d(x)+d(y)|x∈V_1,Y∈V_2}.Amar猜想对任意的s个整数(n_1,n_2,…,n_s),n=n_1+n_2+…+n_s,其中n_i≥2.若δ_(1,1)(G)≥n+s,则G含s个点不交的圈,其长分别为2n_1,2n_2,…,2n_s(见[Discrete Math.,1986,58(1):1-10]).本文证明了若一个点数为4k的均衡二部图G满足δ_(1,1)(G)≥2k+4(k≥3),则G含k-3个4-圈和2个6-圈使得所有这些圈都是点不交的.     

星样树与路的笛卡尔积图的任意可分性（英文）

一个图G称为是任意可分的(简记AP),如果对于正整数|V(G)|的任一满足∑_(i=1)~pn_i=|V(G)|的划分τ=(n_1,n_2,…,n_p),总是存在顶点集V的一个划分(V_1,V_2,…,V_p)满足|V_i|=n_i,i=1,2,…,p,使得每个V_i导出的图是图G的一个连通子图.记S(a_1,a_2,…,a_t,b_1,b_2,…,b_l)是最大度△(S)=t+l的星样树,其中a_i是奇数,b_j是偶数且a_1≤a_2≤…≤a_t,b_1≤b_2≤…≤b_l.我们证明了对于一个大于等于2的偶数n,当△(S)≤n+1时,如果t≤2,或t≥3且a_3 1,则笛卡尔积图S□P_n是AP的.对于一个大于2的奇数n,如果△(S)≤n+1且t≤2,则S□P_n是AP的;如果△(S)≤n+1且t≥3,则S□P_n不是AP的.     

哈密尔顿平面图最小平衡二部划分的上界

设$G（V，E）$是一个图，$V_{1}，V_{2}$是$V$的一个二部划分，用$e（V_{1}，V_{2}）$表示一条边的两个端点在不同划分里边的总数目，当$||V_{1}|-|V_{2}||\leq 1$时，称$V_{1}，V_{2}$是$V$的一个平衡二部划分。最小平衡二部划分是指寻找$G（V，E）$的一个平衡二部划分使得$e（V_{1}，V_{2}）$最小。对于哈密尔顿平面图$G（V，E）$，研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为$d$时，$e（V_{1}，V_{2}）$最小值的上界与$d$之间的关系。     

二树的ABC指标

The atom-bond connectivity(ABC) index of a graph G, introduced by Estrada,Torres, Rodr′?guez and Gutman in 1998, is defined as the sum of the weights(1/di+1/dj-2/didj )~(1/2) of all edges vivj of G, where di denotes the degree of the vertex vi in G. In this paper, we give an upper bound of the ABC index of a two-tree G with n vertices, that is, ABC(G) ≤(2n- 4)2~(1/2)/2+(2n-4)~(1/2)/n-1. We also determine the two-trees with the maximum and the second maximum ABC index.     

关于三圈图的拉普拉斯谱半径的一些结果

边数等于点数加二的连通图称为三圈图.~设 ~$\Delta(G)$~和~$\mu(G)$~
分别表示图~$G$~的最大度和其拉普拉斯谱半径,设${\mathcal
T}(n)$~表示所有~$n$~阶三圈图的集合,证明了对于~${\mathcal
T}(n)$~的两个图~$H_{1}$~和~$H_{2}$~,~若~$\Delta(H_{1})>
\Delta(H_{2})$ ~且 ~$\Delta(H_{1})\geq \frac{n+7}{2}$,~则~$\mu
(H_{1})> \mu (H_{2}).$ 作为该结论的应用,~确定了~${\mathcal
T}(n)(n\geq9)$~中图的第七大至第十九大的拉普拉斯谱半径及其相应的极图.     

一个关于平面图的K-(2,1)-全可选性的结果

设图$G$的一个列表分配为映射$L: V(G)\bigcup E(G)\rightarrow2^{N}$. 如果存在函数$c$使得对任意$x\in V(G)\cup E(G)$有$c(x)\in L(x)$满足当$uv\in E(G)$时, $|c(u)-c(v)|\geq1$, 当边$e_{1}$和$e_{2}$相邻时, $|c(e_{1})-c(e_{2})|\geq1$, 当点$v$和边$e$相关联时, $|c(v)-c(e)|\geq 2$, 则称图$G$为$L$-$(p,1)$-全可标号的. 如果对于任意一个满足$|L(x)|=k,x\in V(G)\cup E(G)$的列表分配$L$来说, $G$都是$L$-$(2,1)$-全可标号的, 则称$G$是 $k$-(2,1)-全可选的. 我们称使得$G$为$k$-$(2,1)$-全可选的最小的$k$为$G$的$(2,1)$-全选择数, 记作$C_{2,1}^{T}(G)$. 本文, 我们证明了若$G$是一个$\Delta(G)\geq 11$的平面图, 则$C_{2,1}^{T}(G)\leq\Delta+4$.     

图的上可嵌入性与独立顶点的新度和

Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable.     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

有循环极大子群的素数幂阶群的作用是边传递的图(II)

假定Γ是一个有限的、单的、无向的且无孤立点的图,G是Aut(Γ)的一个子群.如果G在Γ的边集合上传递,则称Γ是G-边传递图.我们完全分类了当G为一个有循环的极大子群的素数幂阶群时的G-边传递图.结果为:设图Γ含有一个阶为pn(p是素数,n≥2)的自同构群,且G有一个极大子群循环,则Γ是G-边传递的,当且仅当Γ同构于下列图之一1)pmK1,pn-1-m,0≤m≤n-1;2)pmK1,pn-m,0≤m≤n;3)pmKp,pn-m-1,0≤m≤n-2;4)pn-mCpm,pm≥3,m＜n;5)2n-2K1,1;6)pn-1-mCpm,pm≥3,m≤n-1;7)2pn-mCpm,pm≥3,m≤n-1;8)2pn-mK1,pm,0≤m≤n;9)pn-mK1,2pm,0≤m≤n;10)pn-mK2,pm,0＜m≤n;11)C(2pn-m,1,pm);12)pkC(2pm-k,1,pn-m),0＜k＜m,0＜m≤n;13)(t-s,2m)C(2m 1/(t-s,2m),1,2n-1-m),其中0≤m≤n-1,2n-2(s-1)≡0(mod 2m),t≡1(mod 2),s(≠)t(mod 2m),1≤s≤2m,1≤t≤2n-1;14)∪p i=1 Ci p n-1,其中Ci p n-1=Ca1a1 [1 (i-1)pn-2]a 1 2[1 (i--1)p n-2]…a 1 (pn-1-1)[1 (i-1)p n-2]≌Cp n-1,i=1,2,…,p;15)∪2 i=1 Ci 2n-1,其中Ci 2n-1=Ca1a 1 [1 (i-1)(2n-2-1)]a1 2[1 (i-1)(2n-2-1)]…a1 (2n-1-1)[1 (i-1)(2n-2-1)]≌C2n-1,i=1,2.     

划分围长至少为6 的平面图为有界大小的分支

图$G$的$(\mathcal{O}_{k_1}, \mathcal{O}_{k_2})$-划分是将$V(G)$划分成两个非空子集$V_{1}$和$V_{2}$, 使得$G[V_{1}]$和$G[V_{2}]$分别是分支的阶数至多$k_1$和$k_2$的图.在本文中,我们考虑了有围长限制的平面图的点集划分问题,使得每个部分导出一个具有有界大小分支的图.我们证明了每一个围长至少为6并且$i$-圈不与$j$-圈相交的平面图允许$(\mathcal{O}_{2}$, $\mathcal{O}_{3})$-划分,其中$i\in\{6,7,8\}$和$j\in\{6,7,8,9\}$.     

变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．