Three general multivariate semi-Pareto distributions and their characterizations

Three general multivariate semi-Pareto distributions are developed in this paper. First one—GMP^(k)(III) has univariate Pareto (III) marginals, it is characterized by the minimum of two independent and identically distributed random vectors. Second one—GMSP has univariate semi-Pareto marginals and it is characterized by finite sample minima. Third one—MSP is characterized through a geometric minimization procedure. All these three characterizations are based on the general and the particular solutions of the Euler's functional equations of k-variates.     

Modelling gateway placement in wireless networks: Geometric k-centres of unit disc graphs

Motivated by the gateway placement problem in wireless networks, we consider the geometric k-centre problem on unit disc graphs: given a set of points P in the plane, find a set F of k points in the plane that minimizes the maximum graph distance from any vertex in P to the nearest vertex in F in the unit disc graph induced by P∪F. We show that the vertex 1-centre provides a 7-approximation of the geometric 1-centre and that a vertex k-centre provides a 13-approximation of the geometric k-centre, resulting in an O(kn)-time 26-approximation algorithm. We describe O(n²m)-time and O(n³)-time algorithms, respectively, for finding exact and approximate geometric 1-centres, and an O(mn2k)-time algorithm for finding a geometric k-centre for any fixed k. We show that the problem is NP-hard when k is an arbitrary input parameter. Finally, we describe an O(n)-time algorithm for finding a geometric k-centre in one dimension.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

Multivariate semi-logistic distributions

Three new multivariate semi-logistic distributions (denoted by MSL⁽¹⁾, MSL⁽²⁾, and GMSL respectively) are studied in this paper. They are more general than Gumbel’s (1961) [1] and Arnold’s (1992) [2] multivariate logistic distributions. They may serve as competitors to these commonly used multivariate logistic distributions. Various characterization theorems via geometric maximization and geometric minimization procedures of the three MSL⁽¹⁾, MSL⁽²⁾ and GMSL are proved. The particular multivariate logistic distribution used in the multiple logistic regression model is introduced. Its characterization theorem is also studied. Finally, some further research work on these MSL is also presented. Some probability density plots and contours of the bivariate MSL⁽¹⁾, MSL⁽²⁾ as well as Gumbel’s and Arnold’s bivariate logistic distributions are presented in the Appendix.     

图的彩虹连通数与最小度和

令G是一个阶为n且最小度为δ的连通图. 当δ很小而n很大时, 现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大, 它们是n的线性函数. 本文中, 我们用另一种参数,即k个独立点的最小度和σ_k来代替δ, 从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界. 本文证明了如果G有k个独立点, 那么rc(GG)≤3kn/(σk+k)+6k-3. 同时也证明了下面的结果, 如果σ_k≤7k或σ_k≥8k, 那么rvc(G)≤(4k+2k²)n/(σ_k+k)+5k; 如果7k<σ_k<8k, 那么rvc(G)≤(38k/9+2k²)n/(σ_k+k)+5k.文中也给出了例子说明我们的界比现有的界更好, 即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k²或rvc(G)≤83k/9+2k², 这意味着当δ很小而σ_k很大时, 我们的界是一个常数, 而现有的界却是n的线性函数.     

Property (X) for Second-Order Nonlinear Differential Equations of Generalized Euler Type

In this paper the generalized nonlinear Euler differential equation t²k(tu′)u″ + t(f(u)+ k(tu′))u′ + g(u) = 0 is considered. Here the functions f(u), g(u) and k(u) satisfy smoothness conditions which guarantee the uniqueness of solutions of initial value problems, however, no conditions of sub(super) linearity are assumed. We present some necessary and sufficient conditions and some tests for the equivalent planar system to have or fail to have property (X⁺), which is very important for the existence of periodic solutions and oscillation theory.     

On the precise growth, covering, and distortion theorems for normalized biholomorphic mappings

In this paper, we consider a normalized biholomorphic mapping f(x) defined on the unit ball in a complex Banach space, where the origin 0 is a zero of order k+1 of f(x)−x. The precise growth and covering theorem for f(x) is obtained when f(x) is a starlike mapping or a starlike mapping of order α. Especially, the precise growth and covering theorem for f(x) is also established when f(x) is a quasi-convex mapping. Moreover, the precise distortion theorem for f(x) is given when f(x) is a convex mapping. Our result includes many known results.     

Weak barrelledness for C(X) spaces

Buchwalter and Schmets reconciled C_c(X) and C_p(X) spaces with most of the weak barrelledness conditions of 1973, but could not determine if -barrelled ⇔ ?^∞-barrelled for C_c(X). The areas grew apart. Full reconciliation with the fourteen conditions adopted by Saxon and Sánchez Ruiz needs their 1997 characterization of Ruess' property (L), which allows us to reduce the C_c(X) problem to its 1973 status and solve it by carefully translating the topology of Kunen (1980) and van Mill (1982) to find the example that eluded Buchwalter and Schmets. The more tractable C_p(X) readily partitions the conditions into just two equivalence classes, the same as for metrizable locally convex spaces, instead of the five required for C_c(X) spaces. Our paper elicits others, soon to appear, that analytically characterize when the Tychonov space X is pseudocompact, or Warner bounded, or when C_c(X) is a df-space (Jarchow's 1981 question).     

Fixed Points for Directional Multi-Valued <Emphasis Type="Italic">k</Emphasis>(·)-Contractions

A fixed point theorem for directional multi-valued k(·)-contractions acting m a complete metric space is established which extends similar results both for k(·)-contractions and directional contractions. Such theorem enables to obtain fixed points theorems for the former class of set-valued maps from those valid for the latter one without metrical convexity or proximinality assumptions, thereby contributing to unify the current setting of the theory. Connections with several recent advances on this subject are also examinated.Mathematics Subject Classifications (2000): 47H10, 54H25     

