On the sum of all distances in chromatic blocks

In this paper all 2-connected k-chromatic graphs of order n with the maximum sum of all distances between their vertices are characterized for every k ≥ 2, thus strengthening a result of J. Plesnik. Moreover, several auxiliary results are proved on chromatic critical graphs and 2-connected graphs.     

On the sum of distances along a circle

The arc distance between two points on a circle is their geodesic distance along the circle. We study the sum of the arc distances determined by n points on a circle, which is a useful measure of the evenness of scales and rhythms in music theory. We characterize the configurations with the maximum sum of arc distances by a balanced condition: for each line that goes through the circle center and touches no point, the numbers of points on each side of the line differ by at most one. When the points are restricted to lattice positions on a circle, we show that Toussaint's snap heuristic finds an optimal configuration. We derive closed-form formulas for the maximum sum of arc distances when the points are either allowed to move continuously on the circle or restricted to lattice positions. We also present a linear-time algorithm for computing the sum of arc distances when the points are presorted by the polar coordinates.     

On the graph of large distances

For a setS of points in the plane, letd ₁>d ₂>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd _k . It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk ². IfS consists of the vertices of a convex polygon and |S|constk ², then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon.     

The competition-common enemy graph of a digraph

The competition graph of a digraph was first defined in 1968 by Cohen in the study of ecosystems. The competition graph essentially relates any two species which have a common prey.In this paper, a competition-common enemy graph of a digraph is defined and studied. As the term suggests, it relates any two species which have a common prey and a common enemy. Results analogous to those found for competition graphs are obtained.     

On the sum of distances betweenn points on a sphere. II

Acta Mathematica Hungarica -     

Realization of a sum of sequences by a sum graph

It is shown that the realizability of the sequences ϕ=(a ₁,…, _a ), ψ=(b ₁,…,b _n ) and ϕ+ψ is a sufficient condition for the realizability of ϕ+ψ by a graph with a ϕ-factor ifb _i ≦1 fori=1,…,n. The condition is not sufficient in general. A necessary and sufficient condition for the realizability of ϕ+ψ by a graph with a ϕ-factor is given for the case that ϕ is realizable by a star and isolated vertices.     

On zero sum Ramsey numbers: Multiple copies of a graph

As a consequence of our main result, a theorem of Schrijver and Seymour that determines the zero sum Ramsey numbers for the family of all r-hypertrees on m edges and a theorem of Bialostocki and Dierker that determines the zero sum Ramsey numbers for r-hypermatchings are combined into a single theorem. Another consequence is the determination of zero sum Ramsey numbers of multiple copies of some small graphs.     

Perfect matchings of a graph associated with a binary de Bruijn digraph

Let B_n be the binary de Bruijn digraph of order n and W the quotient set of the set of vertices of B_n with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that (v,u) is an arc of B_n. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.     

On the exponent of a primitive digraph

We characterize the equality case of the upper bound $\text{γ(D) ? n + s(n ? 2)}$ for the exponent of a primitive digraph in the case s ? 2, where n is the number of the vertices of the digraph D and s is the length of the shortest elementary circuit of D. We also answer a question about the equality case when s = 1. The exponent of an n × n primitive nonnegative matrix A is the same as the exponent of the associated digraph D(A) of A. So every theorem in this paper can be translated into a theorem about nonnegative matrices.     

On the Ferrers dimension of a digraph

The Ferrers dimension of a digraph has been shown to be an extension of the order dimension. By proving a property of (finite) transitive Ferrers digraphs, we give an original proof of this above result and derive Ore's alternative definition of the order dimension. Still, the order dimension is proved to be ‘polynomially equivalent’ to the Ferrers dimension.     

An algorithm for the determination of longest distances in a graph

This paper presents an algorithm for ranking the vertices of a directed graph. Its space and time requirements are bounded byc ₁ n ² +c ₂, wheren is the number of vertices of the graph andc ₁,c ₂ are positive constants which are independent of the size or other properties of the graph.The algorithm can be easily modified to solve the problem of determining longest distances from a vertex to all other vertices in a positive real valued graph with at mostc ₁ n ² +c ₂ elementary operations; the same result holds for shortest distances in negative real valued graphs.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.     

Tight bounds on the chromatic sum of a connected graph

The chromatic sum of a graph is introduced in the dissertation of Ewa Kubicka. It is the smallest possible total among all proper colorings of G using natural numbers. In this article we determine tight bounds on the chromatic sum of a connected graph with e edges.     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.