The two-machine open shop problem: To fit or not to fit, that is the question

We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D₁ and D₂, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0,D₁] and [0,D₂], respectively.We formulate four simple conditions on D₁ and D₂, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D₁,D₂) for which there exists a feasible schedule.     

Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

Longest path partitions in generalizations of tournaments

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ₁,λ₂, such that λ₁+λ₂ equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D₁ and D₂, such that the order of a longest path in D_i is at most λ_i, for i=1,2.We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.     

Nagata-like theorems for almost Prüfer v-multiplication domains

Let D be an integral domain and X an indeterminate over D . We show that if S is an almost splitting set of an integral domain D , then D is an APVMD if and only if both DS and DN(S) are APVMDs. We also prove that if {Dα}α∈I is a collection of quotient rings of D such that D=∩α∈IDα has finite character (that is, each nonzero d∈D is a unit in almost all Dα) and each of Dα is an APVMD, then D is an APVMD. Using these results, we give several Nagata-like theorems for APVMDs.     

A characterization of the extensions of symmetric designs

Let D be a quasi-symmetric design with block intersection numbers 0 and y. For any fixed block B of D, let D_B denote the incidence structure whose points are the points of D not in B and whose blocks are the blocks of D disjoint from B. If D is an extension of a symmetric design, Cameron showed that D_B is a design and the parameters of D are exactly one of four types. We prove the converse: If D_B is a design, then D is the extension of a symmetric design.     

Optimal strategies for node selection games on oriented graphs: Skew matrices and symmetric games

In the node selection game Γ_D each of the two players simultaneously selects a node from the oriented graph D. If there is an arc between the selected nodes, then there is a payoff from the “dominated” player to the “dominating” player. We investigate the set of optimal strategies for the players in the node selection game Γ_D. We point out that a classical theorem from game theory relates the dimension of the polytope of optimal strategies for Γ_D to the nullity of certain skew submatrix of the payoff matrix for Γ_D. We show that if D is bipartite (with at least two nodes in each partite set), then an optimal strategy for the node selection game Γ_D is never unique. Our work also implies that if D is a tournament, then there is a unique optimal strategy for each player, a result obtained by Fisher and Ryan [Optimal strategies for a generalized “scissors, paper, and stone” game, Amer. Math. Monthly 99 (1992) 935–942] and independently by Laffond, Laslier, and Le Breton [The bipartisan set of a tournament game, Games Econom. Behav. 5 (1993) 182–201].     

Paths partition with prescribed beginnings in digraphs: A Chvátal-Erd?s condition approach

A digraph D verifies the Chvátal-Erd?s conditions if α(D)?κ(D), where α(D) is the stability number of D and κ(D) is its vertex-connectivity. Related to the Gallai-Milgram Theorem (see Gallai and Milgram [Verallgemeinerung eines Graphentheorischen Satzes von Redei, Acta Sci. Math. 21 (1960) 181-186]), we raise in this context the following conjecture. For every set of α=α(D) vertices {x₁,…,x_α}, there exists a vertex-partition of D into directed paths {P₁,…,P_α} such that P_i begins at x_i for all i. The case α(D)=2 of the conjecture is proved.     

The k-Dominating Graph

Given a graph G, the k-dominating graph of G, D _k (G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D _k (G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D _k (G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of D _k (G). In this paper we give conditions that ensure D _k (G) is connected.     

Weak and strong extensions of ordinary differential operators

Let A be a second order differential operator with positive leading term defined on an interval J of R. In this paper we study conditions for the equality D₀(A) = D₁(A) to hold. Here D₀(A) and D₁(A) are the domains of the minimal and maximal extensions of A respectively. Under the general assumption that $\text{A(1)}\text{and}\text{A}{}^1\text{(1)}$ are bounded above it is proven that under certain conditions D₀(A) = D₁(A) if functions which are constant near the boundaries of J are in $\text{D}{}_0\text{(A) ∩ D}{}_0\text{(A}{}^1\text{)}$ whenever they are in $\text{D}{}_1\text{(A) ∩ D}{}_1\text{(A}{}^1\text{)}$. In particular if A is formally selfadjoint and 1 ?D₁(A) then D₁(A) = D₀(A) if and only if 1 ?D₀(A). When the measure of J is infinite at both ends D₀(A) is always equal to D₁(A). This fact is used to show that the leading term of A as well as its terminal coefficient can be chosen arbitrarily (although not independently of one another) in such a way that the equality D₀ = D₁ holds.     

Normal family and the sequence of omitted functions

Let {fn} be a sequence of meromorphic functions on a plane domain D, whose zeros and poles have multiplicity at least 3. Let {hn} be a sequence of meromorphic functions on D, whose poles are multiple, such that {hn} converges locally uniformly in the spherical metric to a function h which is meromorphic and zero-free on D.If fn≠hn, then {fn} is normal on D.     

The n-lie property of the Jacobian as a condition for complete integrability

We prove that an associative commutative algebra U with derivations D ₁, ..., D _n ε DerU is an n-Lie algebra with respect to the n-multiplication D ₁ ^ ? ^ D _n if the system {D ₁, ..., D _n } is in involution. In the case of pairwise commuting derivations this fact was established by V. T. Filippov. One more formulation of the Frobenius condition for complete integrability is obtained in terms of n-Lie multiplications. A differential system {D ₁, ..., D _n } of rank n on a manifold M ^m is in involution if and only if the space of smooth functions on M is an n-Lie algebra with respect to the Jacobian Det(D _i u _j ).     

Kernels in quasi-transitive digraphs

Let D be a digraph, V(D) and A(D) will denote the sets of vertices and arcs of D, respectively.A kernel N of D is an independent set of vertices such that for every w∈V(D)-N there exists an arc from w to N. A digraph is called quasi-transitive when (u,v)∈A(D) and (v,w)∈A(D) implies (u,w)∈A(D) or (w,u)∈A(D). This concept was introduced by Ghouilá-Houri [Caractérisation des graphes non orientés dont on peut orienter les arrêtes de maniere à obtenir le graphe d’ un relation d’ordre, C.R. Acad. Sci. Paris 254 (1962) 1370-1371] and has been studied by several authors. In this paper the following result is proved: Let D be a digraph. Suppose D=D₁∪D₂ where D_i is a quasi-transitive digraph which contains no asymmetrical infinite outward path (in D_i) for i∈{1,2}; and that every directed cycle of length 3 contained in D has at least two symmetrical arcs, then D has a kernel. All the conditions for the theorem are tight.     

Minimal n-fach zusammenhängende Digraphen

For a minimally n-connected digraph D, the subgraph spanned by the edges (x, y) with outdegree of x and indegree of y exceeding n is denoted by D₀. It is proved that D₀ corresponds to a forest. This implies that in a finite, minimally n-connected digraph D, the number of vertices of outdegree n is at least n and that the number of vertices of outdegree or indegree equal to n grows linearly in |D|. For almost every integer m, the maximum number of edges in a minimally n-connected digraph of order m is determined and the extremal digraphs are characterized.     

Hamiltonicity of 6-connected line graphs

Let G be a graph and let D₆(G)={v∈V(G)|d_G(v)=6}. In this paper we prove that: (i) If G is a 6-connected claw-free graph and if |D₆(G)|≤74 or G[D₆(G)] contains at most 8 vertex disjoint K₄’s, then G is Hamiltonian; (ii) If G is a 6-connected line graph and if |D₆(G)|≤54 or G[D₆(G)] contains at most 5 vertex disjoint K₄’s, then G is Hamilton-connected.     

Remarks on Distance Distributions for Graphs Modeling Computer Networks

The Wiener polynomial of a graph G is a generating function for the distance distribution dd(G) = (D₁, D₂,…,D_t), where D_i is the number of unordered pairs of distinct vertices at distance i from one another and t is the diameter of G. We use the Wiener polynomial and several related generating functions to obtain generating functions for distance distributions of graphs that model certain large classes of computer networks. These provide a straightforward means of computing distance and timing statistics when designing new networks or enlarging existing networks.     

Ranking the vertices of an r-partite paired comparison digraph

A paired comparison digraph D is a weighted digraph in which the sum of the weights of arcs, if any, joining two vertices is exactly one. A one-to-one mapping from V(D) onto {1,2…,|V(D)|} is called a ranking of D, and a ranking α of D is optimal if the backward length of α is minimum. We say that D is r-partite if V(D) can be partitioned into V₁∪…∪V_r so that every arc of D joins a vertex of V_i to a vertex of V_i, where i ≠ j. We show that we can easily obtain all the optimal rankings of a certain r-partite paired comparison digraph.     

Minimum 2-tuple dominating set of permutation graphs

For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ _×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D ₂ is said to be minimal if there does not exist any D′?D ₂ such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D ₂, denoted by γ _×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n ²) time.     

New discoveries of domination between traffic matrices

In this paper the definition of domination is generalized to the case that the elements of the traffic matrices may have negative values. It is proved that D₃ dominates D₃ + λ(D₂ ? D₁) for any λ ? 0 if D₁ dominates D₂. Let U(D) be the set of all the traffic matrices that are dominated by the traffic matrix D. It is shown that U(D_∞) and U(D_∈) are isomorphic. Besides, similar results are obtained on multi-commodity flow problems. Furthermore, the results are the generalized to integral flows.     

Inner and outer radial density functions in singly-excited 1snl states of the He atom

The one-electron radial density function D(r) has recently been found to be separable into inner D_<(r) and outer D_>(r) radial density functions. The inner D_<(r) and outer D_>(r) densities are studied for 28 singly-excited 1snl singlet and triplet states (0≤l<n≤5) of the He atom at a correlated level. Theoretical structures of D_<(r) and D_>(r) are discussed within the Hartree-Fock framework. Comparison of correlated D_<(r) and D_>(r) with hydrogenic radial densities based on the modal characteristics and Carbó’s similarity index clarifies that D_<(r) represents the 1s density of the helium cation, while D_>(r) extracts the nl density of the hydrogen atom from D(r). The radial separation 〈|r₁−r₂|〉, which constitutes a lower bound to the standard deviation of D(r), is shown to be estimated from the location of the outermost maximum of D_>(r).     

Distance distributions for graphs modeling computer networks

The Wiener polynomial of a graph G is a generating function for the distance distribution dd(G)=(D₁,D₂,…,D_t), where D_i is the number of unordered pairs of distinct vertices at distance i from one another and t is the diameter of G. We use the Wiener polynomial and several related generating functions to obtain generating functions for distance distributions of unweighted and weighted graphs that model certain large classes of computer networks. These provide a straightforward means of computing distance and timing statistics when designing new networks or enlarging existing networks.