On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.     

Iterated clique graphs with increasing diameters

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(Kⁱ(G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been described by Peyrat, Rall, and Slater and independently by Balakrishnan and Paulraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i ≥ 5 remained open. In the present article, we prove their conjecture. For each positive integer i, we describe a family of graphs G such that diam(Kⁱ(G)) = diam(G) + i. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 147–154, 1998     

Degree sequence conditions for equal edge‐connectivity and minimum degree,depending on the clique number

Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the known results in this area. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 234–245, 2003     

Self-clique graphs and matrix permutations

The clique graph of a graph is the intersection graph of its (maximal) cliques. A graph is self-clique when it is isomorphic with its clique graph, and is clique-Helly when its cliques satisfy the Helly property. We prove that a graph is clique-Helly and self-clique if and only if it admits a quasi-symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex-clique duality. We describe new classes of self-clique and 2-self-clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). We prove that deciding whether a (0,1)-matrix admits a symmetric (quasi-symmetric) permuted matrix is graph (hypergraph) isomorphism complete. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 178–192, 2003     

On Standard Quadratic Optimization Problems

A standard quadratic optimization problem (QP) consists of finding (global) maximizers of a quadratic form over the standard simplex. Standard QPs arise quite naturally in copositivity-based procedures which enable an escape from local solutions. Furthermore, several important applications yield optimization problems which can be cast into a standard QP in a straightforward way. As an example, a new continuous reformulation of the maximum weight clique problem in undirected graphs is presented which considerably improves previous attacks both as numerical stability and interpretation of the results are concerned. Apparently also for the first time, an equivalence between standard QPs and QPs on the positive orthant is established. Also, a recently presented global optimization procedure (GENF - genetical engineering via negative fitness) is shortly reviewed.     

The combinatorics of pivoting for the maximum weight clique

In this paper we prove the equivalence between a pivoting-based heuristic (PBH) for the maximum weight clique problem and a combinatorial greedy heuristic. It is also proved that PBH always returns a local solution although this is not always guaranteed for Lemke's method, on which PBH is based.     

Graph relations,clique divergence and surface triangulations

This work has two aims: first, we introduce a powerful technique for proving clique divergence when the graph satisfies a certain symmetry condition. Second, we prove that each closed surface admits a clique divergent triangulation. By definition, a graph is clique divergent if the orders of its iterated clique graphs tend to infinity, and the clique graph of a graph is the intersection graph of its maximal complete subgraphs. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments

We present an exact and efficient branch-and-bound algorithm MCR for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular type of graph. It employs approximate coloring to obtain an upper bound on the size of a maximum clique along with an improved appropriate sorting of vertices. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that in general, our algorithm decidedly outperforms other existing algorithms. The algorithm has been successfully applied to interesting problems in bioinformatics, image processing, design of quantum circuits, and design of DNA and RNA sequences for biomolecular computation.     

A study of ACO capabilities for solving the maximum clique problem

This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal cliques through the repeated addition of vertices into partial cliques, and uses “pheromone trails” as a greedy heuristic to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are laid and exploited, i.e., on edges or on vertices of the graph. We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.