包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

A sufficient condition for equality of edge-connectivity and minimum degree of a graph

Let G be a connected graph of order p ≥ 2, with edge-connectivity κ₁(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ₁(G) = δ(G), it is sufficient that, for each vertex x of minimum degree in G, the vertices in the neighbourhood N(x) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G) ≥ [p/2].     

A degree condition for a graph to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1 ≤ a < b. We show that G has an [a, b]-factor if δ(G) ≥ a, n ≥ 2a + b + and max {d_G(u), d_G(v) ≥ for any two nonadjacent vertices u and v in G. This result is best possible, and it is an extension of T. Iida and T. Nishimura's results (T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs, Graphs and Combinat. 7 (1991), 353–361; T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992), 141–151). about the existence of a k-factor. As an immediate consequence, it shows that a conjecture of M. Kano (M. Kano, Some current results and problems on factors of graphs, Proc. 3rd China–USA International Conference on Graph Theory and Its Application, Beijing (1993). about connected [a, b]-factors is incorrect. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 1–6, 1998     

A minimum degree condition forcing complete graph immersion

An immersion of a graph H into a graph G is a one-to-one mapping f: V (H) → V (G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P _uv corresponding to edge uv has endpoints f(u) and f(v). The immersion is strong if the paths P _uv are internally disjoint from f(V (H)). It is proved that for every positive integer Ht, every simple graph of minimum degree at least 200t contains a strong immersion of the complete graph K _t . For dense graphs one can say even more. If the graph has order n and has 2cn ² edges, then there is a strong immersion of the complete graph on at least c ² n vertices in G in which each path P _uv is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree d has a clique minor of order at least cd ^3/2, where c>0 is an absolute constant. For small values of t, 1≤t≤7, every simple graph of minimum degree at least t?1 contains an immersion of K _t (Lescure and Meyniel [13], DeVos et al. [6]). We provide a general class of examples showing that this does not hold when t is large.     

The differential equation satisfied by a plane curve of degree n

Eliminating the arbitrary coefficients in the equation of a generic plane curve of order n by computing sufficiently many derivatives, one obtains a differential equation. This is a projective invariant. The first one, corresponding to conics, has been obtained by Monge. Sylvester, Halphen, Cartan used invariants of higher order. The expression of these invariants is rather complicated, but becomes much simpler when interpreted in terms of symmetric functions.     

On extension results for n-cyclically monotone operators in reflexive Banach spaces

In this paper we provide some extension results for n-cyclically monotone operators in reflexive Banach spaces by making use of the Fenchel duality. In this way we give a positive answer to a question posed by Bauschke and Wang (2007) [4].     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

最大度为6的平面图为第一类的一个新充分条件

本文证明了:若一个平面图G不含带弦的6-圈,则G是第一类的.这部分地证实了Vizing的关于平面图边染色的一个猜想.     

The maximum degree of a minimally hamiltonian-connected graph

We determine the possible maximum degrees of a minimally hamiltonian-connected graph with a given order. This answers a question posed by Modalleliyan and Omoomi in 2016. We also pose two unsolved problems.     

Every monotone graph property has a sharp threshold

In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This follows from the following theorem. Let denote the Hamming space endowed with the probability measure defined by , where . Let be a monotone subset of . We say that is symmetric if there is a transitive permutation group on such that is invariant under . Theorem. For every symmetric monotone , if then for . ( is an absolute constant.)

     

The scaling window for a random graph with a given degree sequence

We consider a random graph on a given degree sequence D, satisfying certain conditions. Molloy and Reed defined a parameter Q = Q(D) and proved that Q = 0 is the threshold for the random graph to have a giant component. We introduce a new parameter R = R( \begin{align*}\mathcal {D}\end{align*}) and prove that if |Q| = O(n^‐1/3R^2/3) then, with high probability, the size of the largest component of the random graph will be of order Θ(n^2/3R^‐1/3). If |Q| is asymptotically larger than n^‐1/3R^2/3 then the size of the largest component is asymptotically smaller or larger than n^2/3R^‐1/3. Thus, we establish that the scaling window is |Q| = O(n^‐1/3R^2/3). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

The irredundance number and maximum degree of a graph

A vertex η in a subset X of vertices of an undirected graph is redundant if its closed neighborhood is contained in the union of closed neighborhoods of vertices of X-{η}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X-{η}. The irredundance number ir(G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) ? n/(2Δ-1) for a graph G having n vertices and maximum degree Δ.     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .