有向图中几类支撑树数目的计算公式

将W.T.Tultte提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般的情况,并给出了有向图中具有不同特点的支撑树数目的计算公式。     

On the Entropy of Spanning Trees on a Large Triangular Lattice

The double integral representing the entropy S_tri of spanning trees on a large triangular lattice is evaluated using two different methods, one algebraic and one graphical. Both methods lead to the same result

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

图的生成树, 基本圈与Betti亏数

G为图且T是G的一棵生成树. 记号ξ(G, T)表示G＼E(T)中边数为奇数的连通分支个数. 文献［2］称ξ(G)=min[DD(X]T[DD)]ξ(G, T)为图G的Betti亏数, 这里min取遍G的所有生成树T. 由文献［2］知, 确定一个图G的最大亏格主要确定这个图的Betii亏数ξ(G).该文研究与Betti亏数有关的图的特征结构, 得到了关于图的最大亏格的若干结果.     

随机无穷点集上欧几里德最小扩张树的自包含性

本文证明好的欧氏空间无穷点集上最小扩张树的自包含性．应用上述性质,以及AlexanderK．S．[1]中有关二维Poisson连续渗流的结果,我们给出二维情形AldousD．和SteeleJ．M．[2]之猜想的一个新证明,区别于AlexanderK．S．[3]对上述猜想的排除法证明,我们直接证明它,显然,我们的证明更简单．对Poisson连续渗流,得到其二维临界值相对于Poisson最小扩张树的一个刻画;最后我们给出上述临界值相对于点渗流临界值的一个上下界估计。     

Some p-Ranks Related to Orthogonal Spaces

We determine the p-rank of the incidence matrix of hyperplanes of PG(n, p ^e) and points of a nondegenerate quadric. This yields new bounds for ovoids and the size of caps in finite orthogonal spaces. In particular, we show the nonexistence of ovoids in and . We also give slightly weaker bounds for more general finite classical polar spaces. Another application is the determination of certain explicit bases for the code of PG(2, p) using secants, or tangents and passants, of a nondegenerate conic.     

Some Maximal Operators Related to Families of Singular Integral Operators

In this paper, we shall study L^p-boundedness of two kinds of maximal operators related to some families of singular integrals.     

点删除下的图的$A_\alpha$特征值的交错性

设$G$为具有顶点集$V$, 边集$E$的简单图, 本文给出了图$G$与其子图$G-U$的$A_\alpha$特征值的交错不等式, 其中$U\subset V$. 作为应用, 我们利用该交错不等式导出了一些关于图的独立数, 点覆盖数, 哈密尔顿性及支撑数的$A_\alpha$ 谱条件.     

图的度序列不等式

用代数的方法证明了有关图度序列的几个不等式，并且得到了其相应的极图。     

Some remarks on almost l-groups

The divisibility group of every Bézout domain is an abelian l-group. Conversely, Jaffard, Kaplansky, and Ohm proved that each abelian l-group can be obtained in this way, which generalizes Krull’s theorem for abelian linearly ordered groups. Dumitrescu, Lequain, Mott, and Zafrullah [3] proved that an integral domain is almost GCD if and only if its divisibility group is an almost l-group. Then they asked whether the Krull-Jaffard-Kaplansky-Ohm theorem on l-groups can be extended to the framework of almost l-groups, and asked under what conditions an almost l-group is lattice-ordered [3, Questions 1 and 2]. This note answers the two questions. Received: 29 April 2008     

Renewal Theory on the Affine Group of an Oriented Tree

The affine group of a tree is the group of the isometries of a homogeneous tree that fix an end of its boundary. Consider a probability measure on this group and the associated random walk. The main goal of this paper is to determine the accumulation points of the potential kernel

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Number of Components in the Complement to a Level Surface of a Partially Parabolic Polynomial

Mathematical Notes -     

Controller design to optimize a composite performance measure

This paper studies a mixed objective problem of minimizing a composite measure of thel ₁, ₂, andl -norms together with thel -norm of the step response of the closed loop. This performance index can be used to generate Pareto-optimal solutions with respect to the individual measures. The problem is analyzed for discrete-time, single-input single-output (SISO), linear time-invariant systems. It is shown via Lagrange duality theory that the problem can be reduced to a convex optimization problem with a priori known dimension. In addition, continuity of the unique optimal solution with respect to changes in the coefficients of the linear combination that defines the performance measure is estabilished.This research was supported by the National Science Foundation under Grants No. ECS-92-04309, ECS-92-16690 and ECS-93-08481.     

