It is well known that each tree metric M has a unique realization as a tree, and that this realization minimizes the total length of the edges among all other realizations of M. We extend this result to the class of symmetric matrices M with zero diagonal, positive entries, and such that mij + mkl ≤ max{mik + mjl, mil + mjk} for all distinct i,j,k,l.
It is proved in this paper that special generalized ultrametric and special matrices are, in a sense, extremal matrices in the boundary of the set of generalized ultrametric and matrices, respectively. Moreover, we present a new class of inverse -matrices which generalizes the class of matrices.
Let F be a forest of order n. It is well known that if F 6= Sn, a star of order n, then there exists an embedding of F into its complement F. In this note we consider a problem concerning the uniqueness of such an embedding.
Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an embedding G into its complement [G̅]. In this note, we consider a problem concerning the uniqueness of such an embedding.
For a graph H, we compare two notions of uniquely H-colourable graphs, where one is defined via automorphisms, the second by vertex partitions. We prove that the two notions of uniquely H-colourable are not identical for all H, and we give a condition for when they are identical. The condition is related to the first homomorphism theorem from algebra.
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
The paper studies the bus-journey graphs in the case when they are piecewise expanding and contracting (if described by fathers-sons relations starting with the greatest independent set of nodes). This approach can make it possible to solve the minimization problem of the total service time of crews.
A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers of all abstract genealogical trees with exactly n+1 nodes and k leaves is found by means of enumeration of code words. For each n, the form a partition of the n-th Catalan numer Cₙ, that means .
Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
We study an uncapacitated facility location model where customers are served by facilities of level one, then each level one facility that is opened must be assigned to an opened facility of level two. We identify a polynomially solvable case, and study some valid inequalities and facets of the associated polytope.