共查询到20条相似文献,搜索用时 31 毫秒
1.
Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix.Recently we showed that if G has no 4-cycle, then μ2-μn-1, with equality if and only if G is the friendship graph.Here we prove that if m9 and G has no 4-cycle, then μ2m, with equality if G is a star. For 4m8 this assertion fails. 相似文献
2.
Vojtech Blint 《Discrete Applied Mathematics》2008,156(14):2740-2752
A 1-approximation of connected graph G=(V,E) is a tree T=(V,E′) with the same vertex set such that for every two vertices |dG(u,v)−dT(u,v)|1. A polynomial time algorithm is designed for finding such a tree. 相似文献
3.
A graph G is (m,n)-linked if for any two disjoint subsets R,BV(G) with |R|m and |B|n, G has two disjoint connected subgraphs containing R and B, respectively. We shall prove that a planar graph with at least six vertices is (3,3)-linked if and only if G is 4-connected and maximal. 相似文献
4.
A finite group G is called an ah-group if any two distinct conjugacy classes of G have distinct cardinality. We show that if G is an ah-group, then the non-abelian socle of G is isomorphic to one of the following:
- 1. , for 1a5, a≠2.
- 2. A8.
- 3. PSL(3,4)e, for 1e10.
- 4. A5×PSL(3,4)e, for 1e10.
- 1. , for 3a5.
- 2. PSL(3,4)e, for 1e10.
5.
Given a set TGF(q), |T|=t, wT is defined as the smallest positive integer k for which ∑yTyk≠0. It can be shown that wTt always and wTt−1 if the characteristic p divides t. T is called a Vandermonde set if wTt−1 and a super-Vandermonde set if wT=t. This (extremal) algebraic property is interesting for its own right, but the original motivation comes from finite geometries. In this paper we classify small and large super-Vandermonde sets. 相似文献
6.
Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ2(G)n+k-1. Let v1,…,vk be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C1,…,Ck with viV(Ci) for all 1ik.Then G has k vertex-disjoint cycles such that
- (i) for all 1ik.
- (ii) , and
- (iii) At least k-1 of the k cycles are triangles.
Keywords: Degree sum condition; Independent vertices; Vertex-disjoint cycles 相似文献
7.
In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2nu1 (HSOLSSOM(2nu1)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28). 相似文献
8.
9.
C. Iliopoulos K. Perdikuri E. Theodoridis A. Tsakalidis K. Tsichlas 《Journal of Discrete Algorithms》2007,5(2):229-242
In this paper we present three algorithms for the Motif Identification Problem in Biological Weighted Sequences. The first algorithm extracts repeated motifs from a biological weighted sequence. The motifs correspond to repetitive words which are approximately equal, under a Hamming distance, with probability of occurrence 1/k, where k is a small constant. The second algorithm extracts common motifs from a set of N2 weighted sequences. In this case, the motifs consists of words that must occur with probability 1/k, in 1qN distinct sequences of the set. The third algorithm extracts maximal pairs from a biological weighted sequence. A pair in a sequence is the occurrence of the same word twice. In addition, the algorithms presented in this paper improve previous work on these problems. 相似文献
10.
A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph G=(V,E), let
be a function such that 1f(v)deg(v). We present a Las Vegas algorithm which produces a book embedding of G with
pages, such that at most f(v) edges incident to a vertex v are on a single page. This result generalises that of Malitz [J. Algorithms 17 (1) (1994) 71–84]. 相似文献
11.
An efficient method to generate all edge sets XE of a graph G=(V,E), which are vertex-disjoint unions of cycles, is presented. It can be tweaked to generate (i) all cycles, (ii) all cycles of cardinality 5, (iii) all chordless cycles, (iv) all Hamiltonian cycles. 相似文献
12.
Let μ be a real measure on the line such that its Poisson integral M(z) converges and satisfies|M(x+iy)|Ae−cyα, y→+∞,for some constants A,c>0 and 0<α1. We show that for 1/2<α1 the measure μ must have many sign changes on both positive and negative rays. For 0<α1/2 this is true for at least one of the rays, and not always true for both rays. Asymptotical bounds for the number of sign changes are given which are sharp in some sense. 相似文献
13.
Javad Namazi 《Journal of Mathematical Analysis and Applications》2004,290(2):553-562
Let 1<p<∞, and k,m be positive integers such that 0(k−2m)pn. Suppose ΩRn is an open set, and Δ is the Laplacian operator. We will show that there is a sequence of positive constants cj such that for every f in the Sobolev space Wk,p(Ω), for all xΩ except on a set whose Bessel capacity Bk−2m,p is zero. 相似文献
14.
Let be a finite or infinite sequence of 2×2 matrices with entries in an integral domain. We show that, except in a very special case, is (simultaneously) triangularizable if and only if all pairs (Aj,Ak) are triangularizable, for 1j,k∞. We also provide a simple numerical criterion for triangularization.Using constructive methods in invariant theory, we define a map (with the minimal number of invariants) that distinguishes simultaneous similarity classes for non-commutative sequences over a field of characteristic ≠2. We also describe canonical forms for sequences of 2×2 matrices over algebraically closed fields, and give a method for finding sequences with a given set of invariants. 相似文献
15.
In this paper we present some new results about unlike powers in arithmetic progression. We prove among other things that for given k 4 and L 3 there are only finitely many arithmetic progressions of the form with xi , gcd(x0, xl) = 1 and 2 li L for i = 0, 1, …, k − 1. Furthermore, we show that, for L = 3, the progression (1, 1,…, 1) is the only such progression up to sign. Our proofs involve some well-known theorems of Faltings [9], Darmon and Granville [6] as well as Chabauty's method applied to superelliptic curves. 相似文献
16.
Biing-Feng Wang Shietung Peng Hong-Yi Yu Shan-Chyun Ku 《Journal of Algorithms in Cognition, Informatics and Logic》2006,59(2):107-124
Let T=(V,E) be a free tree in which each vertex has a weight and each edge has a length. Let n=|V|. Given T and parameters k and l, a (k,l)-tree core is a subtree X of T with diameter l, having k leaves, which minimizes the sum of the weighted distances from all vertices in T to X. In this paper, two efficient algorithms are presented for finding a (k,l)-tree core of T. The first algorithm has O(n2) time complexity for the case that each edge has an arbitrary length. The second algorithm has O(lkn) time complexity for the case that the lengths of all edges are 1. The (k,l)-tree core problem has an application in distributed database systems. 相似文献
17.
S. Bandyopadhyay B. Dacorogna 《Annales de l'Institut Henri Poincaré (C) Analyse Non Linéaire》2009,26(5):1717-1741
We discuss the existence of a diffeomorphism such that
φ*(g)=f