The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

Subdivisions of graphs: A generalization of paths and cycles

One of the basic results in graph theory is Dirac's theorem, that every graph of order n?3 and minimum degree ?n/2 is Hamiltonian. This may be restated as: if a graph of order n and minimum degree ?n/2 contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to (n-t)/2 if H has t components that are trees.We attempt a similar generalization of the Corrádi-Hajnal theorem that every graph of order ?3k and minimum degree ?2k contains k disjoint cycles. Again, this may be restated as: every graph of order ?3k and minimum degree ?2k contains a subdivision of kK₃. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order ?n and minimum degree ?n-k contains a subdivision of H.     

The complex of non-crossing diagonals of a polygon

Given a convex n-gon P in R² with vertices in general position, it is well known that the simplicial complex θ(P) with vertex set given by diagonals in P and facets given by triangulations of P is the boundary complex of a polytope of dimension n−3. We prove that for any non-convex polygonal region P with n vertices and h+1 boundary components, θ(P) is a ball of dimension n+3h−4. We also provide a new proof that θ(P) is a sphere when P is convex with vertices in general position.     

Conditional colorings of graphs

For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χ_r(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated.     

Monge-Ampère equations and moduli spaces of manifolds of circular type

A (bounded) manifold of circular type is a complex manifold M of dimension n admitting a (bounded) exhaustive real function u, defined on M minus a point xo, so that: (a) it is a smooth solution on M?{xo} to the Monge-Ampère equation n(ddcu)=0; (b) xo is a singular point for u of logarithmic type and eu extends smoothly on the blow up of M at xo; (c) ddc(eu)>0 at any point of M?{xo}. This class of manifolds naturally includes all smoothly bounded, strictly linearly convex domains and all smoothly bounded, strongly pseudoconvex circular domains of Cn.A set of modular parameters for bounded manifolds of circular type is considered. In particular, for each biholomorphic equivalence class of them it is proved the existence of an essentially unique manifold in normal form. It is also shown that the class of normalizing maps for an n-dimensional manifold M is a new holomorphic invariant with the following property: it is parameterized by the points of a finite dimensional real manifold of dimension n² when M is a (non-convex) circular domain while it is of dimension n²+2n when M is a strictly linearly convex domain. New characterizations of the circular domains and of the unit ball are also obtained.     

The number of distinct symbols in sections of rectangular arrays

We investigate transversals of rectangular arrays. For positive integers m and n, where 2?m?n an m by n array consists of mn cells arranged in m rows and n columns. Each cell contains one symbol. When m=n we speak of an array of order n. A section in the array consists of m cells, one from each row and no two from the same column. A transversal is a section whose m symbols are distinct. A partial transversal is a subset of a transversal. We investigate the existence in an array of a section with many different symbols, in particular the existence of a transversal.     

The jumping phenomenon of the dimensions of cohomology groups of tangent sheaf

Let X be a compact complex manifold. Consider a small deformation π: X → B of X, the dimensions of the cohomology groups of tangent sheaf H^q(X_t, TX_t) may vary under this deformation. This article studies such phenomena by studying the obstructions to deform a class in H^q(X, TX) with parameter t and gets a formula for the obstructions.     

Asymptotic expansions of the ordered spectrum of symmetric matrices

In this work, we build on ideas of Torki (2001 [6]) and show that if a symmetric matrix-valued map t?A(t) has a one-sided asymptotic expansion at t=0⁺ of order K then so does t?λ_m(A(t)), where λ_m is the mth largest eigenvalue. We derive formulas for computing the coefficients A₀,A₁,…,A_K in the asymptotic expansion. As an application of the approach we give a new proof of a classical result due to Kato (1976 [3]) about the one-sided analyticity of the ordered spectrum under analytic perturbations. Finally, as a demonstration of the derived formulas, we compute the first three terms in the asymptotic expansion of λ_m(A+tE) for any fixed symmetric matrices A and E.     

Geodeticity of the contour of chordal graphs

A vertex v is a boundary vertex of a connected graph G if there exists a vertex u such that no neighbor of v is further away from u than v. Moreover, if no vertex in the whole graph V(G) is further away from u than v, then v is called an eccentric vertex of G. A vertex v belongs to the contour of G if no neighbor of v has an eccentricity greater than the eccentricity of v. Furthermore, if no vertex in the whole graph V(G) has an eccentricity greater than the eccentricity of v, then v is called a peripheral vertex of G. This paper is devoted to study these kinds of vertices for the family of chordal graphs. Our main contributions are, firstly, obtaining a realization theorem involving the cardinalities of the periphery, the contour, the eccentric subgraph and the boundary, and secondly, proving both that the contour of every chordal graph is geodetic and that this statement is not true for every perfect graph.     

Genericity and amalgamation of classes of Banach spaces

We study universality problems in Banach space theory. We show that if A is an analytic class, in the Effros-Borel structure of subspaces of C([0,1]), of non-universal separable Banach spaces, then there exists a non-universal separable Banach space Y, with a Schauder basis, that contains isomorphs of each member of A with the bounded approximation property. The proof is based on the amalgamation technique of a class C of separable Banach spaces, introduced in the paper. We show, among others, that there exists a separable Banach space R not containing L¹(0,1) such that the indices β and rND are unbounded on the set of Baire-1 elements of the ball of the double dual R∗∗ of R. This answers two questions of H.P. Rosenthal.We also introduce the concept of a strongly bounded class of separable Banach spaces. A class C of separable Banach spaces is strongly bounded if for every analytic subset A of C there exists Y∈C that contains all members of A up to isomorphism. We show that several natural classes of separable Banach spaces are strongly bounded, among them the class of non-universal spaces with a Schauder basis, the class of reflexive spaces with a Schauder basis, the class of spaces with a shrinking Schauder basis and the class of spaces with Schauder basis not containing a minimal Banach space X.     

Periodic solutions of semilinear equations of evolution of compact type

The existence of solutions in a weak sense of x′ + (A + B(t, x))x = f(t, x), x(0) = x(T) is established under the conditions that A generates a semigroup of compact type on a Hilbert space H; B(t,x) is a bounded linear operator and f(t, x) a function with values in H; for each square integrable ?(t) the problem with B(t, ?(t)) and f(t, ?(t)) in place of B(t, x) and f(t, x) has a unique solution; and B and f satisfy certain boundedness and continuity conditions.     

Determinant of the distance matrix of a tree with matrix weights

Let T be a tree with n vertices and let D be the distance matrix of T. According to a classical result due to Graham and Pollack, the determinant of D is a function of n, but does not depend on T. We allow the edges of T to carry weights, which are square matrices of a fixed order. The distance matrix D of T is then defined in a natural way. We obtain a formula for the determinant of D, which involves only the determinants of the sum and the product of the weight matrices.     

Hamiltonicity and pancyclicity of cartesian products of graphs

The cartesian product of a graph G with K₂ is called a prism over G. We extend known conditions for hamiltonicity and pancyclicity of the prism over a graph G to the cartesian product of G with paths, cycles, cliques and general graphs. In particular we give results involving cubic graphs and almost claw-free graphs.We also prove the following: Let G and H be two connected graphs. Let both G and H have a 2-factor. If Δ(G)≤g^′(H) and Δ(H)≤g^′(G) (we denote by g^′(F) the length of a shortest cycle in a 2-factor of a graph F taken over all 2-factorization of F), then G□H is hamiltonian.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

A conjugated version of the countable dense homogeneity

We are interested in finding a homeomorphism h of a space X with h⁻¹○Φ○h(A)=B for a given bijection Φ of X and every pair of countable dense subsets A and B of X. For a separable Banach space X, such a homeomorphism h always exists provided the fixed-point set of Φ has the empty interior. Moreover, h can be chosen to be real-analytic. As a consequence, there exists a real analytic flow that sends A onto B after time t=1. Actually, for X=Rn, any bounded real-analytic vector field can be approximated by a real-analytic vector field whose induced flow sends A onto B after time t=1. Topological and Cp smooth counterparts of these results are also obtained.     

Boundary singularities of solutions of N-harmonic equations with absorption

We study the boundary behaviour of solutions u of −ΔNu+|u|^q−1u=0 in a bounded smooth domain Ω⊂RN subject to the boundary condition u=0 except at one point, in the range q>N−1. We prove that if q?2N−1 such an u is identically zero, while, if N−1<q<2N−1, u inherits a boundary behaviour which either corresponds to a weak singularity, or to a strong singularity. Such singularities are effectively constructed.     

The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.     

An extension of Picard's theorem for meromorphic functions of small hyper-order

A version of the second main theorem of Nevanlinna theory is proved, where the ramification term is replaced by a term depending on a certain composition operator of a meromorphic function of small hyper-order. As a corollary of this result it is shown that if n∈N and three distinct values of a meromorphic function f of hyper-order less than 1/n² have forward invariant pre-images with respect to a fixed branch of the algebraic function τ(z)=z+αn−1z1−1/n+?+α₁z1/n+α₀ with constant coefficients, then f○τ≡f. This is a generalization of Picard's theorem for meromorphic functions of small hyper-order, since the (empty) pre-images of the usual Picard exceptional values are special cases of forward invariant pre-images.     

Strongly simplicial vertices of powers of trees

For a tree T and an integer k?1, it is well known that the kth power T^k of T is strongly chordal and hence has a strong elimination ordering of its vertices. In this note we obtain a complete characterization of strongly simplicial vertices of T^k, thereby characterizing all strong elimination orderings of the vertices of T^k.