Review of Some Functionals of Compound Poisson Processes and Related Stopping Times

The paper reviews recent results of D. Perry, W. Stadje and S. Zacks, on functionals of stopping times and the associated compound Poisson process with lower and upper linear boundaries. In particular, formulae of these functionals are explicitly developed for the total expected discounted cost of discarded service in an M/G/1 queue with restricted accessibility; for the expected total discounted waiting cost in an M/G/1 restricted queue; for the shortage, holding and clearing costs in an inventory system with continuous input; for the risk in sequential estimation and for the transform of the busy period when the upper boundary is random.      

Sub-Laplacians of Holomorphic L-type on Rank One AN-Groups and Related Solvable Groups

Consider a right-invariant sub-Laplacian L on an exponential solvable Lie group G, endowed with a left-invariant Haar measure. Depending on the structure of G and possibly also that of L, L may admit differentiable L^p-functional calculi, or may be of holomorphic L^p-type for a given p≠2, as recent studies of specific classes of groups G and sub-Laplacians L have revealed. By “holomorphic L^p-type” we mean that every L^p-spectral multiplier for L is necessarily holomorphic in a complex neighborhood of some point in the L²-spectrum of L. This can only arise if the group algebra L¹(G) is non-symmetric. In this article we prove that, for large classes of exponential groups, including all rank one AN-groups, a certain Lie algebraic condition, which characterizes the non-symmetry of L¹(G) [37], also suffices for L to be of holomorphic L¹-type. Moreover, if this condition, which was first introduced by J. Boidol [6] in a different context, holds for generic points in the dual * of the Lie algebra of G, then L is of holomorphic L^p-type for every p≠2. Besides the non-symmetry of L¹(G), also the closedness of coadjoint orbits plays a crucial role. We also discuss an example of a higher rank AN-group. This example and our results in the rank one case suggest that sub-Laplacians on exponential Lie groups may be of holomorphic L¹-type if and only if there exists a closed coadjoint orbit Ω * such that the points of Ω satisfy Boidol's condition. In the course of the proof of our main results, whose principal strategy is similar as in [8], we develop various tools which may be of independent interest and largely apply to more general Lie groups. Some of them are certainly known as “folklore” results. For instance, we study subelliptic estimates on representation spaces, the relation between spectral multipliers and unitary representations, and develop some “holomorphic” and “continuous” perturbation theory for images of sub-Laplacians under “smoothly varying” families of irreducible unitary representations.     

Distinguished extensions of a lattice-ordered group

Any lattice-ordered group (l-group for short) is essentially extended by its lexicographic product with a totally ordered group. That is, anl-homomorphism (i.e., a group and lattice homomorphism) on the extension which is injective on thel-group must be injective on the extension as well. Thus nol-group has a maximal essential extension in the categoryIGp ofl-groups withl-homomorphisms. However, anl-group is a distributive lattice, and so has a maximal essential extension in the categoryD of distributive lattices with lattice homomorphisms. Adistinguished extension of onel-group by another is one which is essential inD. We characterize such extensions, and show that everyl-groupG has a maximal distinguished extensionE(G) which is unique up to anl-isomorphism overG.E(G) contains most other known completions in whichG is order dense, and has mostl-group completeness properties as a result. Finally, we show that ifG is projectable then E(G) is the -completion of the projectable hull ofG.Presented by M. Henriksen.     

Some comments on a paper onk-HNBUE life distributions

Summary In a recent paper by A. P. Basu and N. Ebrahimi (1984, Ann. Inst. Statist. Math., A, 36, 87–100) a new class of life distributions calledk-HNBUE (with dualk-HNWUE) is introduced. Closure properties and bounds on the moments and on the survival function to ak-HNBUE (k-HNWUE) life distribution are presented. However, some of the results presented are incorrect. This research was supported by Swedish Natural Science Research Council Post Doctoral Fellowship F-PD 1564-100.     

Some <Emphasis Type="Italic">L</Emphasis>-Function of a Regular Covering of a Graph

Let ₁:KH, ₂:HG and ₂₁:KG be three finite regular coverings of graphs, and let be a representation of the covering transformation group of ₁. We show that the (Bartholdi type) L-function of G associated to the representation of the covering transformation group of ₂₁ induced from is equal to that of H associated to by means of ordinary voltage assignments.Acknowledgments. We would like to thank the referee for many valuable comments and suggestions. This is partially supported by Grant-in-Aid for Science Research (C).Final version received: February 16, 2004