共查询到20条相似文献,搜索用时 31 毫秒
1.
In 2000, Enomoto and Ota [J Graph Theory 34 (2000), 163–169] stated the following conjecture. Let G be a graph of order n, and let n1, n2, …, nk be positive integers with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} {{n}}_{{{i}}} = {{n}}\end{eqnarray*}. If σ2(G)≥n+ k?1, then for any k distinct vertices x1, x2, …, xk in G, there exist vertex disjoint paths P1, P2, …, Pk such that |Pi|=ni and xi is an endpoint of Pi for every i, 1≤i≤k. We prove an asymptotic version of this conjecture in the following sense. For every k positive real numbers γ1, …, γk with \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} \gamma_{{{i}}} = {{1}}\end{eqnarray*}, and for every ε>0, there exists n0 such that for every graph G of order n≥n0 with σ2(G)≥n+ k?1, and for every choice of k vertices x1, …, xk∈V(G), there exist vertex disjoint paths P1, …, Pk in G such that \begin{eqnarray*}\sum\nolimits_{{{i}} = {{1}}}^{{{k}}} |{{P}}_{{{i}}}| = {{n}}\end{eqnarray*}, the vertex xi is an endpoint of the path Pi, and (γi?ε)n<|Pi|<(γi + ε)n for every i, 1≤i≤k. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 37–51, 2010 相似文献
2.
Jiuying Dong 《Journal of Applied Mathematics and Computing》2010,34(1-2):485-493
The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ 2(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:
- Let k≥2 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k of length at most four such that v i ∈V(C i ) for all 1≤i≤k.
- Let k≥1 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k such that:
- v i ∈V(C i ) for all 1≤i≤k.
- V(C 1)∪???∪V(C k )=V(G), and
- |C i |≤4, 1≤i≤k?1.
3.
4.
Let G be a graph of order n, and n = Σki=1 ai be a partition of n with ai ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v1,…, vk of G, the vertex set V(G) can be decomposed into k disjoint subsets A1,…, Ak so that |Ai| = ai,viisAi is an element of Ai and “the subgraph induced by Ai contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc. 相似文献
5.
H. J. Broersma J. Den Van Heuvel H. A. Jung H. J. Veldman 《Journal of Graph Theory》1993,17(3):373-385
For a graph G and an integer k, denote by Vk the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc. 相似文献
6.
Nathan Linial 《Journal of Combinatorial Theory, Series B》1984,36(1):16-25
A. Frank (Problem session of the Fifth British Combinatorial Conference, Aberdeen, Scotland, 1975) conjectured that if G = (V, E) is a connected graph with all valencies ≥k and a1,…,ak ≥ 2 are integers with Σ ai = |V |, then V may be decomposed into subsets A1,…,Ak so that |Ai | = ai and the subgraph spanned by Ai in G has no isolated vertices (i = 1,…,k). The case k = 2 is proved in Maurer (J. Combin. Theory Ser. B27 (1979), 294–319) along with some extensions. The conjecture for k = 3 and a result stronger than Maurer's extension for k = 2 are proved. A related characterization of a k-connected graph is also included in the paper, and a proof of the conjecture for the case a1 = a2 = … = ak?1 = 2. 相似文献
7.
Yoshimi Egawa Hikoe Enomoto Ralph J. Faudree Hao Li Ingo Schiermeyer 《Journal of Graph Theory》2003,43(3):188-198
It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v1,v2,…,vk} ? V(G), there is a 2‐factor of G with precisely k cycles {C1,C2,…,Ck} such that vi ∈ V(Ci) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003 相似文献
8.
Hong Wang 《Journal of Graph Theory》1997,26(2):105-109
We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e1, …, ek of G, there exist k vertex-disjoint cycles C1, …, Ck in G such that ei ∈ E(Ci) for all i ∈ {1, …, k} and V(C1 ∪ ···∪ Ck) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997 相似文献
9.
Let G be a simple undirected graph of order n. For an independent set S ? V(G) of k vertices, we define the k neighborhood intersections Si = {v ? V(G)&#92;S|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with si = |Si|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem. 相似文献
10.
Jarmila Chvátalová 《Discrete Mathematics》1975,11(3):249-253
If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.Pn will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. Pm × Pn will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(Pm × Pn) = min(m, n). 相似文献
11.
The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ E (G) of the graph G via θ E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight. 相似文献
12.
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 相似文献
13.
A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ+(G) = max{d+(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)2 + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998 相似文献
14.
Let G = (V, E) be a connected graph. The hamiltonian index h(G) (Hamilton-connected index hc(G)) of G is the least nonnegative integer k for which the iterated line graph L k (G) is hamiltonian (Hamilton-connected). In this paper we show the following. (a) If |V(G)| ≥ k + 1 ≥ 4, then in G k , for any pair of distinct vertices {u, v}, there exists k internally disjoint (u, v)-paths that contains all vertices of G; (b) for a tree T, h(T) ≤ hc(T) ≤ h(T) + 1, and for a unicyclic graph G, h(G) ≤ hc(G) ≤ max{h(G) + 1, k′ + 1}, where k′ is the length of a longest path with all vertices on the cycle such that the two ends of it are of degree at least 3 and all internal vertices are of degree 2; (c) we also characterize the trees and unicyclic graphs G for which hc(G) = h(G) + 1. 相似文献
15.
Daniel W. Cranston Anja Pruchnewski Zsolt Tuza Margit Voigt 《Journal of Graph Theory》2012,71(1):18-30
The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[Sk], where Sk: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(Sk) in G between the components of G[Sk]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012 相似文献
16.
One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S1 + deg S2 ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S1, S2 ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed. 相似文献
17.
Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v1a1v2v3···vt−1vt of distinct vertices v1, v2,⋖, vt and distinct arcs a1, ⋖, at−1 such that vi precedes vt−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as vi's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997 相似文献
18.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
of length at most four such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k, V(C
1) ∪...∪ V(C
k
) = V(G), and |C
i
| ≤ 4 for all 1 ≤ i ≤ k − 1.
The condition of degree sum σ2(G) ≥ n + k − 1 is sharp.
Received: December 20, 2006. Final version received: December 12, 2007. 相似文献
19.
We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = Kn (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998 相似文献
20.
Peter J. Slater 《Journal of Graph Theory》1978,2(3):209-222
For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize es(u) = max {d(u, v): v ∈ S} and ds(u) = ∑u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let rk(u) = max {∑s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which rk(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included. 相似文献