首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 250 毫秒
1.
A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2∨(K1∪K2) with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1∨(K1∪K2 ) with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.  相似文献   

2.
As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope Pn. In this paper, we show that Pn is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of Pn, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].  相似文献   

3.
Let τ be the four-directional mesh of the plane and let Σ1 (respectively Λ1) be the unit square (respectively the lozenge) formed by four (respectively eight) triangles of τ. We study spaces of piecewise polynomial functions in C k (R 2) with supports Σ1 or Λ1 having sufficiently high degree n, which are invariant with respect to the group of symmetries of Σ1 or Λ1 and whose integer translates form a partition of unity. Such splines are called complete Σ1 and Λ1-splines. We first give a general study of spaces of linearly independent complete Σ1 and Λ1-splines of class C k and degree n. Then, for any fixed k≥0, we prove the existence of complete Σ1 and Λ1-splines of class C k and minimal degree, but they are not unique. Finally, we describe algorithms allowing to compute the Bernstein–Bézier coefficients of these splines.  相似文献   

4.
5.
Let G be an outerplane graph with maximum degree A and the entire chromatic number Xvef(G). This paper proves that if △ ≥6, then △+ 1≤Xvef(G)≤△+ 2, and Xvef (G) = △+ 1 if and only if G has a matching M consisting of some inner edges which covers all its vertices of maximum degree.  相似文献   

6.
A n-vertex graph is said to be decomposable if for any partition (λ1,…,λp) of the integer n, there exists a sequence (V1,…,Vp) of connected vertex-disjoint subgraphs with |Vi|=λi. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.  相似文献   

7.
J. Conde 《Discrete Mathematics》2009,309(10):3166-1344
In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d2−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJn=dJn and A2+A+(1−d)In=Jn+B, where Jn denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials Fi,d(x)=fi(x2+x+1−d), where fi(x) denotes the minimal polynomial of the Gauss period , being ζi a primitive ith root of unity. We formulate a conjecture on the irreducibility of Fi,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.  相似文献   

8.
Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex vi by d(vi). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v1),d(v2),…,d(vn)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q1(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q1(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q1(G). Then we present three sharp lower bounds for q1(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.  相似文献   

9.
Let K be a number field of degree m with ring of integers R and absolute discriminant dK. Given a hypersurface ZK of degree d in the projective space PKus over K with Zariski closure Z in PRs, we give an explicit function of m, dK, s,d, a Hermitian metric on Rs+1z C, and a projective height of Z defined in [1], 4.1, such that there exists an integral point in PRs Z of degree bounded by this function.  相似文献   

10.
Let C be a curve (possibly non reduced or reducible) lying on a smooth algebraic surface. We show that the canonical ring ${ R(C, \omega_C)=\bigoplus_{k\geq 0} H^0(C, {\omega_C}^{\otimes k})}$ is generated in degree 1 if C is numerically four-connected, not hyperelliptic and even (i.e. with ω C of even degree on every component). As a corollary we show that on a smooth algebraic surface of general type with p g (S) ≥ 1 and q(S) = 0 the canonical ring R(S, K S ) is generated in degree ≤  3 if there exists a curve ${C \in |K_S|}$ numerically three-connected and not hyperelliptic.  相似文献   

11.
In this paper we construct a planar graph of degree four which admits exactly Nu 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between Nu and 2Nu and that an appropriate generalization holds for at least certain nondenumerable graphs.  相似文献   

12.
In this paper, we prove existence results for a nonlocal boundary value problem concerning a higher order differential equation. Our method is based upon the coincidence degree theory of Mawhin. The interesting point is that the degree of some variables among x0,x1,…,xn−1 in the function f(t,x0,x1,…,xn−1) are allowable to be greater than 1. Some examples are given to illustrate the main results.  相似文献   

13.
Let K be an algebraic number field, of degree n, with a completely ramifying prime p, and let t be a common divisor of n and (p ? 1)2. Then it is proved that if K does not contain the unique subfield, of degree t, of the p-th cyclotomic number field, then we have (hK, n) > 1, where hK is the class number of K. As applications, we give several results on hK of such algebraic number fields K.  相似文献   

14.
In this paper, we make a complete study on small perturbations of Hamiltonian vector field with a hyper-elliptic Hamiltonian of degree five, which is a Liénard system of the form x=y, y=Q1(x)+εyQ2(x) with Q1 and Q2 polynomials of degree respectively 4 and 3. It is shown that this system can undergo degenerated Hopf bifurcation and Poincaré bifurcation, which emerges at most three limit cycles in the plane for sufficiently small positive ε. And the limit cycles can encompass only an equilibrium inside, i.e. the configuration (3,0) of limit cycles can appear for some values of parameters, where (3,0) stands for three limit cycles surrounding an equilibrium and no limit cycles surrounding two equilibria.  相似文献   

15.
We prove that a foliation 877-1 of degree ≠ 1 on P2 is completely determined by its singular subscheme SingS(877-2) of P2. We apply this result to obtain a similar characterization of 877-3 in terms of the configuration of base points associated to its singular scheme, in case every singularity of 877-4 has non-trivial linear part. Our main motivation comes from a well-known fact: in case a foliation 877-5 of degree r ≥ 2 on Pn has only isolated singularities of multiplicity 1, then 877-6 is completely determined by its singular set Sing(877-7).  相似文献   

16.
We study the logical content of several maximality principles related to the finite intersection principle (FIP) in set theory. Classically, these are all equivalent to the axiom of choice, but in the context of reverse mathematics their strengths vary: some are equivalent to ACA0 over RCA0, while others are strictly weaker and incomparable with WKL0. We show that there is a computable instance of FIP every solution of which has hyperimmune degree, and that every computable instance has a solution in every nonzero c.e. degree. In particular, FIP implies the omitting partial types principle (OPT) over RCA0. We also show that, modulo Σ 2 0 induction, FIP lies strictly below the atomic model theorem (AMT).  相似文献   

17.
Let A(λ) be a complex regular matrix polynomial of degree ? with g elementary divisors corresponding to the finite eigenvalue λ0. We show that for most complex matrix polynomials B(λ) with degree at most ? satisfying rank the perturbed polynomial (A+B)(λ) has exactly elementary divisors corresponding to λ0, and we determine their degrees. If does not exceed the number of λ0-elementary divisors of A(λ) with degree greater than 1, then the λ0-elementary divisors of (A+B)(λ) are the elementary divisors of A(λ) corresponding to λ0 with smallest degree, together with rank(B(λ)-B(λ0)) linear λ0-elementary divisors. Otherwise, the degree of all the λ0-elementary divisors of (A+B)(λ) is one. This behavior happens for any matrix polynomial B(λ) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most ?. If A(λ) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial.  相似文献   

18.
In 2002 Jarque and Villadelprat proved that planar polynomial Hamiltonian systems of degree 4 have no isochronous centers and raised an open question for general planar polynomial Hamiltonian systems of even degree. Recently, it was proved that a planar polynomial Hamiltonian system is non-isochronous if a quantity, denoted by M2m−2, can be computed such that M2m−2≤0. As a corollary of this criterion, the open question was answered for those systems with only even degree nonlinearities. In this paper we consider the case of M2m−2>0 and give a new criterion for non-isochronicity. Applying the new criterion, we also answer the open question for some cases in which some terms of odd degree are included.  相似文献   

19.
A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γt-critical. If such a graph G has total domination number k, we call it k-γt-critical. We characterize the connected graphs with minimum degree one that are γt-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γt-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1).  相似文献   

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

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