A note on complete subdivisions in digraphs of large outdegree

Mader conjectured that for all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order . In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let be a digraph of order n whose minimum outdegree is at least d. Then contains a subdivision of a complete digraph of order . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008     

Compactly supported (bi)orthogonal wavelets generated by interpolatory refinable functions

This paper provides several constructions of compactly supported wavelets generated by interpolatory refinable functions. It was shown in [7] that there is no real compactly supported orthonormal symmetric dyadic refinable function, except the trivial case; and also shown in [10,18] that there is no compactly supported interpolatory orthonormal dyadic refinable function. Hence, for the dyadic dilation case, compactly supported wavelets generated by interpolatory refinable functions have to be biorthogonal wavelets. The key step to construct the biorthogonal wavelets is to construct a compactly supported dual function for a given interpolatory refinable function. We provide two explicit iterative constructions of such dual functions with desired regularity. When the dilation factors are larger than 3, we provide several examples of compactly supported interpolatory orthonormal symmetric refinable functions from a general method. This leads to several examples of orthogonal symmetric (anti‐symmetric) wavelets generated by interpolatory refinable functions. This revised version was published online in June 2006 with corrections to the Cover Date.     

抛物方程的基于BB型对偶剖分的有限体积元法

本文讨论了抛物方程的基于三角形剖分和BB型对偶剖分的有限体积元法,给出了半离散及全离散有限体积元格式的最佳阶L2和H1误差估计.     

四边形网格的削角细分

提出了一种四边形网格的削角细分方法(Corner-Cuttmg Subdivision Scheme).每细分一次,四边形网格数目增加为原来的两倍,两次细分结果相当于一次二分对偶细分(Binary Dual Subdivision)和一个旋转.细分算法采用线性细分加平滑的形式,具体地讲平滑是采用两次重复平均的方法,因此其生成曲面具有C1连续性.而且由于这种细分方法对网格几何操作简单,所得网格数据量增长相对缓慢,更适合于3D图像重构及网络传输等应用领域..     

曲线设计的几何细分法

分曲线是通过对初始控制多边形进行重复逼近或插值得到的,提出了一种新的构造曲线的逼近型细分法--曲线设计的几何细分法.该方法用折线割角代替传统的直线割角产生新点和新边,得到的曲线具有保凸性、凸包性等与Bézier方法类似的性质,引入了一些参数来控制细分过程,且参数对曲线形状的影响是局部的.另外,本文中的方法可以用来生成圆,这是Bézier方法所不具备的.当参数在一定范围内取值时,用这种方法可以构造出C1连续的逼近曲线.     

一种四边形网格上的Midedge细分格式

提出了一种逼近型细分格式,通过初始网格的边插入边点,再去除初始点、边,连接所插入边点的方式生成新的网格。 该细分格式是对PETERS 等提出的Midedge格式的拓展,其分离因子为1-2,意味着每通过1次细分,便将1个矩形分离成2个。 通过分析对应细分矩阵的性质,证明了此细分格式具有至少C1的连续性这一性质。     

一种新的细分小波及其应用

在图形图像数据传输与数据处理过程中,数据鼍过大是造成不便的主要原因,因此用少量的数据更好地表现图形图像特征是人们追求的目标．图形简化的任务是在保留图形特征的同时删除过多的采样点．简化的中心问题是简化模板的选择,王国谨等人介绍了基于球面多边形逼近的曲面简化技术等方法．用小波技术进行图形简化也是目前图形图像处理过程中的常用方法,如孙延奎等人研究了B样条曲线的多分辨率表示,LounsberyM．等人研究了任意拓扑结构的曲面多分辨分析问题等等．     

On certain spanning subgraphs of embeddings with applications to domination

We prove the existence of certain spanning subgraphs of graphs embedded in the torus and the Klein bottle. Matheson and Tarjan proved that a triangulated disc with n vertices can be dominated by a set of no more than n/3 of its vertices and thus, so can any finite graph which triangulates the plane. We use our existence theorems to prove results closely allied to those of Matheson and Tarjan, but for the torus and the Klein bottle.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

On proper secrets, (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-bases and linear codes

This paper contains three parts where each part triggered and motivated the subsequent one. In the first part (Proper Secrets) we study the Shamir’s “k-out-of-n” threshold secret sharing scheme. In that scheme, the dealer generates a random polynomial of degree k−1 whose free coefficient is the secret and the private shares are point values of that polynomial. We show that the secret may, equivalently, be chosen as any other point value of the polynomial (including the point at infinity), but, on the other hand, setting the secret to be any other linear combination of the polynomial coefficients may result in an imperfect scheme. In the second part ((t, k)-bases) we define, for every pair of integers t and k such that 1 ≤ t ≤ k−1, the concepts of (t, k)-spanning sets, (t, k)-independent sets and (t, k)-bases as generalizations of the usual concepts of spanning sets, independent sets and bases in a finite-dimensional vector space. We study the relations between those notions and derive upper and lower bounds for the size of such sets. In the third part (Linear Codes) we show the relations between those notions and linear codes. Our main notion of a (t, k)-base bridges between two well-known structures: (1, k)-bases are just projective geometries, while (k−1, k)-bases correspond to maximal MDS-codes. We show how the properties of (t, k)-independence and (t, k)-spanning relate to the notions of minimum distance and covering radius of linear codes and how our results regarding the size of such sets relate to known bounds in coding theory. We conclude by comparing between the notions that we introduce here and some well known objects from projective geometry.