Disjoint factors of diameter two in complete graphs

Let f(k) be the least positive integer n such that the complete graph with n vertices has a decomposition into k factors of diameter two. It is well known that f(2) = 5, f(3) = 12 or 13, and 4k ?1 ? f(k) ? 7k for every integer k ? 4. In the present paper it is proved that 6k ? 52 ? f(k) ? 6k for every integer k ? 2. (For k ? 370 also a better lower estimate of f(k) is given.)     

Universal tilings and universal (0,1)-matrices

A periodic regular tiling of the plane by black and white squares is k-universal if it contains all possible k × k blocks of black and white tiles. There is a 4 × 4 periodic tiling that is 2-universal; this paper looks for the smallest 3-universal tiling and obtains a 64 × 32 periodic tiling that is 3-universal.Related to this is the following: a (0,1)-matrix is k-universal if every possible k × k (0,1)-matrix occurs as a submatrix. It is proved that, for k even, there is a k2^k/2 matrix that is k-universal and, for k odd, there is a (3k + 1)2^(k−3)/2 by (3k − 1)2^k−3/2 matrix that is k-universal.     

On the chromatic number of q-Kneser graphs

We show that the q-Kneser graph qK _2k:k (the graph on the k-subspaces of a 2k-space over GF(q), where two k-spaces are adjacent when they intersect trivially), has chromatic number q ^k ?+?q ^k?1 for k?=?3 and for k < q log q ? q. We obtain detailed results on maximal cocliques for k = 3.     

All-shortest-path 2-interval routing is NP-complete

k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. All of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problems have been proved to be NP-complete for every k≥3, and remain open for k=1,2. In this paper, we close the open case of k=2 by showing that it is NP-complete to decide whether a graph admits an all-shortest-path 2-IRS. The same proof is also valid for all-shortest-path Strict 2-IRS. All-shortest-path Strict k-IRS is previously known to be polynomial for k=1, open for k=2,3, and NP-complete for every constant k≥4.     

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 the complexity of a family of generalized matching problems

We consider a family of generalized matching problems called k-feasible matching (k-RM) problems, where k? {1,2,3,…} ∪ {∞}. We show each k-FM problem to be NP-complete even for very restricted cases. We develop a dynamic programming algorithm that solves in polynomial time the k-FM problem for graphs with width bounded by 2k. We also show that for any subset S of {1,2,…} ∪ {∞}, there is a set D of problem instances such that for k in S the k-FM problem is NP-complete on D, while for k not in S the k-FM problem is polynomially solvable on D.     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

Extremal edge problems for graphs with given hyperoctahedral automorphism group

For k > 1, let H_k denote the hyperoctahedral group S_k[S₂] of order 2^kk!. An (H_k, n)- graph is a graph on n vertices with automorphism group abstractly isomorphic to H_k. For each k an (H_k, n)-graph exists precisely when n ? 2k; for each n ? 2k the minimum and maximum number of edges possible for such graphs are determined. The analogous results for connected (H_k, n)-graphs are also obtained.     

Log-convexity and log-concavity of hypergeometric-like functions

We find sufficient conditions for log-convexity and log-concavity for the functions of the forms a?∑fkk(a)xk, a?∑fkΓ(a+k)xk and a?∑fkxk/k(a). The most useful examples of such functions are generalized hypergeometric functions. In particular, we generalize the Turán inequality for the confluent hypergeometric function recently proved by Barnard, Gordy and Richards and log-convexity results for the same function recently proved by Baricz. Besides, we establish a reverse inequality which complements naturally the inequality of Barnard, Gordy and Richards. Similar results are established for the Gauss and the generalized hypergeometric functions. A conjecture about monotonicity of a quotient of products of confluent hypergeometric functions is made.     

