Light subgraphs in the family of 1-planar graphs with high minimum degree

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.     

The convex hull of degree sequences of signed graphs

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 P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, 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].     

Pairs of B-Splines with Small Support on the Four-Directional Mesh Generating a Partition of Unity

Let τ be the four-directional mesh of the plane and let Σ₁ (respectively Λ₁) 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 ²) with supports Σ₁ or Λ₁ having sufficiently high degree n, which are invariant with respect to the group of symmetries of Σ₁ or Λ₁ and whose integer translates form a partition of unity. Such splines are called complete Σ₁ and Λ₁-splines. We first give a general study of spaces of linearly independent complete Σ₁ and Λ₁-splines of class C ^k and degree n. Then, for any fixed k≥0, we prove the existence of complete Σ₁ and Λ₁-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.     

ENTIRE CHROMATIC NUMBER AND △-MATCHING OF OUTERPLANE GRAPHS

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.     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_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.     

On the existence of graphs of diameter two and defect two

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=d²−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 AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n 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 F_i,d(x)=f_i(x²+x+1−d), where f_i(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 F_i,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.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(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 q₁(G). Then we present three sharp lower bounds for q₁(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.     

The degree of an integral point in Ps minus a hypersurface

Let K be a number field of degree m with ring of integers R and absolute discriminant d_K. Given a hypersurface Z_K of degree d in the projective space P_K^us over K with Zariski closure Z in P_R^s, we give an explicit function of m, d_K, s,d, a Hermitian metric on R^s+1 ⊗_z C, and a projective height of Z defined in [1], 4.1, such that there exists an integral point in P_R^s Z of degree bounded by this function.     

On the canonical ring of curves and surfaces

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.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 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 N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Solvability of nonlocal boundary value problems for ordinary differential equations of higher order

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 x₀,x₁,…,x_n−1 in the function f(t,x₀,x₁,…,x_n−1) are allowable to be greater than 1. Some examples are given to illustrate the main results.     

Class numbers of algebraic number fields of Eisenstein type,II

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 $\text{(p ? 1)}\text{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 (h_K, n) > 1, where h_K is the class number of K. As applications, we give several results on h_K of such algebraic number fields K.     

On the number of limit cycles in small perturbations of a class of hyper-elliptic Hamiltonian systems with one nilpotent saddle

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^′=Q₁(x)+εyQ₂(x) with Q₁ and Q₂ 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.     

A plane foliation of degree different from 1 is determined by its singular scheme

We prove that a foliation _877-1 of degree ≠ 1 on P² is completely determined by its singular subscheme SingS(_877-2) of P². 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).     

On the strength of the finite intersection principle

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 ACA₀ over RCA₀, while others are strictly weaker and incomparable with WKL₀. 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 RCA₀. We also show that, modulo Σ ₂ ⁰ induction, FIP lies strictly below the atomic model theorem (AMT).     

Low rank perturbation of regular matrix polynomials

Let A(λ) be a complex regular matrix polynomial of degree ? with g elementary divisors corresponding to the finite eigenvalue λ₀. 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 λ₀, and we determine their degrees. If does not exceed the number of λ₀-elementary divisors of A(λ) with degree greater than 1, then the λ₀-elementary divisors of (A+B)(λ) are the elementary divisors of A(λ) corresponding to λ₀ with smallest degree, together with rank(B(λ)-B(λ₀)) linear λ₀-elementary divisors. Otherwise, the degree of all the λ₀-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.     

Non-isochronicity of the center in polynomial Hamiltonian systems

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 M_2m−2, can be computed such that M_2m−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 M_2m−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.     

The diameter of total domination vertex critical graphs

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).