A bijection between 2-triangulations and pairs of non-crossing Dyck paths

A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.     

Multitriangulations as Complexes of Star Polygons

Maximal (k+1)-crossing-free graphs on a planar point set in convex position, that is, k-triangulations, have received attention in recent literature, motivated by several interpretations of them. We introduce a new way of looking at k-triangulations, namely as complexes of star polygons. With this tool we give new, direct proofs of the fundamental properties of k-triangulations, as well as some new results. This interpretation also opens up new avenues of research that we briefly explore in the last section. This paper was written while the first author was visiting the second one via an internship agreement between the école Normale Supérieure and the University of Cantabria. Research of both authors was also funded by grant MTM2005-08618-C02-02 of the Spanish Ministry of Education and Science. A short version of this paper was presented at the FPSAC 08 conference.     

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.     

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.     

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.     

Factors of the Gaussian coefficients

We present some simple observations on factors of the q-binomial coefficients, the q-Catalan numbers, and the q-multinomial coefficients. Writing the Gaussian coefficient with numerator n and denominator k in a form such that 2k?n by the symmetry in k, we show that this coefficient has at least k factors. Some divisibility results of Andrews, Brunetti and Del Lungo are also discussed.     

Extremal k-edge-hamiltonian hypergraphs

An r-uniform hypergraph is k-edge-hamiltonian iff it still contains a hamiltonian-chain after deleting any k edges of the hypergraph. What is the minimum number of edges in such a hypergraph? We give lower and upper bounds for this question for several values of r and k.     

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.     

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.     

The maximum integer multiterminal flow problem in directed graphs

Given an arc-capacitated digraph and k terminal vertices, the directed maximum integer multiterminal flow problem is to route the maximum number of flow units between the terminals. We introduce a new parameter k_L?k for this problem and study its complexity with respect to k_L.     

Parallel and k-out-of-n: G systems with nonidentical components and their mean residual life functions

A system with n independent components which has a k-out-of-n: G structure operates if at least k components operate. Parallel systems are 1-out-of-n: G systems, that is, the system goes out of service when all of its components fail. This paper investigates the mean residual life function of systems with independent and nonidentically distributed components. Some examples related to some lifetime distribution functions are given. We present a numerical example for evaluating the relationship between the mean residual life of the k-out-of-n: G system and that of its components.     

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.     

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.     

Packing of Steiner trees and S-connectors in graphs

Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set S⊆V(G) to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G.We improve Lau?s result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimi?s criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem.     

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.     

Map operations and k-orbit maps

A k-orbit map is a map with k flag-orbits under the action of its automorphism group. We give a basic theory of k-orbit maps and classify them up to k?4. “Hurwitz-like” upper bounds for the cardinality of the automorphism groups of 2-orbit and 3-orbit maps on surfaces are given. Furthermore, we consider effects of operations like medial and truncation on k-orbit maps and use them in classifying 2-orbit and 3-orbit maps on surfaces of small genus.     

Orbits of rational n-sets of projective spaces under the action of the linear group

Let k=Fq be a finite field. We enumerate k-rational n-sets of (unordered) points in a projective space PN over k, and we compute the generating function for the numbers of PGLN+1(k)-orbits of these n-sets. For N=1,2 we obtain a formula for these numbers of orbits as a polynomial in q with integer coefficients.     

q-Analog of tableau containment

We prove a q-analog of the following result due to McKay, Morse and Wilf: the probability that a random standard Young tableau of size n contains a fixed standard Young tableau of shape λ?k tends to fλ/k! in the large n limit, where fλ is the number of standard Young tableaux of shape λ. We also consider the probability that a random pair (P,Q) of standard Young tableaux of the same shape contains a fixed pair (A,B) of standard Young tableaux.     

A recursion formula for k-Schur functions

The Bernstein operators allow one to build recursively the Schur functions. We present a recursion formula for k-Schur functions at t=1 based on combinatorial operators that generalize the Bernstein operators. The recursion leads immediately to a combinatorial interpretation for the expansion coefficients of k-Schur functions at t=1 in terms of homogeneous symmetric functions.     

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].