Graphs with given number of cut vertices and extremal Merrifield-Simmons index

The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by G(n,k) the set of connected graphs with n vertices and k cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield-Simmons index, respectively, among all graphs in G(n,k) for all possible k values.     

A sufficient condition for boundedness of tolerance graphs

Golumbic, Monma, and Trotter showed that every tolerance graph for which no vertex neighborhood is contained in another vertex neighborhood is a bounded tolerance graph. We strengthen this result by weakening the neighborhood condition. In this way, more tolerance graphs can be recognized as bounded. Our argument relies on a variation of the concept of “assertive vertices”.     

多面体截面和小覆盖的闭子流形

设π:M~n→P~n是P~n上的小覆盖,S是P~n的任意一个n-1维截面.给出了π~(-1)(S)是n-1维闭子流形(或者两个相互同胚n-1维闭子流形的不交并),以及π~(-1)(S)是n-1维伪流形的充要条件.     

Alliance free and alliance cover sets

A defensive (offensive) k-alliance in Γ = (V,E) is a set S ⊆ V such that every υ in S (in the boundary of S) has at least k more neighbors in S than it has in V / S. A set X ⊆ V is defensive (offensive) k-alliance free, if for all defensive (offensive) k-alliance S, S/X ≠ ∅, i.e., X does not contain any defensive (offensive) k-alliance as a subset. A set Y ⊆ V is a defensive (offensive) k-alliance cover, if for all defensive (offensive) k-alliance S, S ∩ Y ≠ ∅, i.e., Y contains at least one vertex from each defensive (offensive) k-alliance of Γ. In this paper we show several mathematical properties of defensive (offensive) k-alliance free sets and defensive (offensive) k-alliance cover sets, including tight bounds on their cardinality.     

A Construction of Sequentially Cohen-Macaulay Graphs

For every simple graph G,a class of multiple clique cluster-whiskered graphs Geπm is introduced,and it is shown that all such graphs are vertex decomposable;thus,the independence simplicial complex IndGeπm is sequentially Cohen-Macaulay.The properties of the graphs Geπm and Gπ constructed by Cook and Nagel are studied,including the enumeration of facets of the complex Ind Gπ and the calculation of Betti numbers of the cover ideal Ic(Geπ").We also prove that the complex △ =IndH is strongly shellable and pure for either a Boolean graph H =Bn or the full clique-whiskered graph H =Gw of G,which is obtained by adding a whisker to each vertex of G.This implies that both the facet ideal I(△) and the cover ideal Ic(H) have linear quotients.     

Multipliers,covers, and stem extensions for Lie superalgebras

Suppose that the underlying field is of characteristic different from 2 and 3. We first prove that the so-called stem deformations of a free presentation of a finite-dimensional Lie superalgebra L exhaust all the maximal stem extensions of L; up to equivalence of extensions. Then we prove that multipliers and covers always exist for a Lie superalgebra and they are unique up to superalgebra isomorphisms. Finally, we describe the multipliers, covers, and maximal stem extensions of Heisenberg superalgebras and model filiform Lie superalgebras.     

On the state of strength‐three covering arrays

A covering array of size N, strength t, degree k, and order υ is a k × N array on υ symbols in which every t × N subarray contains every possible t × 1 column at least once. We present explicit constructions, constructive upper bounds on the size of various covering arrays, and compare our results with those of a commercial product. Applications of covering arrays include software testing, drug screening, and data compression. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 217–238, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10002     

组合数学与数论间的一些交叉问题初探

我们证明了有限域上的一类方程组解的个数与图的顶点着色数有密切关系，而这又对许多着色问题的产生了许多应用。另外，我们也用图论的一些技巧解决了数论中一些问题。     

On the reversed sub-martingale property of empirical discrepancies in arbitrary sample spaces

The empirical discrepancy is defined as a supremum over a class of functions of a collection of centered sample averages. For uncountable classes the discrepancy need not be measurable, and distributional assertions can become dependent on the structure of the underlying probability space. This paper shows that one such assertion—the reversed sub-martingale property—is valid when interpreted in terms of measurable cover functions for the canonical model, but that it can fail in other constructions of the underlying model.     

Examples of Calabi–Yau Threefolds as Covers of Almost-Fano Threefolds

We give a method for producing examples of Calabi–Yau threefolds as covers of degree d ≤ 8 of almost-Fano threefolds, computing explicitely their Euler– Poincaré characteristic. Such a method generalizes the well-knownclassical construction of Calabi–Yau threefolds as double covers of the projective space branched along octic surfaces.