点染色3-边划分图的最小度(英文)

Addrio-Berry L[1]已经证明了最小度至少为1000的图可以点染色3-边划分,在本文中,我们将其结果改进到了最小度至少为662.     

Ribbon Graph Minors and Low-Genus Partial Duals

We give an excluded minor characterisation of the class of ribbon graphs that admit partial duals of Euler genus at most one.     

Graph Minors. XX. Wagner''s conjecture

In a previous paper (J. Combin. Theory 48 (1990) 255) we showed that for any infinite set of (finite) graphs drawn in a fixed surface, one of the graphs is isomorphic to a minor of another. In this paper we extend that result in two ways:

• we generalize from graphs to hypergraphs drawn in a fixed surface, in which each edge has two or three ends, and

• the edges of our hypergraphs are labelled from a well-quasi-order, and the minor relation is required to respect this order.

This result is another step in the proof of Wagner's conjecture, that for any infinite set of graphs, one is isomorphic to a minor of another.     

Minimum Degree and Dominating Paths

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n‐vertex k‐connected graph and , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a). The preceding results are sharp. For constant s and , an s‐vertex dominating path is guaranteed by when n is sufficiently large, but (where ) does not even guarantee a dominating set of size s. We also obtain minimum‐degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.     

A Property About Minimum Edge- and Minimum Clique-Cover of a Graph

 Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ ⁿ :Ex≤1,x≥0}, P(C)={x∈ℜ ⁿ :Cx≤1,x≥0}, α _E (G)=max{1 ^T x subject to x∈P(E)}, and α _C (G)= max{1 ^T x subject to x∈P(C)}. In this paper we prove that if α _E (G)=α _C (G), then γ(G)=θ(G). Received: May 20, 1998?Final version received: April 12, 1999     

极值图论与度序列

本文简要概述极值图论与度序列的最新研究进展，同时提出了一些有待进一步解决的问题和猜想．     

无爪图的次与Hamilton连通性

本文证明了：设G是n阶、k（≥3）连通无爪图，且不含同构于B的导出子图，若存在点v_0∈V（G），使d（v_0）≥n-2k＋4，则G是Hamilton连通的．     

Average Degree in Graph Powers

The kth power of a simple graph G, denoted by , is the graph with vertex set where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of . Here we prove that if G is connected with minimum degree and , then G⁴ has average degree at least . We also prove that if G is a connected d‐regular graph on n vertices with diameter at least , then the average degree of is at least Both these results are shown to be essentially best possible; the second is best possible even when is arbitrarily large.     

Graph Decompositions Satisfying Extremal Degree Constraints

We show that the vertex set of any graph G with p?2 vertices can be partitioned into non-empty sets V₁, V₂, such that the maximum degree of the induced subgraph 〈V_i〉 does not exceed where pⁱ = |Vⁱ|, for i=1, 2. Furthermore, the structure of the induced subgraphs is investigated in the extreme case.     

准模糊图拟阵的次限制最小基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的次限制最小基的一些性质,这将有利于进一步研究模糊拟阵的其它性质.     

Uniquely Hamiltonian Graphs of Minimum Degree 4

We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree.     

Bounded Degree, Triangle Avoidance Graph Games

We consider variants of the triangle-avoidance game first defined by Harary and rediscovered by Hajnal a few years later. A graph game begins with two players and an empty graph on n vertices. The two players take turns choosing edges within K _n , building up a simple graph. The edges must be chosen according to a set of restrictions ${\mathcal{R}}$ . The winner is the last player to choose an edge that does not violate any of the restrictions in ${\mathcal{R}}$ . For fixed n and ${\mathcal{R}}$ , one of the players has a winning strategy. For various games where ${\mathcal{R}}$ includes bounded degree and triangle avoidance, we determine the winner for all values of n.     

Domination in Graphs of Minimum Degree Five

Let G=(V,E) be a simple graph. A subset D⊆V is a dominating set of G, if for any vertex x ∈ V−D, there exists a vertex y ∈ D such that xy ∈ E. By using the so-called vertex disjoint paths cover introduced by Reed, in this paper we prove that every graph G on n vertices with minimum degree at least five has a dominating set of order at most 5n/14.     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).     

一类无标度随机图的度序列

本文从-个新的角度对-类随机图的度序列进行了分析.证明了此模型度分布的存在性,得到了网络规模比较大的情况下度为七的节点所占比例数的表达式.此外,我们还将模型扩展到每个时间步增加边数为随机变量的情形,得到了类似的结论.     

Hamilton Cycles,Minimum Degree,and Bipartite Holes

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large “bipartite hole” (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erd?s. In detail, an ‐bipartite‐hole in a graph G consists of two disjoint sets of vertices S and T with and such that there are no edges between S and T ; and is the maximum integer r such that G contains an ‐bipartite‐hole for every pair of nonnegative integers s and t with . Our central theorem is that a graph G with at least three vertices is Hamiltonian if its minimum degree is at least . From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of k edge‐disjoint Hamilton cycles. We see that for dense random graphs , the probability of failing to contain many edge‐disjoint Hamilton cycles is . Finally, we discuss the complexity of calculating and approximating .     

准模糊图拟阵的相邻的次限制最小基

模糊拟阵的基图是模糊拟阵的基本概念.在准模糊图拟阵的基础上,给出了准模糊图拟阵基图的相邻的次限制最小基的一些性质.将为深入研究模糊拟阵的内在本质,进一步研究模糊拟阵的算法奠定了基础.     

模特征标度图

本文假设G为一有限群且G的模特征标度图有两个连通分支。记πi(i=1,2)为其顶点集。文章通过p-长界定了G的πi-长，并证明了G的π1－或π2－长至多为4。     

最小次数至少为4的超欧拉图

设Ｇ是２－边－连通的ｎ阶图。假设对任何的的最小边割集Ｅ等于包含于Ｅ（Ｇ）且│Ｅ│≤３,Ｇ－Ｅ的每个分支的阶至少为ｎ／５,则或者Ｇ是一个超欧拉图或者Ｇ有５个互不相交的阶数为ｎ／５连通分支,当这５个分支都收缩时,Ｇ收缩为Ｋ２,３,这个结果推广了蔡小涛,Ｐ．Ａ．Ｃａｔｌｉｎ,Ｆ．Ｊａｅｇｅｒ和Ｈ．Ｊ．Ｌａｉ等人关于超欧拉图的结果。