On the largest kth eigenvalues of trees with n≡0 (mod k)

We consider the only remaining unsolved case n≡0 (mod k) for the largest kth eigenvalue of trees with n vertices. In 1995, Jia-yu Shao gave complete solutions for the cases k=2,3,4,5,6 and provided some necessary conditions for extremal trees in general cases (cf. [Linear Algebra Appl. 221 (1995) 131]). We further improve Shao's necessary condition in this paper, which can be seen as the continuation of [Linear Algebra Appl. 221 (1995) 131].     

Covering vertices of a graph by k disjoint cycles

Let d, k and n be three integers with k3, d4k−1 and n3k. We show that if d(x)+d(y)d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{d,n} vertices of G.     

Sperner systems containing at most k sets of every cardinality

We prove using a direct construction that one can choose n − 2 subsets of an n-element set with different cardinality such that none of them contains any other. As a generalization, we prove that if for any j we can have at most k subsets containing exactly j elements (k> 1), then for n 5 we can choose at most k(n − 3) subsets from an n-element set such that they form a Sperner system. Moreover, we prove that this can be achieved if n is large enough, and give a construction for n 8k − 4.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

Flag-transitive 2-(v, k, λ) symmetric designs with (k, λ) = 1 and alternating socle

Consider the flag-transitive 2-(v, k, λ) symmetric designs with (k, λ) = 1. We prove that if {D} is a nontrivial 2-(v, k, λ) symmetric design with (k, λ) = 1 and G≤Aut({D}) is flag-transitive with Soc(G) = A_n for n≥5, then {D} is the projective space PG₂(3,2) and G = A₇.     

k-Lucas numbers and associated bipartite graphs

For a positive integer k2, the k-Fibonacci sequence {g_n^(k)} is defined as: g₁^(k)==g_k−2^(k)=0, g_k−1^(k)=g_k^(k)=1 and for n>k2, g_n^(k)=g_n−1^(k)+g_n−2^(k)++g_n−k^(k). Moreover, the k-Lucas sequence {l_n^(k)} is defined as l_n^(k)=g_n−1^(k)+g_n+k−1^(k) for n1. In this paper, we consider the relationship between g_n^(k) and l_n^(k) and 1-factors of a bipartite graph.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

Non-naturally reductive Einstein metrics on Sp(n)

We prove that Sp(2k+l)admits at least two non-naturally reductive Einstein metrics which are Ad(Sp(k)×Sp(k)×Sp(l))-invariant ifk<1.It implies that every compact simple Lie group Sp(n)for n≥4 admits at least 2[(n-1)/3]non-naturally reductive left-invariant Einstein metrics.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O(n²) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(logn) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log²n+k) time.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Pancyclicity mod k of claw-free graphs and K1,4-free graphs

For any natural number k, a graph G is said to be pancyclic mod k if it contains a cycle of every length modulo k. In this paper, we show that every K_1,4-free graph G with minimum degree δ(G)k+3 is pancyclic mod k and every claw-free graph G with δ(G)k+1 is pancyclic mod k, which confirms Thomassen's conjecture (J. Graph Theory 7 (1983) 261–271) for claw-free graphs.     

Non-neutrality of the Stiefel manifolds Vn,k II

The Stiefel manifolds V_2^m−1,k are shown to be non-neutral for m5, 2^m−1+2k=2ℓ<2^m−2.     

Maximum planar sets that determine k distances

Maximum planar sets that determine k distances are identified for k 5. Evidence is presented for the conjecture that all maximum sets for k 7 are subsets of the triangular lattice.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

No-hole L(2,1)-colorings

An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,…,k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0,1,…,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ(G) of G as ∞ if G has no no-hole coloring; otherwise μ(G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…,k}.

Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m.     

A local search approximation algorithm for k-means clustering

In k-means clustering we are given a set of n data points in d-dimensional space and an integer k, and the problem is to determine a set of k points in  , called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the very high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.

We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+)-approximation algorithm. We present an example showing that any approach based on performing a fixed number of swaps achieves an approximation factor of at least (9−) in all sufficiently high dimensions. Thus, our approximation factor is almost tight for algorithms based on performing a fixed number of swaps. To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.     

Graphs with prescribed local connectivities

A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected (n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity.     

The k-ball l-path branch weight centroid

If x is a vertex of a tree T of radius r, if k and l are integers, if 0 k r, 0 l r, and if P is an l-path with one end at x, then define β(x; k, P) to be the number of vertices of T that are reachable from x via the l-path P and that are outside of the k-ball about x. That is, β(x;k,P) = {yεV(T):y is reachable from x via P,d(x,y) > k}. Define the k-ball l-path branch weight of x, denoted β(x;k,l), to be max {β(x;k,P):P an l-path with one end at x}, and define the k-balll-path branch weight centroid of T, denoted B(T;k,l), to be the set xεV(T): β(x;k,l) β(y;k,l), yεV(T). This two-parameter family of central sets in T includes the one-parameter family of central sets called the k-nuclei introduced by Slater (1981) which has been shown to be the one parameter family of central sets called the k-branch weight centroids by Zaw Win (1993). It also includes the one-parameter family of central sets called the k-ball branch weight centroid introduced by Reid (1991). In particular, this new family contains the classical central sets, the center and the median (which Zelinka (1968) showed is the ordinary branch weight centroid). The sets obtained for particular values of k and l are examined, and it is shown that for many values they consist of one vertex or two adjacent vertices.