Fault-tolerant panconnectivity of augmented cubes

The augmented cube AQ _n is a variation of the hypercube Q _n . This paper considers the panconnectivity of AQ _n (n ⩾ 3) with at most 2n−5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQ _n , there exist fault-free uv-paths of every length from d + 2 to 2 ⁿ − f − 1, where f is the number of faulty vertices in AQ _n . The proof is based on an inductive construction.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

On radial stochastic Loewner evolution in multiply connected domains

We discuss the extension of radial SLE to multiply connected planar domains. First, we extend Loewner's theory of slit mappings to multiply connected domains by establishing the radial Komatu-Loewner equation, and show that a simple curve from the boundary to the bulk is encoded by a motion on moduli space and a motion on the boundary of the domain. Then, we show that the vector-field describing the motion of the moduli is Lipschitz. We explain why this implies that “consistent,” conformally invariant random simple curves are described by multidimensional diffusions, where one component is a motion on the boundary, and the other component is a motion on moduli space. We argue what the exact form of this diffusion is (up to a single real parameter κ) in order to model boundaries of percolation clusters. Finally, we show that this moduli diffusion leads to random non-self-crossing curves satisfying the locality property if and only if κ=6.     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Quasi‐convexly dense and suitable sets in the arc component of a compact group

Let G be an abelian topological group. The symbol $\widehat{G}Let G be an abelian topological group. The symbol $\widehat{G}$ denotes the group of all continuous characters $\chi :G\rightarrow {\mathbb T}$ endowed with the compact open topology. A subset E of G is said to be qc‐dense in G provided that χ(E)?φ([? 1/4, 1/4]) holds only for the trivial character $\chi \in \widehat{G}$, where $\varphi : {\mathbb R}\rightarrow {\mathbb T}={\mathbb R}/{\mathbb Z}$ is the canonical homomorphism. A super‐sequence is a non‐empty compact Hausdorff space S with at most one non‐isolated point (to which S converges). We prove that an infinite compact abelian group G is connected if and only if its arc component G_a contains a super‐sequence converging to 0 that is qc‐dense in G. This gives as a corollary a recent theorem of Außenhofer: For a connected locally compact abelian group G, the restriction homomorphism $r:\widehat{G}\rightarrow \widehat{G}_a$ defined by $r(\chi )=\chi \upharpoonright _{G_a}$ for $\chi \in \widehat{G}$, is a topological isomorphism. We show that an infinite compact group G is connected if and only if its arc component G_a contains a super‐sequence converging to the identity that is qc‐dense in G and generates a dense subgroup of G. We also offer a short alternative proof of the result of Hofmann and Morris on the existence of suitable sets of minimal size in the arc component of a compact connected group.     

On Constantive Simple and Order-Primal Algebras

A finite algebra is said to be order-primal if its clone of all term operations is the set of all operations defined on A which preserve a given partial order ≤ on A. In this paper we study algebraic properties of order-primal algebras for connected ordered sets (A; ≤). Such order-primal algebras are constantive, simple and have no non-identical automorphisms. We show that in this case cannot have only unary fundamental operations or only one at least binary fundamental operation. We prove several properties of the varieties and the quasi-varieties generated by constantive and simple algebras and apply these properties to order-primal algebras. Further, we use the properties of order-primal algebras to formulate new primality criteria for finite algebras.* Research supported by the Hungarian research grant No. TO34137 and by the János Bolyai grant.** Research supported by the Thailand Research Fund.     

Connectedness in Metric Frames

A new metric diameter for a locally connected metric frame is constructed which is finer than the original one. Amongst other results, this construction allows a proof that the category of uniformly locally connected metric frames and uniform frame maps is reflective in the category of locally connected metric frames and uniform frame maps. Mathematics Subject Classification (2000) 54A05.     

KdV-Burgers方程的级数解

给出ＫｄＶ－Ｂｕｒｇｅｒｓ方程的有界行波解的精确级数解,采用Ａｄｏｍｉａｎ算子分解法分别求行二个区域ζ〈０和ζ〉０的级数解,然后利用对接连续条件构成整体级数解。所得级数解能精确满足对接连续条件,并由此得到确定级数的系数递推公式,无需解非红性高阶代数方程组。与某些精确解及其它方法比较,计算简捷具在对接点处是收剑的。对某些非线性波动现象的研究,可作为计算和分析的数学依据。     

图论在网络出版传播中的应用

利用图论理论研究了网络连通度与广播时间的关系问题 ,获得了网络单信息广播时间的一个界和最少时间广播网的几个充分条件 ,并建立了一个有效的广播方案 .     

图的双控制的一些新结果

图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果.