The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.     

The number of spanning trees in a new lexicographic product of graphs

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.     

A linear programming formulation for an inventory management decision problem with a service constraint

Inventory systems with uncertainty go hand in hand with the determination of a safety stock level. The decision on the safety stock level is based on a performance measure, for example the expected shortage per replenishment period or the probability of a stock-out per replenishment period. The performance measure assumes complete knowledge of the probability distribution during lead time, which might not be available. In case of incomplete information regarding the lead-time distribution of demand, no single figure for the safety stock can de determined in order to satisfy a performance measure. However, an optimisation model may be formulated in order to determine a safety stock level which guarantees the performance measure under the worst case of lead-time demand, of which the distribution is known in an incomplete way. It is shown that this optimisation problem can be formulated as a linear programming problem.     

Multiobjective optimization and multiple constraint handling withevolutionary algorithms. I. A unified formulation

In optimization, multiple objectives and constraints cannot be handled independently of the underlying optimizer. Requirements such as continuity and differentiability of the cost surface add yet another conflicting element to the decision process. While “better” solutions should be rated higher than “worse” ones, the resulting cost landscape must also comply with such requirements. Evolutionary algorithms (EAs), which have found application in many areas not amenable to optimization by other methods, possess many characteristics desirable in a multiobjective optimizer, most notably the concerted handling of multiple candidate solutions. However, EAs are essentially unconstrained search techniques which require the assignment of a scalar measure of quality, or fitness, to such candidate solutions. After reviewing current revolutionary approaches to multiobjective and constrained optimization, the paper proposes that fitness assignment be interpreted as, or at least related to, a multicriterion decision process. A suitable decision making framework based on goals and priorities is subsequently formulated in terms of a relational operator, characterized, and shown to encompass a number of simpler decision strategies. Finally, the ranking of an arbitrary number of candidates is considered. The effect of preference changes on the cost surface seen by an EA is illustrated graphically for a simple problem. The paper concludes with the formulation of a multiobjective genetic algorithm based on the proposed decision strategy. Niche formation techniques are used to promote diversity among preferable candidates, and progressive articulation of preferences is shown to be possible as long as the genetic algorithm can recover from abrupt changes in the cost landscape     

Minimal trees of a given search number

We consider families of all minimal trees of a given search number, which is an invariant in problems of searching in a graph. The problem of enumeration of these families is solved.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 25–31, July–August, 1992.     

Extremal values on the harmonic number of trees

Let G=(V(G), E(G)) be a simple connected graph. The harmonic number of G, denoted by H(G), is defined as the sum of the weights 2/(d(u)+d(v)) of all edges uv of G, where d(u) denotes the degree of a vertex u in G. In this paper, some extremal problems on the harmonic number of trees are studied. The extremal values on the harmonic number of trees with given graphic parameters, such as pendant number, matching number, domination number and diameter, are determined. The corresponding extremal graphs are characterized, respectively.     

A stress-based formulation of the free material design problem with the trace constraint and multiple load conditions

The paper deals with minimization of the weighted sum of compliances related to the load cases applied non-simultaneously. The design variables are all components of the Hooke tensor, subject to the isoperimetric condition bounding the integral of the sum of the Kelvin moduli. This free material design problem is reduced to an equilibrium problem – in two formulations – of an effective body with locking. The stress-based formulation reduces to minimization of an integral of a certain norm of stress fields over the stress fields which equilibrate the given loads. The equivalent displacement-based formulation involves a locking locus defined by using a norm being dual to the previous one. The optimal Hooke tensor is determined by using the stress fields solving the auxiliary locking problem. To make the optimal Hooke tensor positive definite one should consider at least 3 load conditions in the 2D case and not less than 6 load conditions in the 3D case.     

A new formulation of the Hermite criterion

The Routh algorithm is used to generate the parameters of the Hermite criterion, The new formulation is simpler than the original. The relationship among the Hermite, the symmetrical Hurwitz, the Kalman-Bertram, and the Routh criteria is naturally established.     

A limit characterization for the number of spanning trees of graphs