Some Defective Parameters in Graphs

Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with a maximum degree of at most k. Many parameters in graph theory are defined in terms of independent sets. Accordingly, their definitions can be expanded taking into account the notion of k-sparse sets. In this discussion, we examine several of those extensions. Similarly, S is k-dense if S induces a k-sparse graph in the complement of G. A partition of V(G) is a k-defective cocoloring if each part is k-sparse or k-dense. The minimum order of all k-defective cocolorings is the k-defective cochromatic number of G and denoted z _k (G). Analogous notions are defined similarly for k-defective coloring where V(G) is partitioned into k-sparse parts. We show the NP-hardness of computing maximum k-defective sets in planar graphs with maximum degree at most k + 1 and arbitrarily large girth. We explore the extension of Ramsey numbers to k-sparse and k-dense sets of vertices. Lastly, we discuss some bounds related to k-defective colorings and k-defective cocolorings.     

Some dimensional results for homogeneous Moran sets

Let ?(¦n _k ¦k?1,¦c _k ¦k?1) be the collection of homogeneous Moran sets determined by ¦n _k ¦k?1 and ¦c _k ¦k?1, where ¦n _k ¦k?1 is a sequence of positive integers and ¦c _k ¦k?1 a sequence of positive numbers. Then the maximal and minimal values of Hausdorff dimensions for elements in ? are determined. The result is proved that for any values between the maximal and minimal values, there exists an element in ?(¦n _k ¦k?1,¦c _k¦k?1) such that its Hausdorff dimension is equal tos. The same results hold for packing dimension. In the meantime, some other properties of homogeneous Moran sets are discussed.     

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.     

Contraction obstructions for treewidth

We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences.     

On stronger conjectures that imply the Erd?s-Moser conjecture

The Erd?s-Moser conjecture states that the Diophantine equation Sk(m)=mk, where Sk(m)=k¹+k²+?+k(m−1), has no solution for positive integers k and m with k?2. We show that stronger conjectures about consecutive values of the function Sk, that seem to be more naturally, imply the Erd?s-Moser conjecture.     

More on planar point subsets with a specified number of interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let g(k) be the smallest integer such that every set P of points in the plane with no three collinear points and with at least g(k) interior points has a subset containing precisely k interior point of P. We prove that g(k) ≥ 3k for k ≥ 3, which improves the known result that g(k) ≥ 3k ? 1 for k ≥ 3.     

Minimal linear spaces

A decent linear space DLS(k) is a linear space with minimal line size at least three and with maximal line size exactly k. Denote by v_k (resp. b_k) the minimum number of points (resp. lines) in a DLS(k). We determine the numbers v_k and b_k for all k and prove that each DLS(k) with b_k lines has v_k points. Thus the DLS(k)'s with b_k lines are the minimal linear spaces.     

k-eccentricity and absolute k-centrum of a probabilistic tree

The k-eccentricity evaluated at a point x of a graph G is the sum of the (weighted) distances from x to the k vertices farthest from it. The k-centrum is the set of vertices for which the k-eccentricity is a minimum. The concept of k-centrum includes, as a particular case, that of center and that of centroid (or median) of a graph. The absolute k-centrum is the set of points (not necessarily vertices) for which the k-eccentricity is a minimum. In this paper it will be proven that, for a weighted tree, both deterministic and probabilistic, the k-eccentricity is a convex function and that the absolute k-centrum is a connected set and is contained in an elementary path. Hints will be given for the construction of an algorithm to find the k-centrum and the absolute k-centrum.     

On shortest crucial words avoiding abelian powers

Let k≥2 be an integer. An abeliankth power is a word of the form X₁X₂?X_k where X_i is a permutation of X₁ for 2≤i≤k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelian kth power for any letter x occurring in W.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4n−7 for n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−13 for n≥5. They have also conjectured that for any k≥4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ?_k(n), is k²n−(k²+k+1). This is currently the best known upper bound for ?_k(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1) for n≥5 and k≥4. In this note, we improve this lower bound by proving that for n≥2k−1, ?_k(n)≥k²n−(2k³−3k²+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

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.