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.     

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.     

Arithmetic properties of q-Fibonacci numbers and q-pell numbers

We investigate some arithmetic properties of the q-Fibonacci numbers and the q-Pell numbers.     

Extremal double hexagonal chains with respect to k-matchings and k-independent sets

“Double hexagonal chains” can be considered as benzenoids constructed by successive fusions of successive naphthalenes along a zig-zag sequence of triples of edges as appear on opposite sides of each naphthalene unit. In this paper, we discuss the numbers of k-matchings and k-independent sets of double hexagonal chains, as well as Hosoya indices and Merrifield-Simmons indices, and obtain some extremal results: among all the double hexagonal chains with the same number of naphthalene units, (a) the double linear hexagonal chain has minimal k-matching number and maximal k-independent set number and (b) the double zig-zag hexagonal chain has maximal k-matching number and minimal k-independent set number, which are extensions to hexagonal chains [L. Zhang and F. Zhang, Extremal hexagonal chains concerning k-matchings and k-independent sets, J. Math. Chem. 27 (2000) 319-329].     

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.     

On k-Fibonacci sequences and polynomials and their derivatives

The k-Fibonacci polynomials are the natural extension of the k-Fibonacci numbers and many of their properties admit a straightforward proof. Here in particular, we present the derivatives of these polynomials in the form of convolution of k-Fibonacci polynomials. This fact allows us to present in an easy form a family of integer sequences in a new and direct way. Many relations for the derivatives of Fibonacci polynomials are proven.     

Existence of finite test-sets for k-power-freeness of uniform morphisms

A challenging problem is to find an algorithm to decide whether a morphism is k-power-free. When k?3, we provide such an algorithm for uniform morphisms showing that in such a case, contrarily to the general case, there exist finite test-sets for k-power-freeness.     

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.     

The <Emphasis Type="Italic">k</Emphasis>-Fibonacci matrix and the Pascal matrix

We define the k-Fibonacci matrix as an extension of the classical Fibonacci matrix and relationed with the k-Fibonacci numbers. Then we give two factorizations of the Pascal matrix involving the k-Fibonacci matrix and two new matrices, L and R. As a consequence we find some combinatorial formulas involving the k-Fibonacci numbers.     

On 3-regular 4-ordered graphs

A simple graph G is k-ordered (respectively, k-ordered hamiltonian), if for any sequence of k distinct vertices v₁,…,v_kof G there exists a cycle (respectively, hamiltonian cycle) in G containing these k vertices in the specified order. In 1997 Ng and Schultz introduced these concepts of cycle orderability and posed the question of the existence of 3-regular 4-ordered (hamiltonian) graphs other than K₄ and K_3,3. Ng and Schultz observed that a 3-regular 4-ordered graph on more than 4 vertices is triangle free. We prove that a 3-regular 4-ordered graph G on more than 6 vertices is square free,and we show that the smallest graph that is triangle and square free, namely the Petersen graph, is 4-ordered. Furthermore, we prove that the smallest graph after K₄ and K_3,3 that is 3-regular 4-ordered hamiltonianis the Heawood graph. Finally, we construct an infinite family of 3-regular 4-ordered graphs.     

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.     

Some properties and characterizations for generalized multivariate Pareto distributions

In this paper, several distributional properties and characterization theorems of the generalized multivariate Pareto distributions are studied. It is found that the multivariate Pareto distributions have many mixture properties. They are mixed either by geometric, Weibull, or exponential variables. The multivariate Pareto, MP^(k)(I), MP^(k)(II), and MP^(k)(IV) families have closure property under finite sample minima. The MP^(k)(III) family is closed under both geometric minima and geometric maxima. Through the geometric minima procedure, one characterization theorem for MP^(k)(III) distribution is developed. Moreover, the MP^(k)(III) distribution is proved as the limit multivariate distribution under repeated geometric minimization. Also, a characterization theorem for the homogeneous MP^(k)(IV) distribution via the weighted minima among the ordered coordinates is developed. Finally, the MP^(k)(II) family is shown to have the truncation invariant property.     

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.     

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.     

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.     

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.     

Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees

An approach for factoring general boolean functions was described in Golumbic and Mintz [Factoring logic functions using graph partitioning, in: Proceedings of IEEE/ACM International Conference on Computer Aided Design, November 1999, pp. 195-198] and Mintz and Golumbic [Factoring Boolean functions using graph partitioning, Discrete Appl. Math. 149 (2005) 131-153] which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality.For non-read-once functions, we investigate their factoring based on their corresponding graph classes. In particular, we show that if a function F is normal and its corresponding graph is a partial k-tree, then F is a read 2^k function and a read 2^k formula for F can be obtained in polynomial time.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

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.     

A weighted curvature flow for shape deformation

In this paper we shall discuss a weighted curvature flow for a regular curve in the 2D Euclidean space. The weighted curvature flow for planar curves is a generalization of the well-known curvature flow discussed by Gage, Hamilton and Grayson. Under a suitable weighted curvature flow, convex curves will remain convex in the deformation process. However, the curve may not converge to a round point for general weights. Indeed, for a nonnegative weight function ω(u) with k isolated zeros, a curve will converge to a limiting k-polygon. The weighted curvature flow will have many useful properties which have applications to image processing. We shall also present some numerical simulations to illustrate how curves deform under the weighted curvature flow with different weight functions ω(u). Moreover, our algorithm is very effective and stable. The approximation of higher derivatives in our new algorithm only involve in the neighboring points.