共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
G. R. T. Hendry 《Periodica Mathematica Hungarica》1990,21(3):205-218
A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply
the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K
k
orK
k
−e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13]. 相似文献
3.
Paul Wollan 《Combinatorica》2011,31(1):95-126
We prove that for all positive integers k, there exists an integer N =N(k) such that the following holds. Let G be a graph and let Γ an abelian group with no element of order two. Let γ: E(G)→Γ be a function from the edges of G to the elements of Γ. A non-zero cycle is a cycle C such that Σ
e∈E(C)
γ(e) ≠ 0 where 0 is the identity element of Γ. Then G either contains k vertex disjoint non-zero cycles or there exists a set X ⊆ V (G) with |X| ≤N(k) such that G−X contains no non-zero cycle. 相似文献
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.
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. 相似文献
6.
PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS 总被引:5,自引:0,他引:5
Yang Aifeng Yuan Jinjiang Dept. of Appl. Math. South China Univ. of Tech. Guangdong China. Dept. of Math. Zhengzhou Univ. Henan China. 《高校应用数学学报(英文版)》2004,19(3):245-251
§1 IntroductionGraphs considered in this paper are finite and simple.For a graph G,its vertex setandedge set are denoted by V(G) and E(G) ,respectively.If vertices u and v are connected inG,the distance between u and v,denoted by d G(u,v) ,is the length ofa shortest(u,v) -pathin G.The diameter of a connected graph G is the maximum distance between two verticesof G.For X V(G) ,the neighbor set NG(X) of X is defined byNG(X) ={ y∈V(G) \X:there is x∈X such thatxy∈E(G) } .NG({ x} )… 相似文献
7.
Matthias Kriesell 《Graphs and Combinatorics》2006,22(4):481-485
Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ.
Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding
2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3. 相似文献
8.
Viresh Patel 《Order》2008,25(2):131-152
Given a poset P = (X, ≺ ), a partition X
1, ..., X
k
of X is called an ordered partition of P if, whenever x ∈ X
i
and y ∈ X
j
with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results.
Supported by an EPSRC doctoral training grant. 相似文献
9.
LetX be a 1-connected space with Moore loop space ΩX. By a well-known theorem of J. W. Milnor and J. C. Moore [7] the Hurewicz homomorphism induces an isomorphism of Hopf algebrasU(π*(ΩX) ⊗Q)→H
*(ΩX;Q). HereU(−) denotes the universal enveloping algebra and the Lie bracket on π*(ΩX) ⊗Q is given by the Samelson product.
Assume now thatX is the geometric realization of anr-reduced simplicial set,r≥3. LetL
X
be a differential graded free Lie algebra over ℤ describing the tame homotopy type ofX according to the theory of [4]. Then the main result of the present paper is the construction of a sequence of morphisms
of differential graded algebras betwenU(L
X
) and the algebraC U
*(ΩX)z of normalized cubical chains on ΩX such that the induced morphisms on homology with coefficientsR
k
are isomorphismsH
r-1+l
(U(L
x
);R
k
) ≅H
r-1+l
C U
*(ΩX);R
k
) forl≤k; hereR
0⊆R
1⊆… is a tame ring system, i. e.R
k
)⊑Q and each primep with 2p−3≤k is invertible inR
k
.
However, it is no longer true that the Pontrjagin algebraH
≤r−1+k
(ΩX; R
k
) of ΩX in degrees ≤r−1+k is determined by π*(ΩX) or by a cofibrant (-fibrant) modelM of π*(ΩX) as will be shown by an example. But there is a filtration onH
≤r−1+k
(ΩX; R
k
) such that the associated graded algebra is isomorphic toH
≤r−1+k
(U(M); R
k
).This will be proved by using a filtered Lie algebra model ofX constructed from a bigraded model of π*(ΩX).
Supported by a CNRS grant and PROCOPE
Supported by PROCOPE 相似文献
10.
A vertex labeling f : V → Z2 of a simple graph G = (V, E) induces two edge labelings f+ , f*: E → Z2 defined by f+ (uv) = f(u)+f(v) and f*(uv) = f(u)f(v). For each i∈Z2 , let vf(i) = |{v ∈ V : f(v) = i}|, e+f(i) = |{e ∈ E : f+(e) = i}| and e*f(i)=|{e∈E:f*(e)=i}|. We call f friendly if |vf(0)-vf(1)|≤ 1. The friendly index set and the product-cordial index set of G are defined as the sets{|e+f(0)-e+f(1)|:f is friendly} and {|e*f(0)-e*f(1)| : f is friendly}. In this paper we study and determine the connection between the friendly index sets and product-cordial index sets of 2-regular graphs and generalized wheel graphs. 相似文献
11.
Let G =(V, E) be a connected simple graph. A labeling f : V → Z2 induces an edge labeling f* : E → Z2 defined by f*(xy) = f(x) +f(y) for each xy ∈ E. For i ∈ Z2, let vf(i) = |f^-1(i)| and ef(i) = |f*^-1(i)|. A labeling f is called friendly if |vf(1) - vf(0)| ≤ 1. For a friendly labeling f of a graph G, we define the friendly index of G under f by if(G) = e(1) - el(0). The set [if(G) | f is a friendly labeling of G} is called the full friendly index set of G, denoted by FFI(G). In this paper, we will determine the full friendly index set of every Cartesian product of two cycles. 相似文献
12.
For an ordered k-decomposition ? = {G
1, G
2,…,G
k
} of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G
1), d(e, G
2),…,d(e, G
k
)), where d(e, G
i
) is the distance from e to G
i
. A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K
n
) ≤⌊(2n + 5)/3⌋ for n≥ 3.
Received: June 17, 1998 Final version received: August 10, 1999 相似文献
13.
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d
H
(x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let
= {F
1, F
2, ..., F
m
} be a factorization of G and H be a subgraph of G with mr edges. If F
i
, 1 ≤i≤m, has exactly r edges in common with H, then
is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges.
This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China 相似文献
14.
Let G be an outerplanar graph with maximum degree △. Let χ(G^2) and A(G) denote the chromatic number of the square and the L(2, 1)-labelling number of G, respectively. In this paper we prove the following results: (1) χ(G^2) = 7 if △= 6; (2) λ(G) ≤ △ +5 if △ ≥ 4, and ),(G)≤ 7 if △ = 3; and (3) there is an outerplanar graph G with △ = 4 such that )λ(G) = 7. These improve some known results on the distance two labelling of outerplanar graphs. 相似文献
15.
Mark Pankov 《Journal of Algebraic Combinatorics》2011,33(4):555-570
Let V be an n-dimensional vector space (4≤n<∞) and let Gk(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ
k
(V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ
k
(V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ
k
(V) is an apartment of Gk(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ
k
(V), 1<k<n−1. 相似文献
16.
We present results on total domination in a partitioned graph G = (V, E). Let γ
t
(G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ
t
(G; V
i
) be the cardinality of a smallest subset of V such that every vertex of V
i
has a neighbour in it and define the following
We summarize known bounds on γ
t
(G) and for graphs with all degrees at least δ we derive the following bounds for f
t
(G; k) and g
t
(G; k).
相似文献
(i) | For δ ≥ 2 and k ≥ 3 we prove f t (G; k) ≤ 11|V|/7 and this inequality is best possible. |
(ii) | for δ ≥ 3 we prove that f t (G; 2) ≤ (5/4 − 1/372)|V|. That inequality may not be best possible, but we conjecture that f t (G; 2) ≤ 7|V|/6 is. |
(iii) | for δ ≥ 3 we prove f t (G; k) ≤ 3|V|/2 and this inequality is best possible. |
(iv) | for δ ≥ 3 the inequality g t (G; k) ≤ 3|V|/4 holds and is best possible. |
17.
Zverovich I E 《高校应用数学学报(英文版)》2004,19(3):239-244
§1 IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献
18.
WANGWEIFAN ZHANGKEMIN 《高校应用数学学报(英文版)》1997,12(4):455-462
A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g. 相似文献
19.
Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ
tr
(G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ
tr
(G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ
tr
(G) ≤ n − diam(G) − r + 1. 相似文献
20.
Guizhen LIU 《Frontiers of Mathematics in China》2009,4(2):311-323
Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g
−, g
+) and ƒ = (ƒ
−, ƒ
+) be pairs of positive integer-valued functions defined on V(G) such that g
−(x) ⩽ ƒ
−(x) and g
+(x) ⩽ ƒ
+(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g
−(x) ⩽ id
H
(x) ⩽ ƒ
−(x) and g
+(x) ⩽ od
H
(x) ⩽ ƒ
+(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let
= {F
1, F
2,…, F
m} and H be a factorization and a subdigraph of G, respectively.
is called k-orthogonal to H if each F
i
, 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g
−(x), g
+(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.
相似文献