共查询到20条相似文献,搜索用时 31 毫秒
1.
It is well known that there is a planar sloop of cardinality n for each n≡2 or 4 (mod 6) (Math. Z. 111 (1969) 289–300). A semi-planar sloop is a simple sloop in which each triangle either generates the whole sloop or the 8-element sloop. In fact, Quackenbush (Canad. J. Math. 28 (1976) 1187–1198) has stated that there should be such semi-planar sloops. In this paper, we construct a semi-planar sloop of cardinality 2 n for each n≡2 or 4 (mod 6). Consequently, we may say that there is a semi-planar sloop that is not planar of cardinality m for each m>16 and m≡4 or 8 (mod 12). Moreover, Quackenbush (Canad. J. Math. 28 (1976) 1187–1198) has proved that each finite simple planar sloop generates a variety, which covers the smallest non-trivial subvariety (the variety of all Boolean sloops) of the lattice of the subvarieties of all sloops. Similarly, it is easy to show that each finite semi-planar sloop generates another variety, which also covers the variety of all Boolean sloops. Furthermore, for any finite simple sloop
of cardinality n, the author (Beiträge Algebra Geom. 43 (2) (2002) 325–331) has constructed a subdirectly irreducible sloop
of cardinality 2 n and containing
as the only proper normal subsloop. Accordingly, if
is a semi-planar sloop, then the variety
generated by
properly contains the subvariety
. 相似文献
2.
It has been shown by Lei, in his recent paper, that there exists a large set of Kirkman triple systems of order uv (LKTS( uv)) if there exist an LKTS( v), a TKTS( v) and an LR( u), where a TKTS( v) is a transitive Kirkman triple system of order v, and an LR( u) is a new kind of design introduced by Lei. In this paper, we improve this product construction by removing the condition “there exists a TKTS( v)”. Our main idea is to use transitive resolvable idempotent symmetric quasigroups instead of TKTS. As an application, we can combine the known results on LKTS and LR-designs to obtain the existence of an LKTS(3 nm(2·13 n1+1)(2·13 nt+1)) for n1, m{1,5,11,17,25,35,43,67,91,123}{2 2r+125 s+1 : r0, s0}, t0 and ni1 ( i=1,…, t). 相似文献
3.
A graph G = ( V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp( G), of G. In this paper, we find the minimum number, h( n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h( n, k) edges when k is 3 or even. 相似文献
4.
A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix ( w( u, v)) specifying minimum channel separations. An assignment f: V→{0,1,2,…} is feasible if the distance f( u) − f( v) w( u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment. We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦3) steps. 相似文献
5.
Let G be a solvable block transitive automorphism group of a 2−( v,5,1) design and suppose that G is not flag transitive. We will prove that - (1) if G is point imprimitive, then v=21, and GZ21:Z6;
- (2) if G is point primitive, then GAΓL(1,v) and v=pa, where p is a prime number with p≡21 (mod 40), and a an odd integer.
相似文献
6.
In this article, we establish the existence of an LHMTS( mv) for v ≡ 2 (mod 6) and m≡ 3 (mod 6). Thus there exists an LHMTS( mv) if and only if v( v-1) m2 ≡ 0 (mod 3) except possibly for v=6, m≡ 1, 5 (mod 6) and m≠1. In the similar way, the existence of LHDTS( mv) is completely determined, i.e., there exists an LHDTS( mv) if and only if v( v-1) m2 ≡ 0 (mod 3). 相似文献
7.
The bandwidth B( G) of a graph G is the minimum of the quantity max {|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[ H], is the graph with vertex set V( G)× V( H) and with ( u1, v1) is adjacent to ( u2, v2) if either u1 is adjacent to u2 in G or u1= u2 and v1 is adjacent to v2 in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D( G). For two distinct vertices x, yV( G), we define wG( x, y) as the maximum number of internally vertex-disjoint ( x, y)-paths whose lengths are the distance between x and y. We define w( G) as the minimum of wG( x, y) over all pairs of vertices x, y of G with the distance between x and y is equal to D( G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if | V( G)|= B( G) D( G)− w( G)+2, then B( G[ H])=( B( G)+1)| V( H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph. 相似文献
8.
An ( m, n; u, v; c)-system is a collection of components, m of valency u−1 and n of valency v−1, whose difference sets form a perfect system with threshold c. If there is an ( m, n; 3, 6; c)-system, then m2 c−1; and if there is a (2 c−1, n; 3, 6; c)-system, then 2 c−1 n. For all sufficiently large c, there are (2 c−1, n; 3, 6; c)-systems with a split at 3 c+6 n−1 at least when n=1, 5, 6 and 7, but such systems do not exist for n=2, 3 or 4. We describe here a general method of construction for (2c−1, n; 3, 6; c)-systems and use it to show that there are such systems for 2n4 and certain values of c depending on n. We also discuss the limitations of this method. 相似文献
9.
A dominating set for a graph G = ( V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which { v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m1 ( G, D) denote the number of edges that have neither endpoint in D, and let m2 ( G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair ( m1 ( G, D), m2 ( G, D)) can attain for connected graphs having a given domination number. 相似文献
10.
In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an Sλ( t, k, v) such that then there exists an Sλ(v−t+1)( t, k, v+1) having v+1 pairwise disjoint subdesigns Sλ( t, k, v). Moreover, if Bi and Bj are any two blocks belonging to two distinct such subdesigns, then d| Bi∩ Bj|< k− h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an Sλ( t, k, v) such that where m=min{ s, v− k} and n=min{ i, t}, then there exists an having
pairwise disjoint subdesigns Sλ( t, k, v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs. 相似文献
11.
Given a graph G and a positive integer d, an L( d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then | f( u)− f( v)| d; if u and v are not adjacent but there is a two-edge path between them, then | f( u)− f( v)|1. The L( d,1)-number of G, λ d( G), is defined as the minimum m such that there is an L( d,1)-labeling f of G with f( V){0,1,2,…, m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ d( G)Δ 2+( d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ d( G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. 相似文献
12.
Given a graph G = ( V,E) and a finite set L( v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f: V → vεVL( V) such that (i) f( v)ε L( v) for each vε V and (ii) f( u) ≠ f( v) whenever u, vε V and uvε E. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L( v) has at most three elements, (2) each “color” xε vεVL( v) occurs in at most three sets L( v), (3) each vertex vε V has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too. 相似文献
13.
Necessary conditions for existence of a ( v, k,λ) perfect Mendelsohn design (or PMD) are v k and λ v( v − 1) ≡ 0 mod k. When k = 7, this condition is satisfied if v ≡ 0 or 1 mod 7 and v 7 when λ 0 mod 7 and for all v 7 when λ ≡ 0 mod 7. Bennett, Yin and Zhu have investigated the existence problem for k = 7, λ = 1 and λ even; here we provide several improvements on their results and also investigate the situation for λ odd. We reduce the total number of unknown ( v,7,λ)-PMDs to 36,31 for λ = 1 and 5 for λ > 1. In particular, v = 294 is the largest unknown case for λ = 1, and the only unknown cases for λ > 1 are for v = 42, λ [2,3,5,9] and v = 18, λ = 7. 相似文献
14.
An intersection representation of a graph is a function gf mapping vertices to sets such that for any u ≠ v, u is adjacent to v iff gf( u) ∩ gf( v) ≠ . The intersection class defined by a set of sets ∑ is the set of all graphs having an intersection representation using sets from ∑. Interval graphs and chordal graphs are well-studied examples of intersection classes. This paper introduces the notion of completeness for intersection classes. That is, determining precisely what restrictions can be made on the allowable sets without losing the power to represent any graph in the intersection class. The solution to this problem is presented for the chordal graphs. 相似文献
15.
We consider the nonlinear parabolic equation ut = ( k( u) ux) x + b( u) x, where u = u( x, t, x ε R1, t > 0; k( u) ≥ 0, b( u) ≥ 0 are continuous functions as u ≥ 0, b (0) = 0; k, b > 0 as u > 0. At t = 0 nonnegative, continuous and bounded initial value is prescribed. The boundary condition u(0, t) = Ψ( t) is supposed to be unbounded as t → +∞. In this paper, sufficient conditions for space localization of unbounded boundary perturbations are found. For instance, we show that nonlinear equation ut = ( unux) x + ( uβ) x, n ≥ 0, β >; n + 1, exhibits the phenomenon of “inner boundedness,” for arbitrary unbounded boundary perturbations. 相似文献
16.
A graph G = G( V, E) with lists L( v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L( v). We say G is k- choosable if there is at least one L-list colouring for every possible list assignment L with L( v) = k v V( G). Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd
s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”. 相似文献
17.
Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph ( S, E) with vertex set S and edge set E such that for u, vS, uvE if and only if u+ vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ( G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ( Kn− E( Kr)) for r2 n/3−1, (ii) obtain a lower bound for ζ( Kn− E( Kr)) when 2 r<2 n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ( Kr,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of Kr,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211). 相似文献
18.
We prove that for λ ≥ 0, p ≥ 3, there exists an open ball B L2(0,1) such that the problem − (|u′|p−2 u′)′ − λ|u|p−2u = f, in (0,1) , subject to certain separated boundary conditions on (0,1), has a solution for f B. 相似文献
19.
A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L( w)= L( u)+ L( v). The sum number σ( G) of a graph G=( V, E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ( G)| E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=( V, E) with fixed | V|3 and | E|, the average of σ( G) is at least . In other words, for most graphs, σ( G)Ω(| E|). 相似文献
20.
Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ 1. We consider the power method, i.e. that of choosing a vector v0 and setting vk = Akv0; then the Rayleigh quotients Rk = ( Avk, vk)/( vk, vk) usually converge to λ 1 as k → ∞ (here ( u, v) denotes their inner product). In this paper we give two methods for determining how close Rk is to λ 1. They are both based on a bound on λ 1 − Rk involving the difference of two consecutive Rayleigh quotients and a quantity ω k. While we do not know how to directly calculate ω k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ 1 − Rk which is proportional to (λ 2/λ 1) 2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ). 相似文献
|