Fractional clique decompositions of dense graphs

For each , we show that any graph G with minimum degree at least has a fractional K_r‐decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional K_r‐decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery, and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery, and Osthus, this shows that, for any graph F with chromatic number , and any , any sufficiently large graph G with minimum degree at least has, subject to some further simple necessary divisibility conditions, an (exact) F‐decomposition.     

New and old bounds for standard quadratic optimization: dominance,equivalence and incomparability

A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’s θ function bound for the maximum size of a clique in a graph.      

一种图简化方法及其与遗传算法的混合运用

本文提出了一种适用于图着色问题求解的图简化方法。在这种图简化方法中，图中度小于某个定值的节点的不断被云掉。把这种方法与各种图着色算法结合使用，能提高这些算法的效率，文中分析了应如何设定特定值，并着重叙述了遗传算法的混合运用，最后在给出仿真的结果的同时，进行了指出在本方法同样适用于示最在全连接子图等其它图论问题。     

Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems

In Balas and Niehaus (1996), we have developed a heuristic for generating large cliques in an arbitrary graph, by repeatedly taking two cliques and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time through bipartite matching in the complement of the subgraph. Aggarwal, Orlin and Tai (1997) recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover operation. Inspired by their approach, we examine variations of each element of the genetic algorithm—selection, population replacement and mutation—and develop a steady-state genetic algorithm that performs better than its competitors on most problems.     

A finding maximal clique algorithm for predicting loop of protein structure

In this paper we equate the problem of predicting the loop 3D structure in the comparative modeling to a problem of finding the maximal clique with the best weight. Each possible conformation of a residue in a loop sequence is represented as a node in a graph. Edges are then drawn between pairs of nodes that are consistent with each other. Edge and nodes are weighted according to some fixed criteria. Once the entire graph is constructed, all the maximal sets of cliques are found using an algorithm of artificial neural network models. The cliques with the best weights represent the optimal conformation of the region of loop sequence.     

Pseudo‐random properties of self‐complementary symmetric graphs

There are some results in the literature showing that Paley graphs behave in many ways like random graphs G(n, 1/2). In this paper, we extend these results to the other family of self‐complementary symmetric graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 310–316, 2004     

On the Laplacian Eigenvalues of Signed Graphs

A signed graph is a graph with a sign attached to each edge. This article extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the largest Laplacian eigenvalue of a signed graph is investigated, which generalizes the corresponding results on the largest Laplacian eigenvalue of a graph.     

关于图的团符号控制数

引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想.     

The structure of (theta,pyramid, 1-wheel, 3-wheel)-free graphs

In this paper, we study the class of graphs defined by excluding the following structures as induced subgraphs: theta, pyramid, 1-wheel, and 3-wheel. We describe the structure of graphs in , and we give a polynomial-time recognition algorithm for this class. We also prove that -free graphs in are 4-colorable. We remark that includes the class of chordal graphs, as well as the class of line graphs of triangle-free graphs.