Partition into cliques for cubic graphs: Planar case, complexity and approximation

Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V₁,V₂,…,V_k such that the subgraph induced by each part V_i is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs.     

Static Theory for Planar Ferromagnets and Antiferromagnets

Here we generalize the “BBH”-asymptotic analysis to a simplified mathematical model for the planar ferromagnets and antiferromagnets. To develop such a static theory is a necessary step for a rigorous mathematical justification of dynamical laws for the magnetic vortices formally derived in [1] and [2]. Received March 15, 2001, Accepted May 16, 2001     

粗糙集理论在属性约简及知识分类中的应用

本针对不完备信息系统属性约简的两种定义，证明了两的等价性。在此基础上结合粗糙集理论提出了相似矩阵、相似区间的概念，并将其应用于不完备信息系统知识分类的问题中。     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

平面上线性变换的层次

线性变换在线性代数教学中占有重要的地位.借助齐次坐标描述平面上线性变换的矩阵结构和几何特性,分析平面线性变换包含的层次关系.加深学生对线性变换直观理解.     

A Family of Partition Identities Proved Combinatorially

We present three infinite families of partitions that, for corresponding parameters, are equinumerous. This generalizes an identity proved by the first author (Pacific Journal of Mathematics, 77(1) (1978)) and two identities proved by the second and third authors (Relatório Técnico 08/99 IMECC-UNICAMP, 1999).     

用独立圈对图的一个划分

图G包含4k个点,k≥2,如果σ_2(G)≥4k,则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

A Double Bounded Version of Schur's Partition Theorem

Dedicated to the memory of Paul Erdős Schur's partition theorem states that the number of partitions of n into distinct parts (mod 3) equals the number of partitions of n into parts which differ by 3, where the inequality is strict if a part is a multiple of 3. We establish a double bounded refined version of this theorem by imposing one bound on the parts (mod 3) and another on the parts (mod 3), and by keeping track of the number of parts in each of the residue classes (mod 3). Despite the long history of Schur's theorem, our result is new, and extends earlier work of Andrews, Alladi-Gordon and Bressoud. We give combinatorial and q-theoretic proofs of our result. The special case L=M leads to a representation of the generating function of the underlying partitions in terms of the q-trinomial coefficients extending a similar previous representation of Andrews. Received November 18, 1999 Research of the first author supported in part by NSF Grant DMS-0088975.     

Partition of unity and density: A counterexample

By providing a counterexample we show that there exists a shift-invariant spaceS generated by a piecewise linear function such that the union of the corresponding scaled spacesS ^h (h>0) is dense inC ₀(R ²) butS does not contain a stable and locally supported partition of unity. This settles a question raised by C. de Boor and R. DeVore a decade ago.     

平面图书式嵌入综述

图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域,有广泛的应用价值.图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交.其研究的一个重要参数是页数(满足条件所需的最小页数),该问题是NP-困难的.本文主要综述平面图书式嵌入问题的相关研究.     

Partition numbers

We continue [21] and study partition numbers of partial orderings which are related to (ω)/fin. In particular, we investigate P_f, be the suborder of ((ω)/fin)^ω containing only filtered elements, the Mathias partial order M, and (ω), (ω)^ω the lattice of (infinite) partitions of ω, respectively. We show that Solomon's inequality holds for M and that it consistently fails for P_f. We show that the partition number of (ω) is C. We also show that consistently the distributivity number of (ω)^ω is smaller than the distributivity number of (ω)/fin. We also investigate partitions of a Polish space into closed sets. We show that such a partition either is countable or has size at least D, where D is the dominating number. We also show that the existence of a dominating family of size ₁ does not imply that a Polish space can be partitioned into ₁ many closed sets.     

A New Partition Identity Coming from Complex Dynamics

We present a new identity involving compositions (i.e., ordered partitions of natural numbers). The formula has its origin in complex dynamical systems and appears when counting, in the polynomial family periodic critical orbits with equivalent itineraries. We give two different proofs of the identity; one following the original approach in dynamics and another with purely combinatorial methods. Received October 1, 2004     

Planar Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization,Part 1: Theory

In this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization framework of the companion paper (Part 2, Ref. 2). Here, preliminary numerical results are reported.This work was supported by MIUR, FIRB Research Program on Large-Scale Nonlinear Optimization, Rome, ItalyThe author acknowledges Luigi Grippo and Stefano Lucidi, who contributed considerably to the elaboration of this paper. The exchange of experiences with Massimo Roma was a constant help in the investigation. The author expresses his gratitude to the Associate Editor and the referees for suggestions and corrections.