Dual properties of subspaces in products of ordinals

Let μ and ν be two ordinals. If X is a subspace of μ×ν, then X is dually scattered of rank?2. If X is a subspace of countable extent of μ×ν, then X is dually discrete.     

Monotone normality and paracompactness

In this paper it is proved that a topological space is necessarily paracompact if it is monotonically normal and any one of the following: screenable, paralindelöf, has a G_δ-diagonal or a quasi-G_δ-diagonal or has a σ-locally-countable base.     

Monotone retractability and retractional skeletons

We prove that a countably compact space is monotonically retractable if and only if it has a full retractional skeleton. In particular, a compact space is monotonically retractable if and only if it is Corson. This gives an answer to a question of R. Rojas-Hernández and V.V. Tkachuk. Further, we apply this result to characterize retractional skeleton using a topology on the space of continuous functions, answering thus a question of the first author and a related question of W. Kubi?.     

Balanced home–away assignments

In recent years several approaches for generating sports league schedules have been proposed. In this paper we consider foundations for a two-stage approach to construct schedules for a single round robin tournament (or the first half series of a double round robin tournament). In the first stage for each game a mode (home or away) has to be determined and in the second stage the games have to be scheduled in their assigned modes. We study a problem of the first stage where balanced home–away assignments have to be constructed such that for each team the numbers of home and away games differ by at most one. After showing that it is easy to construct balanced home–away assignments we propose repairing mechanisms for unbalanced home–away assignments. Then, neighborhoods on the set of balanced home–away assignments are defined which are shown to be connected. Finally, situations with preassignments are studied.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

Shared values and normality

This paper investigates the relationship between the normality and the shared values for a meromorphic function on the unit disc Δ. Based on Marty’s normality criterion and through a detailed analysis of the meromorphic functions, it is shown that if for every f ∈ , f and f ^(k) share a and b on Δ and the zeros of f(z) − a are of multiplicity k ⩾ 3, then is normal on Δ, where is a family of meromorphic functions on the unit disc Δ, and a and b are distinct values. Selected from Journal of East China Normal University (Natural Science), 2003, 4: 12–18. This work was supported by the National Natural Science Foundation of China under grant number 10271122 and by Shanghai City Foundation for selected academic research     

Constructing and classifying neighborhood anti-Sperner graphs

