首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E + and E consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E + and E are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.  相似文献   

2.
In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q n –1/q–1), (q n–1–1/q–1), (q n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q n –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q n –1/q–1), (q n–1–1/q–1), (q n–2–1/q–1)) are constructed from the ternary sequences of period q n –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.  相似文献   

3.
Let FXB be a fibre bundle with structure group G, where B is (d−1)-connected and of finite dimension, d1. We prove that the strong L–S category of X is less than or equal to , if F has a cone decomposition of length m under a compatibility condition with the action of G on F. This gives a consistent prospect to determine the L–S category of non-simply connected Lie groups. For example, we obtain cat(PU(n))3(n−1) for all n1, which might be best possible, since we have cat(PU(pr))=3(pr−1) for any prime p and r1. Similarly, we obtain the L–S category of SO(n) for n9 and PO(8). We remark that all the above Lie groups satisfy the Ganea conjecture on L–S category.  相似文献   

4.
F. Bry (J. Combin. Theory Ser. B 34 (1983), 48–57) proved that a locally finite infinite n-connected factorizable graph has at least (n−1)! 1-factors and showed that for n = 2 this lower bound is sharp. We prove that for n≥3 any infinite n-connected factorizable graph has at least n! 1-factors (which is a sharp lower bound).  相似文献   

5.
Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes   总被引:1,自引:0,他引:1  
Stefan Felsner 《Order》2001,18(1):19-37
We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.  相似文献   

6.
We construct a new family of cyclic difference sets with parameters ((3 d – 1)/2, (3 d – 1 – 1)/2, (3 d – 2 – 1)/2) for each odd d. The difference sets are constructed with certain maps that form Jacobi sums. These new difference sets are similar to Maschietti's hyperoval difference sets, of the Segre type, in characteristic two. We conclude by calculating the 3-ranks of the new difference sets.  相似文献   

7.
Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n2m) and O(n2d−1m2) for the cyclomatic numbers d=1 and d2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n2d−1+n2m+n3logn).  相似文献   

8.
LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr 2r+1 (r>0). This answers a question by L. Lovász.There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr.Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2r–1.  相似文献   

9.
Jian-Hua Yin   《Discrete Mathematics》2009,309(21):6271-6276
An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d1,d2,…,dn) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544].  相似文献   

10.
Summability of spherical h-harmonic expansions with respect to the weight function ∏j=1d |xj|jj0) on the unit sphere Sd−1 is studied. The main result characterizes the critical index of summability of the Cesàro (C,δ) means of the h-harmonic expansion; it is proved that the (C,δ) means of any continuous function converge uniformly in the norm of C(Sd−1) if and only if δ>(d−2)/2+∑j=1d κj−min1jd κj. Moreover, it is shown that for each point not on the great circles defined by the intersection of the coordinate planes and Sd−1, the (C,δ) means of the h-harmonic expansion of a continuous function f converges pointwisely to f if δ>(d−2)/2. Similar results are established for the orthogonal expansions with respect to the weight functions ∏j=1d |xj|j(1−|x|2)μ−1/2 on the unit ball Bd and ∏j=1d xjκj−1/2(1−|x|1)μ−1/2 on the simplex Td. As a related result, the Cesàro summability of the generalized Gegenbauer expansions associated to the weight function |t|(1−t2)λ−1/2 on [−1,1] is studied, which is of interest in itself.  相似文献   

11.
An edge of ak-connected graph is said to bek-contractible if the contraction of the edge results in ak-connected graph. We prove that every triangle-freek-connected graphG has an induced cycleC such that all edges ofC arek-contractible and such thatG–V(C) is (k–3)-connected (k4). This result unifies two theorems by Thomassen [5] and Egawa et. al. [3].Dedicated to Professor Toshiro Tsuzuku on his sixtieth birthday  相似文献   

12.
A microscopic theory of resonant states for the Zn-doped CuO2 plane in the superconducting phase is formulated in the effective tJ model. In the model derived from the original pd model, Zn impurities are considered as vacancies for the d states at Cu sites. In the superconducting phase, in addition to the local static perturbation induced by the vacancy, a dynamical perturbation appears that results in a frequency-dependent perturbation matrix. Using the T-matrix formalism for the Green's functions in terms of the Hubbard operators, we calculate the local density of electronic states with d, p, and s symmetries.  相似文献   

13.
The paper deals with the power and robustness of the R/S type tests under contiguous alternatives. We briefly review some long memory models in levels and volatility, and describe the R/S-type tests used to test for the presence of long memory. The empirical power of the tests is investigated when replacing the fractional difference operator (1–L) d by the operator (1–rL) d , with r<1 close to 1, in the FARIMA, LARCH and ARCH time series models. We also investigate the Gegenbauer process with a pole of the spectral density at frequency close to zero.  相似文献   

14.
If I is a set ofk – 1 arcs in ak-connected tournamentT, thenT – I has a Hamiltonian dicycle.  相似文献   

15.
T. Gneiting (1998, J. Multivariate Analysis64, 131–147) proved a relation between the primitives of the classes Φd(2) and Φd(1) of 2- and 1-symmetric characteristic functions on d, respectively. We will give a straightforward proof of his relation, answering a question of his. To do this we use the calculus of generalized hypergeometric functions.  相似文献   

16.
We call a convex subsetN of a convexd-polytopePE d ak-nucleus ofP ifN meets everyk-face ofP, where 0<k<d. We note thatP has disjointk-nuclei if and only if there exists a hyperplane inE d which bisects the (relative) interior of everyk-face ofP, and that this is possible only if [d+2/2]kd–1. Our main results are that any convexd-polytope with at most 2d–1 vertices (d3) possesses disjoint (d–1)-nuclei and that 2d–1 is the largest possible number with this property. Furthermore, every convexd-polytope with at most 2d facets (d3) possesses disjoint (d–1)-nuclei, 2d cannot be replaced by 2d+2, and ford=3, six cannot be replaced by seven.Partially supported by Hung. Nat. Found. for Sci. Research number 1238.Partially supported by the Natural Sciences and Engineering Council of Canada.Partially supported by N.S.F. grant number MCS-790251.  相似文献   

17.
The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that Gv is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least 3k/2+2. Then G has an edge e such that GV(e) is still k-connected.The bound on the minimum degree is essentially best possible.  相似文献   

18.
For a fixed multigraph H with vertices w1,…,wm, a graph G is H-linked if for every choice of vertices v1,…,vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing wi (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d such that every n-vertex graph with minimum degree at least d is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.  相似文献   

19.
The code over a finite fieldF q of orderq of a design is the subspace spanned by the incidence vectors of the blocks. It is shown here that if the design is a Steiner triple system on points, and if the integerd is such that 2 d –1<2 d+1–1, then the binary code of the design contains a subcode that can be shortened to the binary Hamming codeH d of length 2 d –1. Similarly the binary code of any Steiner quadruple system on +1 points contains a subcode that can be shortened to the Reed-Muller code (d–2,d) of orderd–2 and length 2 d , whered is as above.  相似文献   

20.
Let X1, …, Xn be independent random variables and define for each finite subset I {1, …, n} the σ-algebra = σ{Xi : i ε I}. In this paper -measurable random variables WI are considered, subject to the centering condition E(WI ) = 0 a.s. unless I J. A central limit theorem is proven for d-homogeneous sums W(n) = ΣI = dWI, with var W(n) = 1, where the summation extends over all (nd) subsets I {1, …, n} of size I = d, under the condition that the normed fourth moment of W(n) tends to 3. Under some extra conditions the condition is also necessary.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号