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.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

Total minus domination in k-partite graphs

A function f defined on the vertices of a graph G=(V,E),f:V→{-1,0,1} is a total minus dominating function (TMDF) if the sum of its values over any open neighborhood is at least one. The weight of a TMDF is the sum of its function values over all vertices. The total minus domination number, denoted by , of G is the minimum weight of a TMDF on G. In this paper, a sharp lower bound on of k-partite graphs is given.     

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 k-product uncapacitated facility location problem

A k-product uncapacitated facility location problem can be described as follows. There is a set of demand points where clients are located and a set of potential sites where facilities of unlimited capacities can be set up. There are k different kinds of products. Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost determined by the product it intends to supply. There is a non-negative cost of shipping goods between each pair of locations. These costs are assumed to be symmetric and satisfy the triangle inequality. The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k   facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, an approximation algorithm within a factor of 2k+1$2k+1$ of the optimum cost is presented. Assuming that fixed setup costs are zero, we give a 2k-1$2k-1$ approximation algorithm for the problem. In addition we show that for the case k=2$k=2$, the problem is NP-complete when the cost structure is general and there is a 2-approximation algorithm when the costs are symmetric and satisfy the triangle inequality. The algorithm is shown to produce an optimal solution if the 2-product uncapacitated facility location problem with no fixed costs happens to fall on a tree graph.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

The d-precoloring problem for k-degenerate graphs

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted to the class of partial k-trees (without any size restriction on S). We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.     

The k-level facility location game

We propose a cost-sharing scheme for the k-level facility location game that is cross-monotonic, competitive, and 6-approximate cost recovery. This extends the recent result for the 1-level facility location game of Pál and Tardos.     

Constant tolerance intersection graphs of subtrees of a tree

A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {S_v}_v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |S_u∩S_v|?t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h?s?3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well.     

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.     

A new family of k-Fibonacci numbers

In the present paper, we give a new family of k-Fibonacci numbers and establish some properties of the relation to the ordinary Fibonacci numbers. Furthermore, we describe the recurrence relations and the generating functions of the new family for k=2 and k=3, and presents a few identity formulas for the family and the ordinary Fibonacci numbers.     

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.     

Fast block diagonalization of k-tridiagonal matrices

In the present paper, we give a fast algorithm for block diagonalization of k-tridiagonal matrices. The block diagonalization provides us with some useful results: e.g., another derivation of a very recent result on generalized k-Fibonacci numbers in [M.E.A. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461]; efficient (symbolic) algorithm for computing the matrix determinant.     

Embedding long cycles in faulty k-ary 2-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. Given an even k ? 4, let (V₁, V₂) be the bipartition of the k-ary 2-cube, f_v1, f_v2 be the numbers of faulty vertices in V₁ and V₂, respectively, and f_e be the number of faulty edges. In this paper, we prove that there exists a cycle of length k² − 2max{f_v1, f_v2} in the k-ary 2-cube with 0 ? f_v1 + f_v2 + f_e ? 2. This result is optimal with respect to the number of faults tolerated.     

Examples of proper k-ball contractive retractions in F-normed spaces

Assume X is an infinite dimensional F-normed space and let r be a positive number such that the closed ball Br(X) of radius r is properly contained in X. The main aim of this paper is to give examples of regular F-normed ideal spaces in which there is a 1-ball or a (1+ε)-ball contractive retraction of Br(X) onto its boundary with positive lower Hausdorff measure of noncompactness. The examples are based on the abstract results of the paper, obtained under suitable hypotheses on X.     

Reliability evaluation of multi-state consecutive k-out-of-r-from-n: G system

This paper proposes a model that generalizes the linear consecutive k-out-of-r-from-n: G system to multi-state case. In this model the system consists of n linearly ordered multi-state components. Both the system and its components can have different states: from complete failure up to perfect functioning. The system is in state j or above if and only if at least k_j components out of r consecutive are in state j or above. An algorithm is provided for evaluating reliability of a special case of multi-state consecutive k-out-of-r-from-n: G system. The algorithm is based on the application of the total probability theorem and on the application of a special case taken from the [Jinsheng Huang, Ming J. Zuo, Member IEEE and Yanhong Wu, Generalized multi-state k-out-of-n: G system, IEEE Trans. Reliab. 49(1) (2000) 105–111.]. Also numerical results of the formerly published test examples and new examples are given.     

A characterization of k-hyponormality via weak subnormality

An operator T acting on a Hilbert space is said to be weakly subnormal if there exists an extension acting on such that for all . When such partially normal extensions exist, we denote by m.p.n.e.(T) the minimal one. On the other hand, for k?1, T is said to be k-hyponormal if the operator matrix is positive. We prove that a 2-hyponormal operator T always satisfies the inequality T∗[T∗,T]T?‖T‖2[T∗,T], and as a result T is automatically weakly subnormal. Thus, a hyponormal operator T is 2-hyponormal if and only if there exists B such that BA∗=A∗T and is hyponormal, where A:=[T∗,T]1/2. More generally, we prove that T is (k+1)-hyponormal if and and only if T is weakly subnormal and m.p.n.e.(T) is k-hyponormal. As an application, we obtain a matricial representation of the minimal normal extension of a subnormal operator as a block staircase matrix.     

On k-regular functions with values in a universal Clifford algebra

In this paper, we mainly study properties of nullsolutions of the operator Dk (k∈N^∗=N?{0}), so-called k-regular functions. Firstly, we study the set of all homogeneous polynomials of degree p in x₁,…,xn which are k-regular in the whole Rn, clearly is a right module over C(Vn,n), we construct a basis for the right module . Secondly, we study the k-regular and analytic functions, and we give the Taylor expansions for these functions. At last, the corresponding Taylor expansions for k-regular functions are given since each k-regular function is a real analytic function.