共查询到20条相似文献,搜索用时 671 毫秒
1.
Arthur S. Finbow 《Discrete Applied Mathematics》2010,158(12):1224-368
For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V1,V2,…,Vm where Vi is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z3 do not have finite packing chromatic numbers. 相似文献
2.
A t-spread set [1] is a set of (t + 1) × (t + 1) matrices over GF(q) such that ∥C∥ = qt+1, 0 ? C, I?C, and det(X ? Y) ≠ 0 if X and Y are distinct elements of . The amount of computation involved in constructing t-spread sets is considerable, and the following construction technique reduces somewhat this computation. Construction: Let be a subgroup of GL(t + 1, q), (the non-singular (t + 1) × (t + 1) matrices over GF(q)), such that ∥G∥|at+1, and det (G ? H) ≠ 0 if G and H are distinct elements of . Let A1, A2, …, An?GL(t + 1, q) such that det(Ai ? G) ≠ 0 for i = 1, …, n and all G?G, and det(Ai ? AjG) ≠ 0 for i > j and all G?G. Let , and ∥C∥ = qt+1. Then is a t-spread set. A t-spread set can be used to define a left V ? W system over V(t + 1, q) as follows: x + y is the vector sum; let e?V(t + 1, q), then xoy = yM(x) where M(x) is the unique element of with x = eM(x). Theorem: Letbe a t-spread set and F the associatedV ? Wsystem; the left nucleus = {y | CM(y) = C}, and the middle nucleus = }y | M(y)C = C}. Theorem: Forconstructed as aboveG ? {M(x) | x?Nλ}. This construction technique has been applied to construct a V ? W system of order 25 with ∥Nλ∥ = 6, and ∥Nμ∥ = 4. This system coordinatizes a new projective plane. 相似文献
3.
Haruko Okamura 《Graphs and Combinatorics》2005,21(4):503-514
Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {si, ti}⊆Xi⊆V(G) (i=1,2) and X1∩X2=∅. We here prove that if k is even and e(Xi)≤2k−1 (i=1,2), then there exist paths P1 and P2 such that Pi joins si and ti, V(Pi)⊆Xi (i=1,2) and G − E(P1∪P2) is (k−2)-edge-connected (for odd k, if e(X1)≤2k−2 and e(X2)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing
given edges. 相似文献
4.
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.
5.
6.
A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7. 相似文献
7.
Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C0,C1,…,Ck such that k+1<|E(C0)|<|E(C1)|<?<|E(Ck)|, |E(Ci)−E(Ci−1)|=2, 1≤i≤k−1, and 1≤|E(Ck)|−|E(Ck−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(Ck)|−|E(Ck−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if dG(u)+dG(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C0,C1,…,Ck such that k+1<|E(C0)|<|E(C1)|<?<|E(Ck)|, |E(Ci)−E(Ci−1)|=2, 1≤i≤k−1, and 1≤|E(Ck)|−|E(Ck−1)|≤2, and furthermore, if dG(u)+dG(v)≥6k+1, then |E(Ck)|−|E(Ck−1)|=2. 相似文献
8.
Robert W. Irving 《Discrete Mathematics》1974,9(3):251-264
The generalised Ramsey number R(G1, G2,..., Gk) is defined as the smallest integer n such that, if the edges of Kn, the complete graph on n vertices, are coloured using k colours C1, C2,..., Ck, then for some i(1≤i≤k) there is a subgraph Gi of Kn with all of its edges colour Ci. When G1=G2=...,Gk=G, we use the more compact notation Rk(G).The generalised Ramsey numbers Rk(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2. 相似文献
9.
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 相似文献
10.
《Applied Mathematics Letters》2002,15(5):623-626
For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where , then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′as(G), and obtain the χ′as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G. 相似文献
11.
Olof Heden Juliane Lehmann Esmeralda N?stase Papa Sissokho 《Designs, Codes and Cryptography》2012,64(3):265-274
A subspace partition Π of V?= V(n, q) is a collection of subspaces of V such that each 1-dimensional subspace of V is in exactly one subspace of Π. The size of Π is the number of its subspaces. Let σ q (n, t) denote the minimum size of a subspace partition of V in which the largest subspace has dimension t, and let ρ q (n, t) denote the maximum size of a subspace partition of V in which the smallest subspace has dimension t. In this article, we determine the values of σ q (n, t) and ρ q (n, t) for all positive integers n and t. Furthermore, we prove that if n ≥?2t, then the minimum size of a maximal partial t-spread in V(n +?t ?1, q) is σ q (n, t). 相似文献
12.
Let k≥1 be an integer and G=(V1,V2;E) a bipartite graph with |V1|=|V2|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V1 and y∈V2, , then for any k independent edges e1,…,ek of G, G has a 2-factor with k+1 cycles C1,…,Ck+1 such that ei∈E(Ci) and |V(Ci)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp. 相似文献
13.
The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V 1,V 2;E) be a bipartite graph with |V 1|=|V 2|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V 1 and y∈V 2, then, for any k independent edges e 1,…,e k of G, G contains k vertex-disjoint quadrilaterals C 1,…,C k such that e i ∈E(C i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V 1|=|V 2|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C 1,…,C k containing specified edges of G. 相似文献
14.
Shinya Fujita 《Discrete Mathematics》2009,309(11):3534-3540
Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{dG(x),dG(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H1,…,Hk such that V(H1)∪?∪V(Hk)=V(G) and Hi is a cycle or K1 or K2 for each 1≤i≤k, unless k=2 and G=C5, or k=3 and G=K1∪C5. 相似文献
15.
Williani T Trotter 《Journal of Combinatorial Theory, Series A》1976,20(1):114-123
For a poset X, Dim(X) is the smallest positive integer t for which X is isomorphic to a subposet of the cartesian product of t chains. Hiraguchi proved that if | X | ? 4, then Dim(X) ? [| X |/2]. For each k ? 2, we define Dimk(X) as the smallest positive integer t for which X is isomorphic to a subposet of the cartesian product of t chains, each of length k. We then prove that if | X | ? 5, Dim3(X) ? {| X |/2} and if | X | ? 6, then Dim4(X) ? [| X |/2]. 相似文献
16.
Hong Wang 《Graphs and Combinatorics》1994,10(2-4):271-281
Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC 1,C 2,...,C k such thats ≤l(C i ) ≤q for 1 ≤i ≤r arnds ≤l(C i ) ≤q + 1 fork -r <i ≤k, where l(Ci) denotes the length ofC i . 相似文献
17.
Let k≥1 be an integer and G=(V 1,V 2;E) a bipartite graph with |V 1|=|V 2|=n such that n≥2k+2. Our result is as follows: If $d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil$ for any nonadjacent vertices x∈V 1 and y∈V 2, then for any k distinct vertices z 1,…,z k , G contains a 2-factor with k+1 cycles C 1,…,C k+1 such that z i ∈V(C i ) and l(C i )=4 for each i∈{1,…,k}. 相似文献
18.
Chandan K. Dubey 《Discrete Applied Mathematics》2009,157(1):149-163
An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a1,b1),(a2,b2),…,(am,bm) such that G(V−{aj1,bj1,…,ajk,bjk}) is also an X-critical graph for arbitrary set of indices {j1,…,jk}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x1,y1),…,(xt,yt) such that xi,yi∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G. 相似文献
19.
Yaki Sternfeld 《Israel Journal of Mathematics》1986,55(3):350-362
LetX andY i, 1 ≦i ≦k, be compact metric spaces, and letρ i:X →Y i be continuous functions. The familyF={ρ i} i 1/k is said to be ameasure separating family if there exists someλ > 0 such that for every measureμ inC(X)*, ‖μ o ρ i ?1 ‖ ≧λ ‖μ ‖ holds for some 1 ≦i ≦k.F is auniformly (point) separating family if the above holds for the purely atomic measures inC(X)*. It is known that fork ≦ 2 the two concepts are equivalent. In this note we present examples which show that fork ≧ 3 measure separation is a stronger property than uniform separation of points, and characterize those uniformly separating families which separate measures. These properties and problems are closely related to the following ones: letA 1,A 2, ...,A k be closed subalgebras ofC(X); when isA 1 +A 2 + ... +A k equal to or dense inC(X)? 相似文献
20.
Let R be a K-algebra acting densely on VD, where K is a commutative ring with unity and V is a right vector space over a division K-algebra D. Let ρ be a nonzero right ideal of R and let f(X1,…,Xt) be a nonzero polynomial over K with constant term 0 such that μR≠0 for some coefficient μ of f(X1,…,Xt). Suppose that d:R→R is a nonzero derivation. It is proved that if rankd(f(x1,…,xt))?m for all x1,…,xt∈ρ and for some positive integer m, then either ρ is generated by an idempotent of finite rank or d=ad(b) for some b∈End(VD) of finite rank. In addition, if f(X1,…,Xt) is multilinear, then b can be chosen such that rank(b)?2(6t+13)m+2. 相似文献