共查询到20条相似文献,搜索用时 31 毫秒
1.
A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph
Kazuhiro Suzuki 《Graphs and Combinatorics》2006,22(2):261-269
We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors. 相似文献
2.
A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results.
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement
of Young Scientists, 15740077, 2005
This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists. 相似文献
3.
Raphael Yuster 《Graphs and Combinatorics》2001,17(3):579-587
We prove that for every ε>0 and positive integer r, there exists Δ0=Δ0(ε) such that if Δ>Δ0 and n>n(Δ,ε,r) then there exists a packing of K
n
with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn
2 edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let αΔ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥αΔ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K
n
).
Received: March 15, 1999?Final version received: October 22, 1999 相似文献
4.
Hong Wang 《Graphs and Combinatorics》2001,17(1):177-183
Let G=(V
1,V
2;E) be a bipartite graph with 2k≤m=|V
1|≤|V
2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs.
Received: December 9, 1998 Final version received: June 2, 1999 相似文献
5.
Sergey Bereg 《Graphs and Combinatorics》2009,25(2):139-144
We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning
trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning
trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G.
A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph
G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice. 相似文献
6.
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. 相似文献
7.
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 相似文献
8.
Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the
following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we
cannot replace δ − 1 by δ, respectively. 相似文献
9.
Atsushi Amahashi 《Graphs and Combinatorics》1985,1(1):111-114
A {1,3,...,2n−1}-factor of a graphG is defined to be a spanning subgraph ofG each degree of whose vertices is one of {1,3,...,2n−1}, wheren is a positive integer. In this paper, we give criterions for the existence of a {1,3,...,2n−1}-factor in a tree and in a graph. 相似文献
10.
Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible. 相似文献
11.
The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as G − e. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(G − e) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital
into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital
in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization
of diameter-vital graphs. 相似文献
12.
A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V
1 and V
2 such that each component in G[V
1] contains at most two vertices while G[V
2] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct
a planar graph G
n
with mad (G
n
) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable. 相似文献
13.
14.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献
15.
ZhaoHaixing LiuRuying ZhangShenggui 《高校应用数学学报(英文版)》2004,19(1):116-124
For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained. 相似文献
16.
Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x
1
x
2…x
r=y inG such thatx
1 ≺x
j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains
2
n
−o(n
2) relations. We prove that almost everyG
n,p satisfies this requirement if
, but almost noG
n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than
2
n
−δ(c)n
2 relations.
Partially supported by MCS Grant 8104854. 相似文献
17.
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. 相似文献
18.
Seyed Mahmoud Sheikholeslami 《Central European Journal of Mathematics》2010,8(3):468-473
A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ
t
(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt
(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar,
(Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sdγ
t
(G) ≤ 2γ
t
(G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper
we first prove that sdγ
t
(G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sdγ
t
(G)=2γ
t
(G)−1. 相似文献
19.
Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ2. For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic
lines passing through at most four, five, or six points. 相似文献
20.
Given a graph G with n vertices and stability number α(G), Turán's Theorem gives a lower bound on the number of edges in G. Furthermore, Turán has proved that the lower bound is only attained if G is the union of α(G) disjoint balanced cliques. We prove a similar result for the 2-stability number α2(G) of G, which is defined as the largest number of vertices in a 2-colorable subgraph of G. Given a graph G with n vertices and 2-stability number α2(G), we give a lower bound on the number of edges in G and characterize the graphs for which this bound is attained. These graphs are the union of isolated vertices and disjoint
balanced cliques. We then derive lower bounds on the 2-stability number, and finally discuss the extension of Turán's Theorem
to the q-stability number, for q>2.
Received: July 21, 1999 Final version received: August 22, 2000
Present address: GERAD, 3000 ch. de la Cote-Ste-Catherine, Montreal, Quebec H3T 2A7, Canada. e-mail: Alain.Hertz@gerad.ca 相似文献