Motzkin树上的保护点的计数问题

In this paper,we enumerate the set of Motzkin trees with n edges according to the number of leaves,the number of vertices adjacent to a leaf,the number of protected nodes,the number of(protected)branch nodes,and the number of(protected)lonely nodes.Explicit formulae as well as generating functions are obtained.We also find that,as n goes to infinity,the proportion of protected branch nodes and protected lonely nodes among all vertices of Motzkin trees with n edges approaches 4/27 and 2/9.     

Ordering Trees with Nearly Perfect Matchings by Algebraic Connectivity

Let T2k＋1 be the set of trees on 2k＋1 vertices with nearly perfect matchings and α（T） be the algebraic connectivity of a tree T. The authors determine the largest twelve values of the algebraic connectivity of the trees in T2k＋1. Specifically, 10 trees T2,T3,... ,T11 and two classes of trees T（1） and T（12） in T2k＋1 are introduced. It is shown in this paper that for each tree T^′1,T^″1∈T（1）and T^′12,T^″12∈T（12） and each i,j with 2≤i〈j≤11,α（T^′1）=α（T^″1）〉α（Tj）〉α（T^′12）=α（T^″12）.It is also shown that for each tree T with T∈T2k＋1／（T（1）∪{T2,T3,…,T11}∪T（12））,α（T^′12）〉α（T）.     

Stochastic Enumeration Method for Counting Trees

The problem of estimating the size of a backtrack tree is an important but hard problem in the computational sciences. An efficient solution of this problem can have a major impact on the hierarchy of complexity classes. The first randomized procedure, which repeatedly generates random paths through the tree, was introduced by Knuth. Unfortunately, as was noted by Knuth and a few other researchers, the estimator can introduce a large variance and become ineffective in the sense that it underestimates the cost of the tree. Recently, a new sequential algorithm called Stochastic Enumeration (SE) method was proposed by Rubinstein et al. The authors showed numerically that this simple algorithm can be very efficient for handling different counting problems, such as counting the number of satisfiability assignments and enumerating the number of perfect matchings in bipartite graphs. In this paper we introduce a rigorous analysis of SE and show that it results in significant variance reduction as compared to Knuth’s estimator. Moreover, we establish that for almost all random trees the SE algorithm is a fully polynomial time randomized approximation scheme (FPRAS) for the estimation of the overall tree size.     

Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs

Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least (1-e)( *20c nr)(1-\varepsilon)\left( {\begin{array}{*{20}c} n\\ r\\ \end{array}}\right) edges, the 2-shadow has a monochromatic matching covering all but at most o(n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1))n in every (r – 1)-coloring of the edges of K^(r)_n{K^{(r)}_{n}}, the complete r-uniform hypergraph on n vertices.     

A Note on Matchings and Spanning Trees with Bounded Degrees

If M is a perfect matching in a k-connected graph G with independence number \(\alpha \le 1 + {3 \over 2}k\) , then M can be extended to a spanning tree of G with maximum degree at most three.     

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of vertices. The complexity of finding a spanning tree of minimum stabbing number is one of the original 30 questions on “The Open Problems Project” list of outstanding problems in computational geometry by Demaine, Mitchell, and O’Rourke. We show -hardness of stabbing problems by means of a general proof technique. For matchings, this also implies a nontrivial lower bound on the approximability. On the positive side, we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. From the corresponding linear programming relaxation we obtain polynomial-time lower bounds and show that there always is an optimal fractional solution that contains an edge of at least constant weight. We conjecture that the resulting iterated rounding scheme constitutes a constant-factor approximation algorithm. An extended abstract appeared in the Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms [11]. M.E. Lübbecke visits to Kingston and Stony Brook were supported by a DFG travel grant. H. Meijer partially supported by NSERC while visiting Braunschweig in 2002.     

完全偶图的星因子计数

图G的一个星因于是G的一个支撑子图，其中每一个分支是一个星图．本文研究完全偶图Km,n的星因子计数，给出了Km,x存在由K个分支构成的星因子的充要条件，进而给出了Km,n星因子计数的公式．     

Laplacian Spectral Radius and Maximum Degree of Trees with Perfect Matchings

Let μ(T) and Δ(T) denote the Laplacian spectral radius and the maximum degree of a tree T, respectively. Denote by ${\mathcal{T}_{2m}}$ the set of trees with perfect matchings on 2m vertices. In this paper, we show that for any ${T_1, T_2\in\mathcal{T}_{2m}}$ , if Δ(T ₁) > Δ(T ₂) and ${\Delta(T_1)\geq \lceil\frac{m}{2}\rceil+2}$ , then μ(T ₁) > μ(T ₂). By using this result, the first 20th largest trees in ${\mathcal{T}_{2m}}$ according to their Laplacian spectral radius are ordered. We also characterize the tree which alone minimizes (resp., maximizes) the Laplacian spectral radius among all the trees in ${\mathcal{T}_{2m}}$ with an arbitrary fixed maximum degree c (resp., when ${c \geq \lceil\frac{m}{2}\rceil + 1}$ ).     

$$q$$ -Universal characters and an extension of the lattice $$q$$ -universal characters

Theoretical and Mathematical Physics - We consider two different subjects: the $$q$$ -deformed universal characters $$widetilde S_{[lambda,mu]}(t,hat t;x,hat x)$$ and the $$q$$ -deformed...     

Complete Enumeration of Small Realizable Oriented Matroids

Enumeration of all combinatorial types of point configurations and polytopes is a fundamental problem in combinatorial geometry. Although many studies have been done, most of them are for 2-dimensional and non-degenerate cases. Finschi and Fukuda (Discrete Comput Geom 27:117–136, 2002) published the first database of oriented matroids including degenerate (i.e., non-uniform) ones and of higher ranks. In this paper, we investigate algorithmic ways to classify them in terms of realizability, although the underlying decision problem of realizability checking is NP-hard. As an application, we determine all possible combinatorial types (including degenerate ones) of 3-dimensional configurations of 8 points, 2-dimensional configurations of 9 points, and 5-dimensional configurations of 9 points. We also determine all possible combinatorial types of 5-polytopes with nine vertices.     

二部图生成树的新的计数公式(英文)

设G =(V ,U ,E)是一个连通的二部图 ,其中｜V｜=m ,｜U｜=n .令M (G)表示G的关联矩阵 ,Jk×s 表示元素全为 1的k ×s矩阵 ,R =M (G)M (G)′ , Jm n =Jm -Jm×n-Jn×m Jn,t(G)表示G中生成树的个数 .在本文中我们不用对G的边定向而获得了下面的主要结论 :t(G) =(m n) -2 det( Jm n R) .     

Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

Colorful Isomorphic Spanning Trees in Complete Graphs

Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n − 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n − 1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two.Received July 24, 2001     

完全二叉树的量词消去

量词消去法已经成为计算机科学和代数模型论中最有力的研究工具之一.本 文针对完全二叉树理论所独有的特性,给出了它的基本公式集,然后利用分布公式及 有限覆盖证明了完全二叉树的理论可以量词消去.     

The Euclidean Distortion of Complete Binary Trees

   Abstract. Bourgain [1] showed that every embedding of the complete binary tree of depth n into l ₂ has metric distortion ≥

完全偶图的[1,2]因子计数

讨论了完全偶图存在[1,2]因子的充分必要条件，并给出了[1,2]因子的计数法。