Resistance characterizations of equiarboreal graphs

A weighted (unweighted) graph $G$ is called equiarboreal if the sum of weights (the number) of spanning trees containing a given edge in $G$ is independent of the choice of edge. In this paper, we give some resistance characterizations of equiarboreal weighted and unweighted graphs, and obtain the necessary and sufficient conditions for $k$-subdivision graphs, iterated double graphs, line graphs of regular graphs and duals of planar graphs to be equiarboreal. Applying these results, we obtain new infinite families of equiarboreal graphs, including iterated double graphs of 1-walk-regular graphs, line graphs of triangle-free 2-walk-regular graphs, and duals of equiarboreal planar graphs.     

胜利断块油藏细分注水技术界限研究

老油田进入特高含水期后,剩余油分布更加零散,各种地质因素也因长期注水开发而发生了一定的改变.此时稳油控水难度进一步加大,为了进一步挖掘剩余油,控制含水上升速度、减缓产量递减,必须对注水井采取进一步的细分调整.基于水湿油藏注水井注水层段吸水效果,从注入水受力分析入手,运用达西定律推导出了水驱油藏水驱油全过程中的单位体积注入水沿竖直、地层两个方向运移的渗流速度公式,明晰了水驱油藏注水层段不同开发阶段砂岩吸水机理.研究结果表明,水驱油藏细分注水效果与岩石绝对渗透率、水相相对渗透率、注入水黏度、水动力压力梯度、注水井启动压力梯度、含水饱和度、地层倾角、油水密度差等参数有关.结合胜利油田断块油藏地质特征及细分注水工艺要求,制定了一套适合胜利油田不同断块区的细分注水技术政策界限:层段内渗透率变异系数小于0.3,砂岩条带宽度极比小于2.5,且东辛油区断块油藏层段内砂岩厚度小于6m,小层数小于4个;现河油区断块油藏层段内砂岩厚度小于5m,小层数小于5个;临盘油区断块油藏层段内砂岩厚度小于6m,小层数小于6个.矿场试验证实,该细分注水技术政策界限是合理、实用的,其为胜利断块油藏注上水、注够水、注好水,实现多层断块油藏的高效开发提供了技术保障,对类似油藏细分注水技术界限研究具有一定的借鉴意义.     

A visual proof of a result of Knuth on spanning trees of Aztec diamonds in the case of odd order

The even Aztec diamond AD_n is known to have precisely four times more spanning trees than the odd Aztec diamond OD_n—this was conjectured by Stanley and first proved by Knuth. We present a short combinatorial proof of this fact in the case of odd n. Our proof works also for the more general case of odd-by-odd Aztec rectangles.     

Graphs with only caterpillars as spanning trees

A connected graph G is caterpillar-pure if each spanning tree of G is a caterpillar. The caterpillar-pure graphs are fully characterized. Loosely speaking they are strings or necklaces of so-called pearls, except for a number of small exceptional cases. An upper bound for the number of edges in terms of the order is given for caterpillar-pure graphs, and those which attain the upper bound are characterized.     

On the selection of subdivision directions in interval branch-and-bound methods for global optimization

This paper investigates the influence of the interval subdivision selection rule on the convergence of interval branch-and-bound algorithms for global optimization. For the class of rules that allows convergence, we study the effects of the rules on a model algorithm with special list ordering. Four different rules are investigated in theory and in practice. A wide spectrum of test problems is used for numerical tests indicating that there are substantial differences between the rules with respect to the required CPU time, the number of function and derivative evaluations, and the necessary storage space. Two rules can provide considerable improvements in efficiency for our model algorithm.The work has been supported by the Grants OTKA 2879/1991, and MKM 414/1994.     

关于k—覆盖图的一些新结果

本文给出了一个图G是k-覆盖图的若干充分条件．     

Network reinforcement

We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invulnerability of a network. Our algorithm has the same asymptotic complexity as |V| applications of the minimum cut algorithm of Goldberg & Tarjan. Received: April, 2004     

Stationary binary subdivision schemes using radial basis function interpolation

A new family of interpolatory stationary subdivision schemes is introduced by using radial basis function interpolation. This work extends earlier studies on interpolatory stationary subdivision schemes in two aspects. First, it provides a wider class of interpolatory schemes; each 2L-point interpolatory scheme has the freedom of choosing a degree (say, m) of polynomial reproducing. Depending on the combination (2L,m), the proposed scheme suggests different subdivision rules. Second, the scheme turns out to be a 2L-point interpolatory scheme with a tension parameter. The conditions for convergence and smoothness are also studied. Dedicated to Prof. Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 41A05, 41A25, 41A30, 65D10, 65D17. Byung-Gook Lee: This work was done as a part of Information & Communication fundamental Technology Research Program supported by Ministry of the Information & Communication in Republic of Korea. Jungho Yoon: Corresponding author. Supported by the Korea Science and Engineering Foundation grant (KOSEF R06-2002-012-01001).     

树图的1—Hamilton连通性

一阶数≥3的简单连通图叫做1-Hamilton连通的,若对每一对顶点v_1、v_2及任一边v_2v_3(v_1≠v_3),存在连接v_1和v_2,并且经过v_3v_2的Hamilton路.本文中我们证明:连通图的树图或是1-Hamilton连通的,或为一超立方体,或同构于K_2×K_3和W_5之一.     

The reduction of graph families closed under contraction

Let be a family of graphs. Suppose there is a nontrivial graph H such that for any supergraph G of H, G is in if and only if the contraction G/H is in . Examples of such an : graphs with a spanning closed trail; graphs with at least k edge-disjoint spanning trees; and k-edge-connected graphs (k fixed). We give a reduction method using contractions to find when a given graph is in and to study its structure if it is not in . This reduction method generalizes known special cases.