In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G_n} be a sequence of graphs G₀,G₁,G₂,… that belong to a particular class. We consider graphs of the form K_n−G_n that result from the complete graph K_n after removing a set of edges that span G_n. We study the spanning tree behaviour of the sequence {K_n−G_n} when n→∞ and the number of edges of G_n scales according to n. More specifically, we define the spanning tree indicator ({G_n}), a quantity that characterizes the spanning tree behaviour of {K_n−G_n}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).     

A new approach to variable-topology shape design using a constraint on perimeter

This paper introduces a method for variable-topology shape optimization of elastic structures called theperimeter method. An upper-bound constraint on the perimeter of the solid part of the structure ensures a well-posed design problem. The perimeter constraint allows the designer to control the number of holes in the optimal design and to establish their characteristic length scale. Finite element implementations generate practical designs that are convergent with respect to grid refinement. Thus, an arbitrary level of geometric resolution can be achieved, so single-step procedures for topology design and detailed shape design are possible. The perimeter method eliminates the need for relaxation, thereby circumventing many of the complexities and restrictions of other approaches to topology design.     

Improved algorithm for the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. The best previous algorithm for computing the symmetry number for an unrooted unordered tree is due to [P.P. Mitra, M.A.U. Abedin, M.A. Kashem, Algorithms for solving the symmetry number problem on trees, Inform. Process. Lett. 91 (2004) 163-169] and runs in O(n³) time. In this paper we show an improvement on this time complexity by encoding small trees. Our algorithm runs in time O(n³²(loglogn/logn)).     

Algorithms for solving the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. Chin and Yen have presented an algorithm for solving the problem of finding the symmetry number of unrooted unordered trees in time O(n⁴). In this paper we present an improved algorithm for solving the symmetry number problem on trees that runs in time O(n³). We also show that our algorithm needs O(n²logn) time for trees with bounded degrees.     

A new formulation of the hypermatrix Householder-QR decomposition

For the Householder-QR decomposition Brönlund and Johnsen presented hypermatrix formulations for the first time several years ago. In this paper a new formulation is given in terms of unitary Hermitian matrices generalizing the concept of an elementary unitary Hermitian. Thereby the greatest possible analogy to the corresponding classical formulations is obtained.     

A matrix formulation for integrating assembly trees and manufacturing resource planning with capacity constraints

This paper introduces a new matrix-based formulation for assembly trees which facilitates solving the manufacturing resource planning (MRP) problem including resource constraints for a large class of problems. The algorithm seamlessly integrates assembly tree information, capacity requirements, and traditional manufacturing resource planning; the algorithm allows for a large class of capacity limitations, and solves these problems without requiring a manager to iteratively adjust the MRP schedule.     

A new approach to stabilisation of a class of nonlinear systems with an output constraint

ABSTRACT

This paper investigates the problem of state-feedback stabilisation for a class of high-order nonlinear systems with an output constraint. A novel tangent-type barrier Lyapunov function is first developed to cope with the output constraint. Then, by introducing the sign function and incorporating the developed tangent-type barrier Lyapunov function, the celebrated adding a power integrator technique is revamped to systematically design a continuous state feedback stabilising controller that prevents violation of the output constraint during operation. The novelty of this paper is the development of an unified design procedure, which can tackle the stabilisation task of the systems with/without the output constraint simultaneously.     

A complementary formulation for traffic equilibrium problem with a new nonadditive route cost

Improving transportation system is essential for all people in each city since transport plays a very important role.Using mathematical programming approach transport problem is an effective way to improve transportation system.In this paper,the traffic equilibrium problem(TEP)with a general nonadditive route cost function is studied.We formulate the route cost function for each route as a disutility function,which can evaluate route cost function flexibly and analyze the route toll conveniently.Furthermore...     

A new tractable class of constraint satisfaction problems

In this paper we consider constraint satisfaction problems where the set of constraint relations is fixed. Feder and Vardi (1998) identified three families of constraint satisfaction problems containing all known polynomially solvable problems. We introduce a new class of problems called para-primal problems, incomparable with the families identified by Feder and Vardi (1998) and we prove that any constraint problem in this class is decidable in polynomial time. As an application of this result we prove a complete classification for the complexity of constraint satisfaction problems under the assumption that the basis contains all the permutation relations. In the proofs, we make an intensive use of algebraic results from clone theory about the structure of para-primal and homogeneous algebras. AMS subject classification 08A70