共查询到20条相似文献,搜索用时 125 毫秒
1.
A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg
G
(u) + deg
G
(v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. 相似文献
2.
Masao Tsugaki 《Combinatorica》2009,29(1):127-129
A tree T is called a k-tree, if the maximum degree of T is at most k. In this paper, we prove that if G is an n-connected graph with independence number at most n + m + 1 (n≥1,n≥m≥0), then G has a spanning 3-tree T with at most m vertices of degree 3. 相似文献
3.
For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented.
Received: August 19, 1998 Final version received: May 17, 2000 相似文献
4.
A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that
1 £ t £ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem. 相似文献
5.
An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N
G−e
(x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present
paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4). 相似文献
6.
Zhi-quanHu FengTian 《应用数学学报(英文版)》2003,19(1):97-106
A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G)≥3κ-1/2 or δ(G)≥5κ-4.Several known results are generalized. 相似文献
7.
Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s
3(G) ≥ 2
k
−3, where s
r
(G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s
3(G) < 2
k
−2, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C
k
by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W
n
by deleting all but s consecutive spokes.
Received: January 29, 1999 Final version received: April 8, 2000 相似文献
8.
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total
coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k. 相似文献
9.
We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P
k
, a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m.
Received: June 29, 1998 Final version received: April 11, 2000 相似文献
10.
In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win. 相似文献
11.
Dr. Matthias Kriesell 《Combinatorica》2006,26(3):277-314
A non-complete graph G is called an (n,k)-graph if it is n-connected but G—X is not (n−|X|+1)-connected for any X ⊂V (G) with |X|≤k. Mader conjectured that for k≥3 the graph K2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism).
Here we prove this conjecture. 相似文献
12.
Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)2. We conjecture that linear growth of f suffices to imply hamiltonicity. 相似文献
13.
(3,k)-Factor-Critical Graphs and Toughness 总被引:1,自引:0,他引:1
A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7.
Revised: September 21, 1998 相似文献
14.
Matthias Kriesell 《Graphs and Combinatorics》2002,18(1):133-146
Let k≤n be positive integers. A finite, simple, undirected graph is called k-critically n-connected, or, briefly, an (n,k)-graph, if it is noncomplete and n-connected and the removal of any set X of at most k vertices results in a graph which is not (n−|X|+1)-connected. We present some new results on the number of vertices of an (n,k)-graph, depending on new estimations of the transversal number of a uniform hypergraph with a large independent edge set.
Received: April 14, 2000 Final version received: May 8, 2001 相似文献
15.
Camino Balbuena Martín Cera Pedro García-Vázquez Juan Carlos Valenzuela 《数学学报(英文版)》2011,27(11):2085-2100
For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K
(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem. 相似文献
16.
A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x
1,x
2, …, x
k
,y
1,y
2, …, y
k
, G contains k pairwise disjoint paths P
1, …, P
k
such that P
i
joins x
i
and y
i
for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P
1, …, P
k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence
of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph.
In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs.
Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the
Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists. 相似文献
17.
Large Vertex-Disjoint Cycles in a Bipartite Graph 总被引:4,自引:0,他引:4
Hong Wang 《Graphs and Combinatorics》2000,16(3):359-366
Let s≥2 and k be two positive integers. Let G=(V
1,V
2;E) be a bipartite graph with |V
1|=|V
2|=n≥s
k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s.
Received: March 2, 1998 Revised: October 26, 1998 相似文献
18.
Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()α≤≤ ()
n
−ω. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour
number μ(G) of G: n− (n−ω)()
n
−ω≤μ(G)≤n−α() α.
Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002 相似文献
19.
Raphael Yuster 《Order》2003,20(2):121-133
Let TT
k
denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT
k
by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c
2=1/2, c
3=5/6 and c
k
=1−2−k−log k
for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c
k
n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c
k
cannot be improved to less than 1−2−0.5k(1+o(1)).
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
20.
We prove that if G is k-connected (with k ≥ 2), then G contains either a cycle of length 4 or a connected subgraph of order 3 whose contraction results in a k-connected graph. This immediately implies that any k-connected graph has either a cycle of length 4 or a connected subgraph of order 3 whose deletion results in a (k − 1)-connected graph. 相似文献