For a simple graph G let N_G(u) be the (open) neighborhood of vertex u∈V(G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v∈V(G)?{u} with N_G(u)⊆N_G(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_H(u)≠N_H(v) when u≠v, for all u and v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69-77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r=0,1,…,6.     

On linear neighborhood assignments and dually discrete spaces

In this note, the concept of a linear neighborhood assignment is introduced. By discussing properties of linear D-spaces, we show that if T is a Suslin tree with FW (or CW) topology, then T is a Lindelöf D-space. We also show that if X is a countably compact space and , where for any linear neighborhood assignment ?n for Xn, there exists a strong DC-like subspace (or a subparacompact C-scattered closed subspace) Dn of Xn, such that for each n∈N, then X is a compact space; Every generalized ordered space is dually discrete. This gives a positive answer to a question of Buzyakova, Tkachuk and Wilson.     

Degree and neighborhood conditions for hamiltonicity of claw-free graphs

For a graph $H$, let ${\sigma }_t\left(H\right)=min\left\{{\Sigma }_{i=1}^t{d}_H\left(v_i\right)\right|\{v_1,v_2,\dots ,v_t\}\text{is an independent set in }H\}$ and let $U_t\left(H\right)=min\left\{\right|{?}_{i=1}^t{N}_H\left(v_i\right)\left|\right|\{v_1,v_2,?,v_t\}\text{is an independent set in }H\}$. We show that for a given number $?$ and given integers $p\ge t>0$, $k\in \{2,3\}$ and $N=N(p,?)$, if $H$ is a $k$-connected claw-free graph of order $n>N$ with $\delta \left(H\right)\ge 3$ and its Ryjác?ek’s closure $cl\left(H\right)=L\left(G\right)$, and if $d_t\left(H\right)\ge t(n+?)∕p$ where $d_t\left(H\right)\in \{{\sigma }_t\left(H\right),U_t\left(H\right)\}$, then either $H$ is Hamiltonian or $G$, the preimage of $L\left(G\right)$, can be contracted to a $k$-edge-connected $K_3$-free graph of order at most $max\{4p?5,2p+1\}$ and without spanning closed trails. As applications, we prove the following for such graphs $H$ of order $n$ with $n$ sufficiently large:(i) If $k=2$, $\delta \left(H\right)\ge 3$, and for a given $t$ ($1\le t\le 4$) $d_t\left(H\right)\ge \frac{tn}{4}$, then either $H$ is Hamiltonian or $cl\left(H\right)=L\left(G\right)$ where $G$ is a graph obtained from $K_{2,3}$ by replacing each of the degree 2 vertices by a $K_{1,s}$ ($s\ge 1$). When $t=4$ and $d_t\left(H\right)={\sigma }_4\left(H\right)$, this proves a conjecture in Frydrych (2001).(ii) If $k=3$, $\delta \left(H\right)\ge 24$, and for a given $t$ ($1\le t\le 10$) $d_t\left(H\right)>\frac{t(n+5)}{10}$, then $H$ is Hamiltonian. These bounds on $d_t\left(H\right)$ in (i) and (ii) are sharp. It unifies and improves several prior results on conditions involved ${\sigma }_t$ and $U_t$ for the hamiltonicity of claw-free graphs. Since the number of graphs of orders at most $max\{4p?5,2p+1\}$ are fixed for given $p$, improvements to (i) or (ii) by increasing the value of $p$ are possible with the help of a computer.     

A fragmentation model with neighborhood interaction

Several models of fragmentation have been studied that suppose random fracture forces. In this article, we did a numerical study on a dynamic model for fragmentation in which the fracture forces are generated by neighboring fragments and are proportional to the size of the common boundary between two fragments. The following assumptions were also considered: the material defects are represented by a random distribution of point flaws; the total mass is conserved; and the iterative fracture of each fragment is randomly stopped by a condition that considers a constant probability and a minimal fragment size. The motivation for this model was to determine under what circumstances a continuous fragmentation model with fracture forces defined by the neighbors’ interaction produces results that are in agreement with the experimental evidence. The main result of this work establishes that the fragment size distribution follows a power-law for fragments of greater area than the minimal fragment size m_fs. The visualizations present complex fracture patterns that resemble real systems.     

Envy-free rights assignments and self-oriented preferences

Very recently a new solution to Sen's “Impossibility of a Paretian liberal” has been suggested where the focus is on the rights assignments per se (Austen-Smith, 1979). It was shown that the concept of fairness, when applied to rights, admits the existence of social decision functions which satisfy Sen's original conditions. Unfortunately this result collapses when individuals have rights over more than one pair of alternatives.In order to obtain possibility results for this more general case the present paper proposes to restrict individuals' preference orderings. It is proved that envy-free collective choice rules exist if individual preferences are self-oriented and if, in addition, people attach primary importance to their own private sphere alternatives. These restrictions are quite severe, but they may be justified if one values the absence of envy in rights allocations very highly.     

An analysis of neighborhood functions on generic solution spaces

The effectiveness of local search algorithms on discrete optimization problems is influenced by the choice of the neighborhood function. A neighborhood function that results in all local minima being global minima is said to have zero L-locals. A polynomially sized neighborhood function with zero L-locals would ensure that at each iteration, a local search algorithm would be able to find an improving solution or conclude that the current solution is a global minimum. This paper presents a recursive relationship for computing the number of neighborhood functions over a generic solution space that results in zero L-locals. Expressions are also given for the number of tree neighborhood functions with zero L-locals. These results provide a first step towards developing expressions that are applicable to discrete optimization problems, as well as providing results that add to the collection of solved graphical enumeration problems.     

关于D-空间

本文研究了用邻域对应定义的空间类.利用构造性的方法,证明了有限多个狭义拟仿紧空间的并是aD-空间及λ-半层空间是D-空间,得到了拓扑空间是aD-空间或D-空间的充分条件,一般化了已有的相应结果.     

Multivariate normality via conditional specification

If X is a k-dimensional random vector, we denote by X_(i) the vector X with coordinate i deleted and by X_(i,j) the vector X with coordinates i and j deleted. If for each i the conditional distribution of X_i given X_(i) = x_(i) is univariate normal for each x_(i) ^K−1 and if for each i, j the conditional distribution of X_i given X_(i,j) = x_(i,j) is univariate normal for each x_(i,j) ^k−2 then it is shown that X has a classical k-variate normal distribution.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

A neighborhood search heuristic for pre-marshalling export containers

In a yard where export containers are piled up, only those on the top are directly accessible to the stacking equipment. As a result, extra rehandles may occur when lifting them up for loading onto ships. One way to improve operational efficiency is to pre-marshal the containers in such an order that it fits the loading sequence. This paper proposes a model to develop a movement plan to improve the layout of containers in a bay. The proposed heuristic consists of a neighborhood search process, an integer programming model, and three minor subroutines. Each of the components plays a different role in the heuristic. Several sets of testing results demonstrate the performance of the heuristic as well as the contributions of the components.     

A heuristic approach for airport gate assignments for stochastic flight delays

To make good flight to gate assignments, not only do all the relevant constraints have to be considered, but stochastic flight delays that occur in actual operations also have to be taken into account. In past research, airport gate assignments and stochastic disturbances have often been handled in the planning and the real-time stages separately, meaning that the interrelationship between these stages, as affected by such delays, has been neglected. In this research, we develop a heuristic approach embedded in a framework designed to help the airport authorities make airport gate assignments that are sensitive to stochastic flight delays. The framework includes three components, a stochastic gate assignment model, a real-time assignment rule, and two penalty adjustment methods. The test results are based on data supplied by a Taiwan international airport, and show that the proposed framework performs better than the current manual assignment process and the traditional deterministic model.