Strong cliques in vertex-transitive graphs

A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique $C$ in a vertex-transitive graph $\mathrm{\Gamma }$ is strong if and only if $\text{◂=▸}\text{◂⋅▸}\mid C\mid \mid I\mid =\mid V\left(\mathrm{\Gamma }\right)\mid$ for every maximal independent set $I$ of $\mathrm{\Gamma }$. On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable.     

Generation of Primary Input Blocking Pattern for Power Minimization during Scan Testing

In this paper we propose a new approach to generate a primary input blocking pattern for applying to the primary inputs during shift cycle such that the switching activity occurred in the combinational part of the circuit under test can be suppressed as much as possible. The primary input blocking technique suppresses transitions of gates in the combinational part during scan by assigning controlling values to one of the gates' inputs. However, simultaneously assigning controlling values to the gates may result in conflicts in the setting of binary values on the primary inputs. Instead of the heuristics based on fanout in other approaches, we use the impact function which is based on transition density to determine the priorities of the gates to be blocked. Experiments performed on the ISCAS 89 benchmark circuits show that the proposed approach can always produce better results than the existing approaches.

带冲突关系装箱问题的启发式求解算法

现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。     

A large class of solutions for the instationary Navier–Stokes system

We investigate very weak solutions to the instationary Navier–Stokes system being contained in where is a bounded domain and . The chosen space of data is small enough to guarantee uniqueness of solutions and existence in case of small data or short time intervals. On the other hand, the data space is large enough that every vector field in is a very weak solution for appropriate data. The solutions and the data depend continuously on each other.      

Modeling Evolution of Weighted Clique Networks

We propose a weighted clique network evolution model, which expands continuously by the addition of a new clique (maximal complete sub-graph) at each time step. And the cliques in the network overlap with each other. The structural expansion of the weighted clique network is combined with the edges' weight and vertices' strengths dynamical evolution. The model is based on a weight-driven dynamics and a weights' enhancement mechanism combining with the network growth. We study the network properties, which include the distribution of vertices' strength and the distribution of edges' weight, and find that both the distributions follow the scale-free distribution. At the same time, we also find that the relationship between strength and degree of a vertex are linear correlation during the growth of the network. On the basis of mean-field theory, we study the weighted network model and prove that both vertices' strength and edges' weight of this model follow the scale-free distribution. And we exploit an algorithm to forecast the network dynamics, which can be used to reckon the distributions and the corresponding scaling exponents. Furthermore, we observe that mean-field based theoretic results are
consistent with the statistical data of the model, which denotes the theoretical result in this paper is effective.     

Robust common visual pattern discovery using graph matching

Discovering common visual patterns (CVPs) between two images is a difficult and time-consuming task, due to the photometric and geometric transformations. The state-of-the-art methods for CVPs discovery are either computationally expensive or have complicated constraints. In this paper, we formulate CVPs discovery as a graph matching problem, depending on pairwise geometric compatibility between feature correspondences. To efficiently find all CVPs, we propose a novel framework which consists of three components: Preliminary Initialization Optimization (PIO), Guided Expansion (GE) and Post Agglomerative Combination (PAC). PIO gets the initial CVPs and reduces the search space of CVPs discovery, based on the internal homogeneity of CVPs. Then, GE anchors on the initializations and gradually explores them, to find more and more correct correspondences. Finally, to reduce false and miss detection, PAC refines the discovery result in an agglomerative way. Experiments and applications conducted on benchmark datasets demonstrate the effectiveness and efficiency of our method.     

Chaos control and synchronization of the Φ<Superscript>6</Superscript>-Van der Pol system driven by external and parametric excitations

The dynamical behavior of the Φ⁶-Van der Pol system subjected to both external and parametric excitation is investigated. The effect of parametric excitation amplitude on the routes to chaos is studied by numerical analysis. It is found that the probability of chaos happening increases along with the parametric excitation amplitude increases while the external excitation amplitude fixed. Based on the invariance principle of differential equations, the system is lead to desirable periodic orbit or chaotic state (synchronization) with different control techniques. Numerical simulations are provided to validate the proposed method.     

There exists no (15,5,4) RBIBD

An (n, M, d)_q code is a q‐ary code of length n, cardinality M, and minimum distance d. We show that there exists no (15,5,4) resolvable balanced incomplete block design (RBIBD) by showing that there exists no (equidistant) (14,15,10)₃ code. This is accomplished by an exhaustive computer search using an orderly algorithm combined with a maximum clique algorithm. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 227–232, 2001     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.