Compact linearization for binary quadratic problems

We show that a well-known linearization technique initially proposed for quadratic assignment problems can be generalized to a broader class of quadratic 0–1 mixed-integer problems subject to assignment constraints. The resulting linearized formulation is more compact and tighter than that obtained with a more usual linearization technique. We discuss the application of the compact linearization to three classes of problems in the literature, among which the graph partitioning problem.      

Construction d'un ensemble d-dominant sur un graphe en utilisant un critère donnéConstruction of a d-dominating set on a graph by using a given criterion

d-dominating sets in graphs are very important in system and network engineering. Their constructions is thus an important research topic. An heuristic which forms such sets by using a given criterion is proposed. We simplify the heuristic presented elsewhere. We extend it and prove the correctness of the extended heuristic. This heuristic has the advantage of being distributed and scalable. To cite this article: A. Delye de Clauzade de Mazieux et al., C. R. Mecanique 334 (2006).     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

图的最小完整度

主要研究了图的完整度,并给出若干关于完整度的结果. 对于所有的顶点数和边数都给定的连通图类,如何确定该图类中完整度最小的图. 同时研究了对于顶点数和完整度都给定的连通图类,如何确定该图类中边数最多的图的问题. 这些结果为图的最小完整度的优化设计提供了理论和方法.     

图的可定向嵌入的标根可数性

给定一族图G,可定向曲面上存在多少个以其中某个图为基础图的标根地图？采用图的自同构群对图在可定向曲面上的嵌入集合进行分类，该文解决了这个问题，同时得到了求解计数函数f^r(M)的一种新的方法。     

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

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

Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids

The chromatic polynomial P_G(q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (−∞,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z_G(q,v). The proofs are quite simple, and employ deletion–contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27.     

On quartic half-arc-transitive metacirculants

Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1, n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ ^m has at least one fixed vertex. A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In this article quartic half-arc-transitive metacirculants are explored and their connection to the so called tightly attached quartic half-arc-transitive graphs is explored. It is shown that there are three essentially different possibilities for a quartic half-arc-transitive metacirculant which is not tightly attached to exist. These graphs are extensively studied and some infinite families of such graphs are constructed. Both authors were supported in part by “ARRS – Agencija za znanost Republike Slovenije”, program no. P1-0285.     

A Priestley Sum of Finite Trees is Acyclic

We show that the Priestley sum of finite trees contains no cyclic finite poset. The first author would like to express his thanks for support from project LN 1M0021620808 of the Ministry of Education of the Czech Republic. The second author would like to express his thanks for support from project 1M0021620808 of the Ministry of Education of the Czech Republic, from the NSERC of Canada and from a PROF grant from the University of Denver. The third author would like to express his thanks for the support from the NSERC of Canada and for partial support from the project 1M0021620808 of the Ministry of Education of the Czech Republic.     

书本图Bm的协调和相继标号

本文给出了书本图Ｂ２ｍ的ｍ种不同的相继标号和Ｂ４ｍ＋１的ｍ种不同的相继标号。因而，书本图Ｂｍ是相继图的充分条件为：ｍ＞１且ｍ≠（３ｍｏｄ４）。这一条件也是书本图Ｂｍ是协调图的充要条件。