极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

3连通图的可去边数

设 e是 3连通图 G的一条边 ,如果 G- e是某个 3连通图的剖分 ,则称 e是 G的可去边 .本文给出了 3连通图的可去边数依赖于极大半轮的下界以及达到下界的极图 .     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G₁,G₂,且|G₁|≥2,|G₂|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡（k-1）点割的（k-1）-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$的整数,若G是一个不含（K₂+tK₁）的k-连通图,且G中任意两个不同点对v,w,有d（v）+d（w）≥ $\frac{{3k}}{2} $+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $条边使得收缩其中任意一条边后仍是拟k-连通的。     

图是超限制性边连通的充分条件

设G=（V,E）是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ＇（G）是G的一个最小限制性边割的基数.G是λ＇-连通的,如果G存在限制性边割.G是λ＇-最优的,如果λ＇（G）=ζ（G）,其中ζ（G）是min{d（x）＋d（y）-2：xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ＇.G的逆度R（G）=∑_（v∈V） 1/d（v）,其中d（v）是点v的度数.我们证明了G是λ＇-连通的且不含三角形,如果R（G）≤2＋1/ζ-ζ/（（2δ-2）（2δ-3））＋（n-2δ-ζ＋2）/（（n-2δ＋1）（n-2δ＋2））,则G是超-λ＇.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

有向图的边割(X,Y)中｜X｜和｜Y｜的下界与有向图的极大性和超级性

在已有的极大边连通、超级边连通、极大局部边连通有向图概念的基础上,提出超级局部边连通有向图的概念,对一般的、二部的、基础图的团数至多为p的有向图、定向图分别给出｜(X,Y)｜＜δ(D)的边割(X,Y)、非平凡的最小边割(X,Y)中｜X｜和｜Y｜的下界,据此分别得到极大边连通、超级边连通有向图的最小度条件.类似地分别得到...     

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

依赖团数的有向图极大与超级边连通的度序列条件

互连网络通常以有向图为模型,有向图的弧连通度是网络可靠性的一个重要参数.给出了依赖团数的有向图极大和超级边连通的度序列条件.     

The maximum spectral radius of uniform hypergraphs with given number of pendant edges

In this paper, we introduce the operations of grafting an edge and subdividing an edge on hypergraphs, and consider how spectral radius of a hypergraph behaves by grafting an edge or subdividing an edge. As an application, we determine the unique hypergraphs with the maximum spectral radius among all the uniform supertrees and all the connected uniform unicyclic hypergraphs with given number of pendant edges, respectively. Moreover, we determine the unique uniform supertree which attains the maximum spectral radius among all the uniform supertrees with given number of pendant vertices.     

Augmenting the Edge‐Connectivity of a Hypergraph by Adding a Multipartite Graph

Given a hypergraph, a partition of its vertex set, and a nonnegative integer k, find a minimum number of graph edges to be added between different members of the partition in order to make the hypergraph k‐edge‐connected. This problem is a common generalization of the following two problems: edge‐connectivity augmentation of graphs with partition constraints (J. Bang‐Jensen, H. Gabow, T. Jordán, Z. Szigeti, SIAM J Discrete Math 12(2) (1999), 160–207) and edge‐connectivity augmentation of hypergraphs by adding graph edges (J. Bang‐Jensen, B. Jackson, Math Program 84(3) (1999), 467–481). We give a min–max theorem for this problem, which implies the corresponding results on the above‐mentioned problems, and our proof yields a polynomial algorithm to find the desired set of edges.     

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.     

H-Eigenvalues of signless Laplacian tensor for an even uniform hypergraph

The signless Laplacian tensor and its H-eigenvalues for an even uniform hypergraph are introduced in this paper. Some fundamental properties of them for an even uniform hypergraph are obtained. In particular, the smallest and the largest H-eigenvalues of the signless Laplacian tensor for an even uniform hypergraph are discussed, and their relationships to hypergraph bipartition, minimum degree, and maximum degree are described. As an application, the bounds of the edge cut and the edge connectivity of the hypergraph involving the smallest and the largest H-eigenvalues are presented.     

Generalized multiplicities of edge ideals

We explore connections between the generalized multiplicities of square-free monomial ideals and the combinatorial structure of the underlying hypergraphs using methods of commutative algebra and polyhedral geometry. For instance, we show that the j-multiplicity is multiplicative over the connected components of a hypergraph, and we explicitly relate the j-multiplicity of the edge ideal of a properly connected uniform hypergraph to the Hilbert–Samuel multiplicity of its special fiber ring. In addition, we provide general bounds for the generalized multiplicities of the edge ideals and compute these invariants for classes of uniform hypergraphs.     

Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size

Let D be a finite and simple digraph with vertex set V (D). The minimum degree δ of a digraph D is defined as the minimum value of its out-degrees and its in-degrees. If D is a digraph with minimum degree δ and edge-connectivity λ, then λ ≤ δ. A digraph is maximally edge-connected if λ=δ. A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree. In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.     

Optimally super-edge-connected transitive graphs

Let X=(V,E) be a connected regular graph. X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ′(X) of X is the minimum number of edges whose removal disconnects X into non-trivial components. A super-edge-connected k-regular graph is said to be optimally super-edge-connected if its restricted edge connectivity attains the maximum 2k−2. In this paper, we define the λ′-atoms of graphs with respect to restricted edge connectivity and show that if X is a k-regular k-edge-connected graph whose λ′-atoms have size at least 3, then any two distinct λ′-atoms are disjoint. Using this property, we characterize the super-edge-connected or optimally super-edge-connected transitive graphs and Cayley graphs. In particular, we classify the optimally super-edge-connected quasiminimal Cayley graphs and Cayley graphs of diameter 2. As a consequence, we show that almost all Cayley graphs are optimally super-edge-connected.     

Coloring uniform hypergraphs with few edges

A hypergraph is b‐simple if no two distinct edges share more than b vertices. Let m(r, t, g) denote the minimum number of edges in an r‐uniform non‐t‐colorable hypergraph of girth at least g. Erd?s and Lovász proved that A result of Szabó improves the lower bound by a factor of r^2?? for sufficiently large r. We improve the lower bound by another factor of r and extend the result to b‐simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed b, t, and ? > 0 and sufficiently large r, every r‐uniform b‐simple hypergraph with maximum edge‐degree at most t^rr^1?? is t‐colorable. Some results hold for list coloring, as well. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Hamilton cycles in quasirandom hypergraphs

We show that, for a natural notion of quasirandomness in k‐uniform hypergraphs, any quasirandom k‐uniform hypergraph on n vertices with constant edge density and minimum vertex degree Ω(n^k‐1) contains a loose Hamilton cycle. We also give a construction to show that a k‐uniform hypergraph satisfying these conditions need not contain a Hamilton ?‐cycle if k– ? divides k. The remaining values of ? form an interesting open question. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 363–378, 2016