The confirmation of a conjecture on disjoint cycles in a graph

Let $t$ and $k$ be two integers with $t\ge 5$ and $k\ge 2$. For a graph $G$ and a vertex $x$ of $G$, we use $d_G\left(x\right)$ to denote the degree of $x$ in $G$. Define ${\sigma }_t\left(G\right)$ to be the minimum value of ${\sum }_{x\in X}{d}_G\left(x\right)$, where $X$ is an independent set of $G$ with $\left|X\right|=t$. This paper proves the following conjecture proposed by Gould et al. (2018). If $G$ is a graph of sufficiently large order with ${\sigma }_t\left(G\right)\ge 2kt?t+1$, then $G$ contains $k$ vertex-disjoint cycles.     

Disjoint hamiltonian cycles in bipartite graphs

Let G=(X,Y) be a bipartite graph and define . Moon and Moser [J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163-165. MR 28 # 4540] showed that if G is a bipartite graph on 2n vertices such that , then G is hamiltonian, sharpening a classical result of Ore [O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55] for bipartite graphs. Here we prove that if G is a bipartite graph on 2n vertices such that , then G contains k edge-disjoint hamiltonian cycles. This extends the result of Moon and Moser and a result of R. Faudree et al. [R. Faudree, C. Rousseau, R. Schelp, Edge-disjoint Hamiltonian cycles, Graph Theory Appl. Algorithms Comput. Sci. (1984) 231-249].     

disjoint cycles containing specified independent vertices

Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ₂(G)n+k-1. Let v₁,…,v_k be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C₁,…,C_k with v_iV(C_i) for all 1ik.Then G has k vertex-disjoint cycles such that

(i) for all 1ik.

(ii) , and

(iii) At least k-1 of the k cycles are triangles.

The condition of degree sum σ₂(G)n+k-1 is sharp.

Disjoint triangles and quadrilaterals in a graph

Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ₂(G)?n+s, then G contains k disjoint cycles C₁,…,C_k satisfying |C_i|=3 for 1?i?s and |C_i|?4 for s<i?k. In the above result, the length of C_i is not specified for s<i?k. We get a result specifying the length of C_i for each s<i?k if n?3s+4(k-s)+3.     

An improved bound for disjoint directed cycles

We show that every directed graph with minimum out-degree at least $18k$ contains at least $k$ vertex disjoint cycles. This is an improvement over the result of Alon who showed this result for digraphs of minimum out-degree at least $64k$. The main benefit of the argument is that getting better results for small values of $k$ allows for further improvements to the constant.     

The Ramsey numbers for disjoint unions of graphs

For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kS_n,W_m)=R(S_n,W_m)+(k-1)n. Furthermore, if |G_i|>(|G_i|-|G_i+1|)(χ(H)-1) and R(G_i,H)=(χ(H)-1)(|G_i|-1)+1, for each i, then .     

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

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

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

On the degrees of a strongly vertex-magic graph

Let G=(V,E) be a finite graph, where |V|=n?2 and |E|=e?1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,…,n+e} with the property that for every v∈V, for some constant h. Such a labeling is strong if λ(V)={1,2,…,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if , then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.     

Covering vertices of a graph by k disjoint cycles

Let d, k and n be three integers with k3, d4k−1 and n3k. We show that if d(x)+d(y)d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{d,n} vertices of G.     

Induced disjoint paths problem in a planar digraph

As an extension of the disjoint paths problem, we introduce a new problem which we call the induced disjoint paths problem. In this problem we are given a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}. The objective is to find k paths P₁,…,P_k such that P_i is a path from s_i to t_i and P_i and P_j have neither common vertices nor adjacent vertices for any distinct i,j.The induced disjoint paths problem has several variants depending on whether k is a fixed constant or a part of the input, whether the graph is directed or undirected, and whether the graph is planar or not. We investigate the computational complexity of several variants of the induced disjoint paths problem. We show that the induced disjoint paths problem is (i) solvable in polynomial time when k is fixed and G is a directed (or undirected) planar graph, (ii) NP-hard when k=2 and G is an acyclic directed graph, (iii) NP-hard when k=2 and G is an undirected general graph.As an application of our first result, we show that we can find in polynomial time certain structures called a “hole” and a “theta” in a planar graph.     

Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible.     

Number of walks and degree powers in a graph

This note deals with the relationship between the total number of k-walks in a graph, and the sum of the k-th powers of its vertex degrees. In particular, it is shown that the the number of all k-walks is upper bounded by the sum of the k-th powers of the degrees.     

Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph

An edge of a 5-connected graph is said to be contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no contractible edge is said to be contraction critically 5-connected. Let G be a contraction critically 5-connected graph and let H be a component of the subgraph induced by the set of degree 5 vertices of G. Then it is known that |V(H)|≥4. We prove that if |V(H)|=4, then , where stands for the graph obtained from K₄ by deleting one edge. Moreover, we show that either |N_G(V(H))|=5 or |N_G(V(H))|=6 and around H there is one of two specified structures called a -configuration and a split -configuration.