Identifying large robust network clusters via new compact formulations of maximum k-club problems

Network robustness issues are crucial in a variety of application areas. In many situations, one of the key robustness requirements is the connectivity between each pair of nodes through a path that is short enough, which makes a network cluster more robust with respect to potential network component disruptions. A k-club, which by definition is a subgraph of a diameter of at most k, is a structure that addresses this requirement (assuming that k is small enough with respect to the size of the original network). We develop a new compact linear 0-1 programming formulation for finding maximum k-clubs that has substantially fewer entities compared to the previously known formulation (O(kn²) instead of O(n^k+1), which is important in the general case of k > 2) and is rather tight despite its compactness. Moreover, we introduce a new related concept referred to as an R-robust k-club (or, (k, R)-club), which naturally arises from the developed k-club formulations and extends the standard definition of a k-club by explicitly requiring that there must be at least R distinct paths of length at most k between all pairs of nodes. A compact formulation for the maximum R-robust k-club problem is also developed, and error and attack tolerance properties of the important special case of R-robust 2-clubs are investigated. Computational results are presented for multiple types of random graph instances.     

Space-time discontinuous galerkin method for maxwell equations in dispersive media

In this paper, a unified model for time-dependent Maxwell equations in dispersive media is considered. The space-time DG method developed in [29] is applied to solve the underlying problem. Unconditional L²-stability and error estimate of order O(τ^r+1+h^k+1/2) are obtained when polynomials of degree at most r and k are used for the temporal discretization and spatial discretization respectively. 2-D and 3-D numerical examples are given to validate the theoretical results. Moreover, numerical results show an ultra-convergence of order 2r+1 in temporal variable t.     

A note on k-potence preserving maps

Let M_n be the algebra of all n×n complex matrices and Γ_n the set of all k-potent matrices in M_n. Suppose ?:M_n→M_n is a map satisfying A-λB∈Γ_n implies ?(A)-λ?(B)∈Γ_n, where A, B∈M_n, λ∈C. Then either ? is of the form ?(A)=cTAT^-1, A∈M_n, or ? is of the form ?(A)=cTA^tT^-1, A∈M_n, where T∈M_n is an invertible matrix, c∈C satisfies c^k=c.     

On low degree k-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian) if, for any sequence of k distinct vertices v₁,…,v_k of G, there exists a cycle (respectively, a hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability, and motivated by the fact that k-orderedness of a graph implies (k-1)-connectivity, they posed the question of the existence of low degree k-ordered hamiltonian graphs. We construct an infinite family of graphs, which we call bracelet graphs, that are (k-1)-regular and are k-ordered hamiltonian for odd k. This result provides the best possible answer to the question of the existence of low degree k-ordered hamiltonian graphs for odd k. We further show that for even k, there exist no k-ordered bracelet graphs with minimum degree k-1 and maximum degree less than k+2, and we exhibit an infinite family of bracelet graphs with minimum degree k-1 and maximum degree k+2 that are k-ordered for even k. A concept related to k-orderedness, namely that of k-edge-orderedness, is likewise strongly related to connectivity properties. We study this relation and give bounds on the connectivity necessary to imply k-(edge-)orderedness properties.     

Soliton solutions for (2 + 1)-dimensional and (3 + 1)-dimensional K(m, n) equations

We consider the nonlinear dispersive K(m,n) equation with the generalized evolution term and derive analytical expressions for some conserved quantities. By using a solitary wave ansatz in the form of sech^p function, we obtain exact bright soliton solutions for (2 + 1)-dimensional and (3 + 1)-dimensional K(m,n) equations with the generalized evolution terms. The results are then generalized to multi-dimensional K(m,n) equations in the presence of the generalized evolution term. An extended form of the K(m,n) equation with perturbation term is investigated. Exact bright soliton solution for the proposed K(m,n) equation having higher-order nonlinear term is determined. The physical parameters in the soliton solutions are obtained as function of the dependent model coefficients.     

Existence and Regularity of Solutions to Model for Liquid Mixture of He-He

Existence and regularity of solutions to model for liquid mixture of ³He-⁴He is considered in this paper. First, it is proved that this system possesses a unique global weak solution in H¹(ω,C×R) by using Galerkin method. Secondly, by using an iteration procedure, regularity estimates for the linear semigroups, it is proved that the model for liquid mixture of ³He-⁴He has a unique solution in H^k(ω,C×R) for all k ≥ 1.     

Subclasses of k-trees: Characterization and recognition

A k-tree is either a complete graph on k vertices or a graph G=(V,E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new subclasses of k-trees and their properties. First, we present the definition and characterization of k-path graphs, based on the concept of k-paths, that generalizes the classic concept of paths. We also introduce the simple-clique k-trees, of which the maximal outerplanar graphs and the planar 3-trees are particular cases. Based on Characterization Theorems, we show recognition algorithms for both families. Finally, we establish the inclusion relations among these new classes and k-trees.     

Power optimization for connectivity problems

Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MPk-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MPk-CSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MPk-EDP). We give an O(log⁴ n)-approximation algorithm for MPb-EC. This gives an O(log⁴ n)-approximation algorithm for MPk-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an approximation algorithm for ECSS, and for its variant in directed graphs (i.e., MPk-EDP), we establish the following inapproximability threshold: MPk-EDP cannot be approximated within O(2^log1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time. This paper was done when V. S. Mirrokni was at Computer Science and Artificial Intelligence Laboratory, MIT.     

Finding the smallest triangles containing a given convex polygon

For a given convex n-gon P an O(n log²n) algorithm finds all local minima (with respect to area) among the triangles containing P. No areas are computed, for the algorithm is based on a simple geometric characterization of the local minima.