On Graph-Lagrangians and clique numbers of 3-uniform hypergraphs

The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs.Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques.This connection provided a new proof of Turán classical result on the Turán density of complete graphs.Since then,Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs.Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range.They showed that if G is a 3-uniform graph with m edges containing a clique of order t-1,then λ(G)=λ([t-1]~((3))) provided (t-13)≤m≤(t-13)+_(t-22).They also conjectured:If G is an r-uniform graph with m edges not containing a clique of order t-1,then λ(G)λ([t-1]~((r))) provided (t-1r)≤ m ≤(t-1r)+(t-2r-1).It has been shown that to verify this conjecture for 3-uniform graphs,it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m=t-13+t-22.Regarding this conjecture,we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t-1]~((3))\E(G)|=p,then λ(G)λ([t-1]~((3))) provided m=(t-13)+(t-22) and t≥17p/2+11.     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

图的{P4}——分解

一个图G的路分解是指一路集合使得G的每条边恰好出现在其中一条路上．记Pl长度为l-1的路，如果G能够分解成若干个Pl，则称G存在{Pl}——分解，关于图的给定长路分解问题主要结果有：（i）连通图G存在{P3}-分解当且仅当G有偶数条边（见[1]）；（ii）连通图G存在{P3，P4}-分解当且仅当G不是C3和奇树，这里C3的长度为3的圈而奇树是所有顶点皆度数为奇数的树（见[3]）．本文讨论了3正则图的{P4}--分解情况，并构造证明了边数为3k（k∈Z且k≥2）的完全图Kn和完全二部图Kr,s存在{P4}-分解.     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

Total [1,2]-domination in Graphs

A subset S ? V in a graph G = (V,E) is a total [1, 2]-set if, for every vertex \( \upsilon \in V, 1 \leq\mid N (\upsilon)\cap S\mid\leq \). The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted by γ_t[1,2](^G).We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover, we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total [1, 2]-domination number, [1, 2]-domination number and domination number.     

不含三角形图的$A_\alpha$-谱半径的界

设$G$是简单无向图. 对于实数$\alpha \in [0,1]$, Nikiforov于2017年定义图的$A_\alpha$-矩阵为$A_\alpha(G)=\alpha D(G)+(1-\alpha)A(G)$, 其中$A(G)$和$D(G)$分别为图$G$的邻接矩阵和度对角矩阵. 图的$A_\alpha$-矩阵可以看着是图的邻接矩阵和无符号拉普拉斯矩阵的共同推广, 其最大特征值称为图的$A_\alpha$- 谱半径. 对于$\alpha\in[0,1)$, 本文确定了不含三角形图的$A_\alpha$-谱半径的一个下界;对于$\alpha \in[1/2, 1)$, 本文确定了不含三角形$k$圈图的$A_\alpha$-谱半径的一个上界.     

星和轮的Mycielski图的[r,s,t]色数

给定非负整数r,s和t,若图G(V,E)有一个映射σ:V∪E→{0,1,…,k-1},k∈N,满足对V中相邻的点v_i,v_j有|σ(v_i)-σ(v_j)|≥r;对E中相邻的边e_i,e_j有|σ(e_i)-σ(e_j)|≥s;对V∪E中相关联的点v_i和边e_j有|σ(v_i)-σ(e_j)|≥t,则称σ为G的一个[r,s,t]-着色.使得图G存在使用了k种颜色的[r,s,t]-着色的最小整数k称为G的[r,s,t]-色数.研究星和轮的Mycielski图的[r,s,t]-着色,并给出其在一定条件下的[r,s,t]-色数.     

最大度不大于5的Halin-图的点强全染色

图G(V,E)的一正常k-全染色f称为G(V,E)的一k-点强全染色当且仅当任意( A)v∈V(G),N[v]中的元素染不同色,其中N[v]={u|uv∈V(G)}U{v},并且XusT(G)=min{k|存在G的k-点强全染色}称为G(V,E)的点强全色数.本文得到了△(G)≤5的Halin-图G(V.E)的XusT(G),并提出如下猜想设G(V,E)为每一连通分支的阶数不小于6的图,则XusT(G)≤△(G)+2,其中△(G)表示图G的最大度.     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.     

具有两个同阶轨道的双轨道图的圈边连通度

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ（G）.定义：ζ（G）=min{w（X）｜X导出G的最短圈},其中w（X）为端点分别在X和V（G）-X中的边的数目.如果一个圈边可分离图G使得cλ（G）=ζ（G）成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.     

外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．     

图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.     

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

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.     

[a,b]-对等图的范-型条件

既是[a,b]-覆盖又是[a,b]-消去的图称为[a,b]-对等图.设1≤aan+1a+b,则G为[a,b]-对等图.给出了一个图是[a,b]-对等图的关于范-型条件及邻域并的若干充分条件,并指出定理中的条件在一定意义上是最好可能的.     

立方图的对控制数

设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq V$, G[S]表示图G中由S所导出的子图. 如果S是G的一个控制集并且G[S]包含至少一个完备匹配, 则称S是G的一个对控制集. G中对控制集的最少的顶点数称为$G$的对控制数, 记为γ_p(G). 该文证明了对任意有n点的连通立方图G, γ_p(G)≤3n/ 5.     

若干图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u|vu∈E(G)}∪{v}.并且vχsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数.本文得到了一些特殊图的点强全色数χvTs(G),并提出猜想:对于简单图G,有k(G)≤χvTs(G)≤k(G)+1,这里k(G)表示图G中所有顶点间距离不超过2的点集的最大顶点数.     

不含4-圈与7-圈的平面图是(2,0,0)-可染的

设d1,d2,...,dk是k个非负整数.若图G=(V,E)的顶点集V可剖分成k个子集V1,V2,...,Vk使得对i=1,2,...,k,由Vi所导出的子图G[Vi]的最大度至多为di,则称G是(d1,d2,...,dk)-可染的.本文证明不含4-圈和7-圈的平面图是(2,0,0)-可染的.     

图在三种约束条件下的正常全染色

设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈N_e(u)},C[f,u]=C(f,u)∪{f(u)},C_2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,N_e(u)表示与顶点u的相关联的边的集合.令C[f;x]={C(f,x);C[f,x];C_2[f,x]},对任意的xy∈E(G),G[f;x]≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C_2[f,x]≠C_3[f,y]同时成立.对任意的边xy∈E(G),如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为(3)-AVDTC).图G的(3)-邻点可区别全染色中最小的颜色数叫做G的(3)-邻点可区别全色数,记为x_((3)as)″(G).研究了联图,完全二部图的(3)-邻点可区别全染色,得到了它们的(3)-邻点可区别全色数.