Toppling kings in a tournament by introducing new kings

A king of a tournament is a vertex which can reach any other vertex within two steps. Let K be the king set of a tournament T. A subset M of K is c-topplable if there exists a supertournament T* of T such that there is a set N of c vertices in T * – T and (K – M) U N is exactly the king set of T*. A characterization of c-topplable sets of kings is given in this paper.     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

A class of facet producing graphs for vertex packing polyhedra

We examine a family of graphs called webs. For integers n ? 2 and $\text{k, 1 ? k ?}\text{1}\text{2}\text{n}$, the web W(n, k) has vertices V_n = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?V_n (sums mod n)}. A characterization is given for the vertex packing polyhedron of W(n, k) to contain a facet, none of whose projections is a facet for the lower dimensional vertex packing polyhedra of proper induced subgraphs of W(n, k). Simple necessary and sufficient conditions are given for W(n, k) to contain W(n′, k′) as an induced subgraph; these conditions are used to show that webs satisfy the Strong Perfect Graph Conjecture. Complements of webs are also studied and it is shown that if both a graph and its complement are webs, then the graph is either an odd hole or its complement.     

Kings in semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete p‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p‐partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r‐king is a vertex q such that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171–183) on the number of 4‐kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4‐kings for every k = 1, 2, 3, 4, 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 177‐183, 2000     

The existence and uniqueness of strong kings in tournaments

A king x in a tournament T is a player who beats any other player y directly (i.e., x→y) or indirectly through a third player z (i.e., x→z and z→y). For x,y∈V(T), let b(x,y) denote the number of third players through which x beats y indirectly. Then, a king x is strong if the following condition is fulfilled: b(x,y)>b(y,x) whenever y→x. In this paper, a result shows that for a tournament on n players there exist exactly k strong kings, 1?k?n, with the following exceptions: k=n-1 when n is odd and k=n when n is even. Moreover, we completely determine the uniqueness of tournaments.     

Characterizations of 2-variegated graphs and of 3-variegated graphs

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. We prove that a graph G on 2n vertices is 2-variegated if and only if there exists a set S of n independent edges in G such that no cycle in G contains an odd number of edges from S. We also characterize 3-variegated graphs.     

A note on the congruence \left( {_{mp^k }^{np^k } } \right) \equiv \left( {_m^n } \right) (mod p r )

In the paper we discuss the following type congruences: $$\left( {_{mp^k }^{np^k } } \right) \equiv \left( {_m^n } \right)(\bmod p^r ),$$ where p is a prime, n, m, k and r are various positive integers with n ? m ? 1, k ? 1 and r ? 1. Given positive integers k and r, denote by W(k, r) the set of all primes p such that the above congruence holds for every pair of integers n ? m ? 1. Using Ljunggren’s and Jacobsthal’s type congruences, we establish several characterizations of sets W(k, r) and inclusion relations between them for various values k and r. In particular, we prove that W(k + i, r) = W(k ? 1, r) for all k ? 2, i ? 0 and 3 ? r ? 3k, and W(k, r) = W(1, r) for all 3 ? r ? 6 and k ? 2. We also noticed that some of these properties may be used for computational purposes related to congruences given above.     

Representing posets with k-tournaments

In this paper, we introduce a binary relation on the vertex set of a k-tournament, and using this relation show that every finite poset with cardinality n4 can be represented by a k-tournament for every k satisfying 3kn–1.     

On a variation of the Oberwolfach problem

We consider the following “spouse-avoiding” variant of the Oberwolfach problem (briefly NOP): “At a gathering there are n couples. Is it possible to arrange a seating for the 2n people present at s round tables T₁,T₂,…,T_s (where T_i can accomodate k_i ? 3 people and Σk_i=2n) for m different meals so that each person has every other person except his spouse for a neighbour exactly once?” We prove several results concerning the existence of solutions to NOP. In particular, we settle the cases when the tables accomodate the same “small” number of people or when there are only two tables one of them accomodating a “small” number of people or when the total number of people is “small”.     

Super-simple, Pan-orientable, and Pan-decomposable BIBDs with Block Size 4 and Related Structures

Let v, k, and μ be positive integers. A tournament T of order k, briefly k-tournament, is a directed graph on k vertices in which there is exactly one directed edge between any two vertices. A (v, k, λ = 2μ)-BIBD is called T-orientable if for each of its blocks B, it is possible to replace B by a copy of T on the set B so that every ordered pair of distinct points appears in exactly μ k-tournaments. A (v, k, λ = 2μ)-BIBD is called pan-orientable if it is T-orientable for every possible k-tournament T. In this paper, we continue the earlier investigations and complete the spectrum for (v, 4, λ = 2μ)-BIBDs which possess both the pan-orientable property and the pan-decomposable property first introduced by Granville et al. (Graphs Comb 5:57–61, 1989). For all μ, we are able to show that the necessary existence conditions are sufficient. When λ = 2 and v > 4, our designs are super-simple, that is they have no two blocks with more than two common points. One new corollary to this result is that there exists a (v, 4, 2)-BIBD which is both super-simple and directable for all v ≡ 1, 4 (mod 6), v > 4. Finally, we investigate the existence of pan-orientable, pan-decomposable (v, 4, λ = 2μ)-BIBDs with a pan-orientable, pan-decomposable (w, 4, λ = 2μ)-BIBD as a subdesign; here we obtain complete results for λ = 2, 4, but there remain several open cases for λ = 6 (mostly for v < 4w), and the case λ = 12 still has to be investigated.     

