共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
Let be a balanced bipartite graph of order , and let be the minimum degree sum of two non-adjacent vertices in different partite sets of . In 1963, Moon and Moser proved that if , then is hamiltonian. In this note, we show that if is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly cycles for sufficiently large graphs. In order to prove this, we also give a condition for the existence of vertex-disjoint alternating cycles with respect to a chosen perfect matching in . 相似文献
4.
Let and be two integers with and . For a graph and a vertex of , we use to denote the degree of in . Define to be the minimum value of , where is an independent set of with . This paper proves the following conjecture proposed by Gould et al. (2018). If is a graph of sufficiently large order with , then contains vertex-disjoint cycles. 相似文献
5.
6.
Let be integers, , , and let for each , be a cycle or a tree on vertices. We prove that every graph G of order at least n with contains k vertex disjoint subgraphs , where , if is a tree, and is a cycle with chords incident with a common vertex, if is a cycle. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 87–98, 2009 相似文献
7.
8.
Adrian Kosowski 《Discrete Applied Mathematics》2009,157(11):2552-2554
The strength of a graph G is the smallest integer s such that there exists a minimum sum coloring of G using integers {1,…,s}, only. For bipartite graphs of maximum degree Δ we show the following simple bound: s≤⌈Δ/2⌉+1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree Δ≤4. 相似文献
9.
10.
We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors. 相似文献
11.
12.
《Discrete Mathematics》2019,342(9):2482-2492
13.
Let BCd,k be the largest possible number of vertices in a bipartite Cayley graph of degree d and diameter k. We show that BCd,k≥2(k−1)((d−4)/3)k−1 for any d≥6 and any even k≥4, and BCd,k≥(k−1)((d−2)/3)k−1 for d≥6 and k≥7 such that k≡3 (mod 4). 相似文献
14.
Let be a positive integer. In this paper, we prove that for a graph with at least vertices, if max for any pair of nonadjacent vertices , then contains disjoint cycles. This generalizes the results given by Corrá di and Hajnal (1963), Enomoto (1998), and Wang (1999). 相似文献
15.
16.
A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy degG x+degG y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002 相似文献
17.
In this paper we determine the minimum and maximum values of the sum of squares of degrees of bipartite graphs with a given number of vertices and edges. 相似文献
18.
A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r‐regular uniquely hamiltonian graphs when r > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 2007 相似文献
19.
Heiko Harborth 《Discrete Mathematics》2001,230(1-3):45-48
Straight ahead cycles in drawings of graphs pass all vertices leaving the same number of edges on each side. For complete bipartite graphs K2r,2s, drawings with straight ahead Eulerian cycles and with straight ahead 4-cycles are constructed. 相似文献
20.
Given k pairs of vertices (si,ti)(1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete. 相似文献