A class of upper-embeddable graphs

In this paper, we prove the following result: Every graph obtained by connecting (with any number of edges) two vertex-disjoint upper-embeddable graphs graphs with even Betti number is upper-embeddable.     

A class of dimension-skipping graphs

Forn≧6 there exists a graphG with dimG=n, dimG*≧n+2, whereG* isG with a certain edge added.     

On h-convexity

We introduce a class of h-convex functions which generalize convex, s-convex, Godunova-Levin functions and P-functions. Namely, the h-convex function is defined as a non-negative function which satisfies f(αx+(1−α)y)?h(α)f(x)+h(1−α)f(y), where h is a non-negative function, α∈(0,1) and x,y∈J. Some properties of h-convex functions are discussed. Also, the Schur-type inequality is given.     

A class of Hamiltonian regular graphs

In this paper, we show that n ? 4 and if G is a 2-connected graph with 2n or 2n?1 vertices which is regular of degree n?2, then G is Hamiltonian if and only if G is not the Petersen graph.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

A class of planar four-colorable graphs

A sufficient condition is given for a planar graph to be 4-colorable. This condition is in terms of the sums of the degrees of a subset of the vertex set of the graph.     

A class of weakly perfect graphs

A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

Homogeneity and h-homogeneity

The relations between zero-dimensional homogeneous spaces and h-homogeneous ones are investigated. We suggest an indication of h  -homogeneity for a homogeneous zero-dimensional paracompact space and its modification for a topological group. We describe some cases when the product X×Y$X\times Y$ is an h-homogeneous space provided X is h-homogeneous and Y is homogeneous.     

h-Vectors of Gorenstein polytopes

We show that the Ehrhart h-vector of an integer Gorenstein polytope with a regular unimodular triangulation satisfies McMullen's g-theorem; in particular, it is unimodal. This result generalizes a recent theorem of Athanasiadis (conjectured by Stanley) for compressed polytopes. It is derived from a more general theorem on Gorenstein affine normal monoids M: one can factor K[M] (K a field) by a “long” regular sequence in such a way that the quotient is still a normal affine monoid algebra. This technique reduces all questions about the Ehrhart h-vector of P to the Ehrhart h-vector of a Gorenstein polytope Q with exactly one interior lattice point, provided each lattice point in a multiple cP, c∈N, can be written as the sum of c lattice points in P. (Up to a translation, the polytope Q belongs to the class of reflexive polytopes considered in connection with mirror symmetry.) If P has a regular unimodular triangulation, then it follows readily that the Ehrhart h-vector of P coincides with the combinatorial h-vector of the boundary complex of a simplicial polytope, and the g-theorem applies.     

Varieties of algebras arising from K-perfect m-cycle systems

A class of algebras forms a variety if it is characterised by a collection of identities. There is a well-known method, often called the standard construction, which gives rise to algebras from m-cycle systems. It is known that the algebras arising from {1}-perfect m-cycle systems form a variety for m∈{3,5} only, and that the algebras arising from {1,2}-perfect m-cycle systems form a variety for m∈{3,5,7} only. Here we give, for any set K of positive integers, necessary and sufficient conditions under which the algebras arising from K-perfect m-cycle systems form a variety.     

A class of threshold and domishold graphs: equistable and equidominating graphs

A threshold graph (respectively domishold graph) is a graph for which the independent sets (respectively the dominating sets) can be characterized by the 0, 1-solutions of a linear Inequality (see [1] and [3]).We define here the graphs for which the maximal independent sets (respectively the minimal dominating sets) are characterized by the 0, 1-solutions of a linear equation. Such graphs are said to be equistable (respectively equldominating).We characterize (by their architectural structure and by forbidden induced subgraphs) threshold graphs and domishold graphs which are equistable or equidominating.A larger class of equistable graphs is also presented.     

Thin bases of order h

A subset is called a basis of order h if every positive integer can be represented as a sum of h members of A. Thin bases of order h will be constructed in this paper, for each h?2, where the value of is smaller than that of thin bases known so far. In the most important case h=2 it is shown that for the considered class of bases (which generalizes an ansatz of Stöhr) the result is best possible up to an ε>0.     

A new class of antimagic Cartesian product graphs

An antimagic labeling of a finite undirected simple graph with m edges and n vertices is a bijection from the set of edges to the integers 1,…,m such that all n-vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel [N. Hartsfield, G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, pp. 108-109, Revised version, 1994] conjectured that every simple connected graph, except K₂, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In particular, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference COCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671-679], all Cartesian products of two or more regular graphs of positive degree can be proved to be antimagic.     

The h-Laplace and q-Laplace transforms

Starting with a general definition of the Laplace transform on arbitrary time scales, we specify the particular concepts of the h-Laplace and q-Laplace transforms. The convolution and inversion problems for these transforms are considered in some detail.     

Coxeter cones and their h-vectors

Coxeter cones are formed by intersecting the nonnegative sides of a collection of root hyperplanes in some root system. They are shellable subcomplexes of the Coxeter complex, and their h-vectors record the distribution of descents among their chambers. We identify a natural class of “graded” Coxeter cones with the property that their h-vectors are symmetric and unimodal, thereby generalizing recent theorems of Reiner-Welker and Brändén about the Eulerian polynomials of graded partially ordered sets.     

A class of planar well-covered graphs with girth four

A well-covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1-well-covered graph was introduced by Staples in her 1975 dissertation: a well-covered graph G is 1-well-covered if and only if G - v is also well covered for every point v in G. Except for K₂ and C₅, every 1-well-covered graph contains triangles or 4-cycles. We show that all planar 1-well-covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.