Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Extremal graphs for the sum of the two largest signless Laplacian eigenvalues

Let G be a simple graph on n vertices and e(G) edges. Consider the signless Laplacian, Q(G) = D + A, where A is the adjacency matrix and D is the diagonal matrix of the vertices degree of G. Let q1(G) and q2(G) be the first and the second largest eigenvalues of Q(G), respectively, and denote by S+ n the star graph with an additional edge. It is proved that inequality q1(G)+q2(G) e(G)+3 is tighter for the graph S+ n among all firefly graphs and also tighter to S+ n than to the graphs Kk _ Kn−k recently presented by Ashraf, Omidi and Tayfeh-Rezaie. Also, it is conjectured that S+ n minimizes f(G) = e(G) − q1(G) − q2(G) among all graphs G on n vertices.