𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

✍ Scribed by C. Delorme; S. Poljak

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
683 KB
Volume
111
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Delorme, C. and S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Mathematics 111 (1993) 145-156.

The authors earlier introduced a number q(C), which gives a well-computable upper bound on the maximum bipartite subgraph of a graph or, more generally, on the maximum cut of a weighted graph. In this paper we study the performance of this bound on a large variety of examples from the graph theory. We also present an alternative definition of v(C) using a graph operation of vertex-splitting.

Finally, we present the results of some preliminary computational experiments on randomly generated graphs.

πŸ“œ SIMILAR VOLUMES

The max clique problem in classes of str
The max clique problem in classes of string-graphs
✍ M. Middendorf; F. Pfeiffer πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 378 KB

Middendorf, M., F. Pfeiffer, The max clique problem in classes of string-graphs, Discrete Mathematics 108 (1992) 365-372. A string-graph is an intersection graph of a set of curves in the plane. Investigating the complexity of the max clique problem for some classes of string-graphs we obtain NPcomp

An upper bound on the size of the larges
An upper bound on the size of the largest cliques in a graph
✍ Alain Billionnet πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 194 KB πŸ‘ 1 views

## Abstract We produce in this paper an upper bound for the number of vertices existing in a clique of maximum cardinal. The proof is based in particular on the existence of a maximum cardinal clique that contains no vertex __x__ such that the neighborhood of __x__ is contained in the neighborhood