3-一致超图的反馈数研究（英文）

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τ_c(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τ_c(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τ_c(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τ_c′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τ_c'(H)≤2m-n+p.     

一致超图中Berge线性森林的Turán数

设F是一个图,■是一个超图,如果存在一个双射φ:E(F)→E(■),使得?e∈E(F)有e?φ(e),那么称超图■是Berge-F.不含Berge-F作为子超图的n阶r-一致超图所能达到的最大边数称为Berge-F的Turán数,记作ex_r(n,Berge-F).线性森林是指连通分支全是路或者孤立顶点的图.设■_n,k是一类含有n个顶点k条边的线性森林图族.本文研究了r-一致超图中Berge-■_n,k的Turán数.当r≥k+1和3≤r≤■(k-1)/2■-1时,分别确定了ex_r(n,Berge-■_n,k)的精确值;当■(k-1)/2■≤r≤k时,给出了ex_r(n,Berge-■_n,k)的上界.     

交叉立方体网络的反馈数

对于简单图G=(V,E),顶点子集F■V,如果由V\F导出的子图G′= (V\F,E′)是不含圈的,则称F是图G的一个反馈点集.点数最少的反馈点集称图的最小反馈点集,最小的点数称为反馈数.文章给出了交叉立方体网络的一个等价定义,用递归的方法构造出交叉立方体网络的诱导树,证明了诱导树的阶数Fibonacci数,进而得到叉立方体网络反馈数的上下界.     

折叠立方体网络的最小反馈点集

对简单图G=(V,E),顶点子集F V,如果由V\F导出的子图不含圈,则称F是G的反馈点集。点数最小的反馈点集称图的最小反馈点集,最小的点数称为反馈数。一个k维折叠立方体是由一个k维超立方体加上所有的互补边构成的图。本文证明了k维折叠立方体网络的反馈数f(k)=c.2k-1(k 2),其中c∈k-1     

无圈超图的1—因子定理

本文证明了一个无圈超图 H=(X,E)有1-因子当且仅当(?)S(?)X,sum from i=1 to r-1(r-i)q_i≤|S|,其中 q_i 表示 H 的子超图 H-S 的顶点数模 r 等于 i 的连通分支数,r 是超图 H 的秩.     

Kautz网络中的最小反馈点集

对简单有向图D=(V，E)，顶点子集F∈V，如果由V＼F导出的子图不含有向圈，则称F是D的反馈点集。点数最小的子集F称为最小反馈点集。最小的点数称为反馈数。本利用Kautz最小轨道的方法确定出了Kautz有向图K(d，k)反馈数的一个下界和上界。并且具体给出了当k≤3时的反馈数。     

图与超图中的彩色匹配综述

超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.     

3一致 C-超图的最小边数

混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k 1时,该下界是可以达到的．     

周长为3的m限制边割连通图

如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.     

5-一致超图的全横贯

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.     

A note on a conjecture of Ryser

A special case of a conjecture of Ryser states that if a 3-partite 3-uniform hypergraph has at mostv pairwise disjoint edges then there is a set of vertices of cardinality at most 2v meeting all edges of the hypergraph. The best known upper bound for the size of such a set is (8/3)v, given by Tuza [7]. In this note we improve this to (5/2)v.     

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.     

若干图的点强全着色

图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的点集的最大顶点数.     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

Total restrained bondage in graphs

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.     

Dense 3-uniform hypergraphs containing a large clique

An r-uniform graph C is dense if and only if every proper subgraph G' of G satisfies λ(G') λ(G).,where λ(G) is the Lagrangian of a hypergraph G. In 1980's, Sidorenko showed that π(F), the Turán density of an γ-uniform hypergraph F is r! multiplying the supremum of the Lagrangians of all dense F-hom-free γ-uniform hypergraphs. This connection has been applied in the estimating Turán density of hypergraphs. When γ=2 the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph. However,when r ≥ 3, it becomes much harder to estimate the Lagrangians of γ-uniform hypergraphs and to characterize the structure of all dense γ-uniform graphs. The main goal of this note is to give some sufficient conditions for3-uniform graphs with given substructures to be dense. For example, if G is a 3-graph with vertex set [t] and m edges containing [t-1]~(3),then G is dense if and only if m≥{t-2 3)+(t-2 2)+1. We also give a sufficient condition on the number of edges for a 3-uniform hypergraph containing a large clique minus 1 or 2 edges to be dense.     

广义de Bruijn和Kautz有向图的双向控制集

设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

Antimagic Labelings of Join Graphs

An antimagic labeling of a graph with q edges is a bijection from the set of edges of the graph to the set of positive integers \({\{1, 2,\dots,q\}}\) such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. The join graph G + H of the graphs G and H is the graph with \({V(G + H) = V(G) \cup V(H)}\) and \({E(G + H) = E(G) \cup E(H) \cup \{uv : u \in V(G) {\rm and} v \in V(H)\}}\). The complete bipartite graph K _m,n is an example of join graphs and we give an antimagic labeling for \({K_{m,n}, n \geq 2m + 1}\). In this paper we also provide constructions of antimagic labelings of some complete multipartite graphs.     

On unavoidable hypergraphs

A r-uniform hypergraph H (or a r-graph, for short) is a collection E = E(H) of r-element subsets (called edges) of a set V = V(H) (called vertices). We say a r-graph H is (n, e)-unavoidable if every r-graph with n vertices and e edges must contain H. In this paper we investigate the largest possible number of edges in an (n, e)-unavoidable 3-graph for fixed n and e. We also study the structure of such unavoidable 3-graphs.