The maximum clique and the signless Laplacian eigenvalues
Lower and upper bounds are obtained for the clique number and the independence number , in terms of the eigenvalues of the signless Laplacian matrix of a graph .
The maximum distinguishing number of a group.
The maximum genus, matchings and the cycle space of a graph
In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .
The maximum multiplicity and the two largest multiplicities of eigenvalues in a Hermitian matrix whose graph is a tree
The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, M1, was understood fully (froma combinatorial perspective) by C.R. Johnson, A. Leal-Duarte (Linear Algebra and Multilinear Algebra 46 (1999) 139-144). Among the possible multiplicity lists for the eigenvalues of Hermitian matrices whose graph is a tree, we focus upon M2, the maximum value of the sum of the two largest multiplicities when the largest multiplicity is M1. Upper and lower bounds are given for M2. Using a combinatorial...
The maximum number of odd submatrices in -matrices.
The maximum number of edges in a three-dimensional grid-drawing.
The maximum number of perfect matchings in graphs with a given degree sequence.
The maximum of the maximum rectilinear crossing numbers of -regular graphs of order .
The maximum order of finite groups of outer automorphisms of free groups.
The maximum path theorem and extreme points of James space
The maximum size of a partial spread in is .
The Median Problem on k-Partite Graphs
In a connected graph G, the status of a vertex is the sum of the distances of that vertex to each of the other vertices in G. The subgraph induced by the vertices of minimum (maximum) status in G is called the median (anti-median) of G. The median problem of graphs is closely related to the optimization problems involving the placement of network servers, the core of the entire networks. Bipartite graphs play a significant role in designing very large interconnection networks. In this paper, we...
The Merris index of a graph.
The middle graph of a hypergraph
The minimal perimeter for confined deformable bubbles of equal area.
The minimum number of monotone subsequences.
The minimum rank problem over finite fields.
The minimum spectral radius of graphs with a given clique number.
The Minimum Spectral Radius of Signless Laplacian of Graphs with a Given Clique Number
In this paper we observe that the minimal signless Laplacian spectral radius is obtained uniquely at the kite graph PKn−ω,ω among all connected graphs with n vertices and clique number ω. In addition, we show that the spectral radius μ of PKm,ω (m ≥ 1) satisfies [...] More precisely, for m > 1, μ satisfies the equation [...] where [...] and [...] . At last the spectral radius μ(PK∞,ω) of the infinite graph PK∞,ω is also discussed.
The min-max supergraph