共查询到20条相似文献,搜索用时 421 毫秒
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.
3.
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.
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.
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. 相似文献
20.
Anders Yeo 《Journal of Graph Theory》2007,55(4):325-337
A total dominating set, S, in a graph, G, has the property that every vertex in G is adjacent to a vertex in S. The total dominating number, γt(G) of a graph G is the size of a minimum total dominating set in G. Let G be a graph with no component of size one or two and with Δ(G) ≥ 3. In 6 , it was shown that |E(G)| ≤ Δ(G) (|V(G)|–γt(G)) and conjectured that |E(G)| ≤ (Δ(G)+3) (|V(G)|–γt(G))/2 holds. In this article, we prove that holds and that the above conjecture is false as there for every Δ exist Δ‐regular bipartite graphs G with |E(G)| ≥ (Δ+0.1 ln(Δ)) (|V(G)|–γt(G))/2. The last result also disproves a conjecture on domination numbers from 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 325–337, 2007 相似文献