Matchings in starlike trees

Let m(G,k) be the number of k-matchings in the graph G. We write G₁ ⪯ G₂ if m(G₁, k) ≤ m(G₂, k) for all k = 1, 2,…. A tree is said to be starlike if it possesses exactly one vertex of degree greater than two. The relation T₁ ⪯ T₂ is shown to hold for various pairs of starlike trees T₁, T₂. The starlike trees (with a given number of vertices), extremal with respect to the relation ⪯, are characterized.     

Some graphs determined by their (signless) Laplacian spectra

Let W _n = K ₁ ? C _n?1 be the wheel graph on n vertices, and let S(n, c, k) be the graph on n vertices obtained by attaching n-2c-2k-1 pendant edges together with k hanging paths of length two at vertex υ ₀, where υ ₀ is the unique common vertex of c triangles. In this paper we show that S(n, c, k) (c ? 1, k ? 1) and W _n are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that S(n, c, k) and its complement graph are determined by their Laplacian spectra, respectively, for c ? 0 and k ? 1.     

Some unavoidable subdigraphs of tournaments

Let H(n, i) be a simple (n ? 1)-path v₁ → v₂ → …? → v_n with an additional arc v₁v_i (3 ? i ? n). We prove that for each n and i (3 ? i ? n), with few exceptions, every n-tournament T_n contains a copy of H(n, i).     

Convex labelings of trees

A convex labeling of a tree T of order n is a one-to-one function f from the vertex set of T into the nonnegative integers, so that f(y) ? (f(x) + f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f(v) ? n ? 1 for every vertex v of T, then f is a perfect convex labeling and T is called a perfectly convex tree. Jamison introduced this concept and conjectured that every tree is perfectly convex. We show that there exists an infinite class of trees, none of which is perfectly convex, and in fact prove that for every n there exists a tree of order n which requires a convex labeling with maximum value at least 6n/5 – 22. We also prove that every tree of order n admits a convex labeling with maximum label no more than n²/8 + 2. In addition, we present some constructive methods for obtaining perfect convex labelings of large classes of trees.     

On Turan hypergraphs

Let α(H) be the stability number of a hypergraph H = (X, $\text{E}$). T(n, k, α) is the smallest q such that there exists a k-uniform hypergraph H with n vertices, q edges and with α(H) ? α. A k-uniform hypergraph H, with n vertices, T(n, k, α) edges and α(H) ?α is a Turan hypergraph. The value of T(n, 2, α) is given by a theorem of Turan. In this paper new lower bounds to T(n, k, α) are obtained and it is proved that an infinity of affine spaces are Turan hypergraphs.     

On k-hyperexpansive operators

This paper considers the k-hyperexpansive Hilbert space operators T (those satisfying , 1?n?k) and the k-expansive operators (those satisfying the above inequality merely for n=k). It is known that if T is k-hyperexpansive then so is any power of T; we prove the analogous result for T assumed merely k-expansive. Turning to weighted shift operators, we give a characterization of k-expansive weighted shifts, and produce examples showing the k-expansive classes are distinct. For a weighted shift W that is k-expansive for all k (that is, completely hyperexpansive) we obtain results for k-hyperexpansivity of back step extensions of W. In addition, we discuss the completely hyperexpansive completion problem which is parallel to Stampfli's subnormal completion problem.     

Note on group distance magic complete bipartite graphs

A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ? from V to an Abelian group Γ of order n such that the weight $w(x) = \sum\nolimits_{y \in N_G (x)} {\ell (y)}$ of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ? _p -distance magic. Moreover we show that if p ≡ 2 (mod 4) and k is even, then there does not exist a group Γ of order p such that there exists a Γ-distance labeling for a k-partite complete graph of order p. We also prove that K _m,n is a group distance magic graph if and only if n + m ? 2 (mod 4).     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

Rank-k-preservers and preservers of sets of ranks

Let T be a linear transformation on the set of m × n matrices with entries in an algebraically closed field. If T maps the set of all matrices whose rank is k into itself, and if$\text{n?}\text{3}\text{k}\text{2}$, then the rank of A is the rank of T(A) for every m × n matrix.     

Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.