Maximizing signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity

In this paper, we characterize the graphs with maximum signless Laplacian or adjacency spectral radius among all graphs with fixed order and given vertex or edge connectivity. We also discuss the minimum signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity. Consequently we give an upper bound of signless Laplacian or adjacency spectral radius of graphs in terms of connectivity. In addition we confirm a conjecture of Aouchiche and Hansen involving adjacency spectral radius and connectivity.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

Maximizing Free Entropy

Maximization problems are solved for Voiculescu's free entropy of probability measures supported in R, R+, and [-1, 1], respectively, under constraint of the pth moment for any p > 0 and implications of these results for multivariate free entropy are discussed in the setting of noncommutative random variables. Similar extremum problems are treated for probability measures on C and Tunder certain constraints. The elliptic law and a distribution found earlier in quantum physics are encountered. These results are in the setting of potential theory and can be viewed independently from Voiculescu's work. The machinery of weighted potentials is exploited.     

Maximizing edge-ratio is NP-complete

Given a graph G and a bipartition of its vertices, the edge-ratio is the minimum for both classes so defined of their number of internal edges divided by their number of cut edges. We prove that maximizing edge-ratio is NP-complete.     

Maximizing the descent statistic

For a subsetS, let the descent statistic (S) be the number of permutations that have descent setS. We study inequalities between the descent statistics of subsets. Each subset (and its complement) is encoded by a list containing the lengths of the runs. We define two preorders that compare different lists based on the descent statistic. Using these preorders, we obtain a complete order on lists of the form (k ⁱ ,P,k ^n–i , whereP is a palindrome, whose first entry is larger thank. We prove a conjecture due to Gessel, which determines the list that maximizes the descent statistic, among lists of a given size and given length. We also have a generalization of the boustrophedon transform of Millar, Sloane and Young.     

Invariant Hamming graphs in infinite quasi-median graphs

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph.     

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

Hamilton cycles in random graphs and directed graphs

We prove that almost every digraph D_{2–in, 2–out} is Hamiltonian. As a corollary we obtain also that almost every graph G_4–out is Hamiltonian. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 369–401, 2000     

Maximizing system lifetime in wireless sensor networks

One of the most critical issues in wireless sensor networks is represented by the limited availability of energy on network nodes; thus, making good use of energy is necessary to increase network lifetime. In this paper, we define network lifetime as the time spanning from the instant when the network starts functioning properly, i.e., satisfying the target level of coverage of the area of interest, until the same level of coverage cannot be guaranteed any more due to lack of energy in sensors. To maximize system lifetime, we propose to exploit sensor spatial redundancy by defining subsets of sensors active in different time periods, to allow sensors to save energy when inactive. Two approaches are presented to maximize network lifetime: the first one, based on column generation, must run in a centralized way, whereas the second one is based on a heuristic algorithm aiming at a distributed implementation. To assess their performance and provide guidance to network design, the two approaches are compared by varying several network parameters. The column generation based approach typically yields better solutions, but it may be difficult to implement in practice. Nevertheless it provides both a good benchmark against which heuristics may be compared and a modeling framework which can be extended to deal with additional features, such as reliability.     

Maximizing throughput in finite-source parallel queue systems

Motivated by the dispatching of trucks to shovels in surface mines, we study optimal routing in a Markovian finite-source, multi-server queueing system with heterogeneous servers, each with a separate queue. We formulate the problem of routing customers to servers to maximize the system throughput as a Markov Decision Process. When the servers are homogeneous, we demonstrate that the Shortest Queue policy is optimal, and when the servers are heterogeneous, we partially characterize the optimal policy and present a near-optimal and simple-to-implement policy. We use the model to illustrate the substantial benefits of pooling, by comparing it to the permanent assignment of customers to servers.     

Maximizing Flexibility in Air Force Weapon Procurement

Defence policy-making has to be set against an uncertain—indeed unpredictable—future. Given this uncertainty surrounding future conflict, air forces play an important part because of their inherent flexibility to undertake a variety of roles. This paper describes the assistance given to the Air Staff in deciding what mix of air-delivered weapons should be stockpiled to provide the RAF with this flexibility, subject to budgetary and other constraints. It is a simple application of linear programming with an unusual objective function. A number of alternative approaches are reviewed, and the rather pragmatic way in which various decisions regarding the conduct of the study were made is discussed.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.