共查询到20条相似文献,搜索用时 500 毫秒
1.
If G is a graph on n vertices and r ≥ 2, we let mr(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining mr(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that mr(G) ≥ log2 (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with mr(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound mr(G) ≥ max{n+ (G, n−(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc. 相似文献
2.
3.
The tree partition number of an r‐edge‐colored graph G, denoted by tr(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t2(K(n1, n2,…, nk)) of the complete k‐partite graph K(n1, n2,…, nk). In particular, we prove that t2(K(n, m)) = ? (m‐2)/2n? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005 相似文献
4.
Linda Lesniak-Foster 《Journal of Combinatorial Theory, Series B》1977,22(3):263-273
With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph Lm(G) of G is defined to be L(Lm-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L2(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L2(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that Lm(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs. 相似文献
5.
It has been conjectured that r(Cm, Kn) = (m − 1)(n − 1) + 1 for all m ≥ n ≥ 4. This has been proved recently for n = 4 and n = 5. In this paper, we prove that r(C5, K6) = 21. This raises the possibility that r(Cm, K6) = 5m − 4 for all m ≥ 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 99–108, 2000 相似文献
6.
Let C be a longest cycle in the 3‐connected graph G and let H be a component of G ? V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2d(u) + 2d(v) ? α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
7.
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree Δ. Our results include: (a) if Δ ≤ 3, and G ≠ K4, then a(G) ≥ n ? e/4 ? 1/4 and this is sharp for all permissible e ≡ 3 (mod 4); and (b) if Δ ≥ 3, then a(G) ≥ α(G) + (n ? α(G))/(Δ ? 1)2. Several problems remain open. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 113–123, 2001 相似文献
8.
Yuan Jinjiang 《Journal of Graph Theory》1998,28(4):203-213
We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K2, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are Cn × K2, for n ≥ 3, and C2n(1, n), for n ≥ 2, where C2n(1, n) is the graph with 2n vertices x0, x1, …, x2n−1, such that xixj is an edge of C2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998 相似文献
9.
Ralph Faudree Ronald J. Gould Linda Lesniak Terri Lindquester 《Journal of Graph Theory》1995,19(3):397-409
We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K1,m-free grphs we obtain generalizations of known results. In particular we show: Theorem. Let r ≥ 1 and m ≥ 3 be integers. Then for each nonnegative function f(r, m) there exists a constant C = C(r, m, f(r, m)) such that if G is a graph of order n (n ≥ r, n > m) with δr(G) ≥ (n/3) + C and β (G) ≥ f(r, m), then (a) G is traceable if δ(G) ≥ r and G is connected; (b) G is hamiltonian if δ(G) ≥ r + 1 and G is 2-connected; (c) G is hamiltonian-connected if δ(G) ≥ r + 2 and G is 3-connected. © 1995 John Wiley & Sons, Inc. 相似文献
10.
Xuding Zhu 《Journal of Graph Theory》2005,48(3):186-209
For 1 ≤ d ≤ k, let Kk/d be the graph with vertices 0, 1, …, k ? 1, in which i ~j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χc(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to Kk/d. The circular clique number ωc(G) of G is the maximum of those k/d for which Kk/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χc(H) = ωc(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, NG[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, NG[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph Kk/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005 相似文献
11.
Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N0 = N0(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N0 edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997 相似文献
12.
Benny Sudakov 《Random Structures and Algorithms》2005,26(3):253-265
In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph Ks on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph Kr. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph KN, contains either a red copy of G or a blue copy of H. The book with n pages is the graph Bn consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(Bn, Kn) ≤ O(n3/log3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K4‐free graph of order n which has no independent set of size n1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005 相似文献
13.
Francis K. Bell 《Journal of Graph Theory》2003,43(2):137-149
It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path Pt as a star complement for the eigenvalue ?2. The maximal graph is the line graph of Km,m if t = 2m?1, and of Km,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement Pr ∪ Ps or Pr ∪ Cs for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003 相似文献
14.
In this paper we study three-color Ramsey numbers. Let K
i,j
denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G
1, G
2 and G
3, if r(G
1, G
2)≥s(G
3), then r(G
1, G
2, G
3)≥(r(G
1, G
2)−1)(χ(G
3)−1)+s(G
3), where s(G
3) is the chromatic surplus of G
3; (ii) (k+m−2)(n−1)+1≤r(K
1,k
, K
1,m
, K
n
)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K
k,m
, K
k,m
, K
n
)≤c(n/logn), and r(C
2m
, C
2m
, K
n
)≤c(n/logn)
m/(m−1)
for sufficiently large n.
Received: July 25, 2000 Final version received: July 30, 2002
RID="*"
ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of
education ministry of China, and the foundations of Jiangsu Province
Acknowledgments. The authors are grateful to the referee for his valuable comments.
AMS 2000 MSC: 05C55 相似文献
15.
Guizhen Liu 《Journal of Graph Theory》1988,12(3):453-459
Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible. 相似文献
16.
A square-cycle is the graph obtained from a cycle by joining every pair of vertices of distance two in the cycle. The length of a square-cycle is the number of vertices in it. Let G be a graph on n vertices with minimum degree at least 2/3n and let c be the maximum length of a square-cycle in G. Pósa and Seymour conjectured that c = n. In this paper, it is proved that either c = n or 1/2n ≤ c ≤ 2/3n. As an application of this result, it is shown that G has two vertex-disjoint square-cycles C1, and C2 such that V(G) = V(C1) ∪ V(C2). © 1996 John Wiley & Sons, Inc. 相似文献
17.
Jacob Fox 《Journal of Graph Theory》2008,57(2):89-98
The Ramsey multiplicity M(G;n) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph Kn. For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C(G) to be , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of Kn. In 1980, Burr and Rosta showed that 0 ≥ C(G) ≤ 21?E for all graphs G, and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2E?1C(G) arbitrarily small. We prove that for each positive integer E, there is a graph G with E edges and C(G) ≤ E?E/2 + o(E). © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008 相似文献
18.
For an arbitrary tree T of order m and an arbitrary positive integer n, Chvátal proved that the Ramsey number r(T, Kn) = 1 + (m ? 1) (n ? 1). for graphs G, G1, and G2, we say that G arrows G1 and G2, written G → (G1, G2), if for every factorization G = R ⊕ B, either G1 is a subgraph of R or G2 is a subgraph of B. it is shown that (i) for each l ≥ 2, K1+ (m?1)(n?1) ?E(K1) → (T, Kn) for m ≥ 2/ ? 1 and n ≥ 2; (ii) K1 +,(m ?1)(n ?1) ? E(H) → (T, Kn), where H is any tree of order m ? 1, m ≥ 3 and n ≥ 2. It is further shown that result (i) is sharp with respect to the inequality m ≥ 2/? 1; in particular, examples are given to show that K1 + (2l?3)(n?1) E(K1) ? (P21?2, Kn) for all n ≥ 2, where P21?2 denotes the path of order 21 ? 2. Also result (ii) is sharp with respect to the order of H; examples aregiven to show that K1 + (m?1)(n?1)? E(K(1, m ? 1)) ?(T, Kn)for any tree T of order m and any n ≥ 2. 相似文献
19.
A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v1, v2, …, vk of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v1, v2, …, vk in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999 相似文献
20.
The book with n pages Bn is the graph consisting of n triangles sharing an edge. The book Ramsey number r(Bm,Bn) is the smallest integer r such that either Bm ? G or Bn ? G for every graph G of order r. We prove that there exists a positive constant c such that r(Bm,Bn) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献