The partition of a strong tournament

A digraph T is strong if for every pair of vertices u and v there exists a directed path from u to v and a directed path from v to u. Denote the in-degree and out-degree of a vertex v of T by d^-(v) and d⁺(v), respectively. We define δ^-(T)=min_vV(T){d^-(v)} and δ⁺(T)=min_vV(T){d⁺(v)}. Let T₀ be a 7-tournament which contains no transitive 4-subtournament. In this paper, we obtain some conditions on a strong tournament which cannot be partitioned into two cycles. We show that a strong tournament T with n6 vertices such that TT₀ and max{δ⁺(T),δ^-(T)}3 can be partitioned into two cycles. Finally, we give a sufficient condition for a tournament to be partitioned into k cycles.     

Proof of a Lin-Peng-Toh's conjecture on an Andrews-Beck type congruence

Recently, Andrews proved two conjectures of Beck related to ranks of partitions. Very recently, Chern established some results on weighted rank and crank moments and proved many Andrews-Beck type congruences. Motivated by Andrews and Chern's work, Lin, Peng and Toh proved a number of Andrews-Beck type congruences for k-colored partitions. At the end of their paper, Lin, Peng and Toh posed several conjectures on Andrews-Beck type congruences. In this paper, we confirm one of those conjectures based on some q-series identities.     

Squaring a tournament: A proof of Dean's conjecture

Let the square of a tournament be the digraph on the same nodes with arcs where the directed distance in the tournament is at most two. This paper verifies Dean's conjecture: any tournament has a node whose outdegree is at least doubled in its square. © 1996 John Wiley & Sons, Inc.     

Proof of a conjecture of Metsch

In this paper we prove a conjecture of Metsch about the maximum number of lines intersecting a pointset in PG(2,q), presented at the conference “Combinatorics 2002”. As a consequence, we give a short proof of the famous Jamison, Brouwer and Schrijver bound on the size of the smallest affine blocking set in AG(2,q).     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

On degree sum conditions for 2-factors with a prescribed number of cycles

For a vertex subset $X$ of a graph $G$, let ${\Delta }_t\left(X\right)$ be the maximum value of the degree sums of the subsets of $X$ of size $t$. In this paper, we prove the following result: Let $k,m$ be positive integers, and let $G$ be an $m$-connected graph of order $n\ge 5k?2$. If ${\Delta }_2\left(X\right)\ge n$ for every independent set $X$ of size $?m∕k?+1$ in $G$, then $G$ has a 2-factor with exactly $k$ cycles. This is a common extension of the results obtained by Brandt et al. (1997) and Yamashita (2008), respectively.     

Proof of a conjecture of Fiedler and Markham

Let A be an n×n nonsingular M-matrix. For the Hadamard product AA⁻¹, M. Fiedler and T.L. Markham conjectured in [Linear Algebra Appl. 10l (1988) 1] that q(AA⁻¹)2/n, where q(AA⁻¹) is the smallest eigenvalue (in modulus) of AA⁻¹. We considered this conjecture in [Linear Algebra Appl. 288 (1999) 259] having observed an incorrect proof in [Linear Algebra Appl. 144 (1991) 171] and obtained that q(AA⁻¹)(2/n)(n−1)/n. The present paper gives a proof for this conjecture.     

Proof of a conjecture of Alan Hartman

A tree T is said to be bad, if it is the vertex‐disjoint union of two stars plus an edge joining the center of the first star to an end‐vertex of the second star. A tree T is good, if it is not bad. In this article, we prove a conjecture of Alan Hartman that, for any spanning tree T of K_2m, where m ≥ 4, there exists a (2m − 1)‐edge‐coloring of K_2m such that all the edges of T receive distinct colors if and only if T is good. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 7–17, 1999     

Proof of a conjecture on game domination

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b‐dimensional cube is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b‐dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line—i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number ψ(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least ?log₂ψ(G)?. In this article, we show that for an interval graph G ?log₂ψ(G)??cub(G)??log₂ψ(G)?+2. It is not clear whether the upper bound of ?log₂ψ(G)?+2 is tight: till now we are unable to find any interval graph with cub(G)>?log₂ψ(G)?. We also show that for an interval graph G, cub(G)??log₂α?, where α is the independence number of G. Therefore, in the special case of ψ(G)=α, cub(G) is exactly ?log₂α₂?. The concept of cubicity can be generalized by considering boxes instead of cubes. A b‐dimensional box is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k‐dimensional boxes. It is clear that box(G)?cub(G). From the above result, it follows that for any graph G, cub(G)?box(G)?log₂α?. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323–333, 2010     

Proof of a conjecture on monomial graphs

Let e be a positive integer, p be an odd prime, $q=p^e$, and ${\mathbb{F}}_q$ be the finite field of q elements. Let $f,g\in {\mathbb{F}}_q[X,Y]$. The graph $G_q(f,g)$ is a bipartite graph with vertex partitions $P={\mathbb{F}}_q^3$ and $L={\mathbb{F}}_q^3$, and edges defined as follows: a vertex $(p)=(p_1,p_2,p_3)\in P$ is adjacent to a vertex $[l]=[l_1,l_2,l_3]\in L$ if and only if $p_2+l_2=f(p_1,l_1)$ and $p_3+l_3=g(p_1,l_1)$. If $f=XY$ and $g=X{Y}^2$, the graph $G_q(XY,X{Y}^2)$ contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs $G_q(f,g)$ containing no cycles of length less than eight and not isomorphic to the graph $G_q(XY,X{Y}^2)$, even without requiring them to be edge-transitive. So far, no such graphs $G_q(f,g)$ have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture.     

Proof of a conjecture of V. Nikiforov

Using analytical tools, we prove that for any simple graph G on n vertices and its complement [`(G)]\bar G the inequality $\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1$\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1 holds, where μ(G) and m( [`(G)] )\mu \left( {\bar G} \right) denote the greatest eigenvalue of adjacency matrix of the graphs G and [`(G)]\bar G respectively.     

Proof of a conjecture of Gross concerning fix-points

Research performed as a Feodor Lynen Research Fellow of the Alexander von Humboldt Foundation at Cornell University     

Proof of a conjecture of S. Chowla

Let θ(k, p) be the least s such that the congruence $\text{x}{}_1{}^{\mathrm{k}}\text{+ … + x}{}_{\mathrm{s}}{}^{\mathrm{k}}\text{≡ 0(}\text{mod}\text{p)}$ has a nontrivial solution. Let θ(k) = {max θ(k, p)| p > 1 + 2k}. The purpose of this note is to prove the following conjecture of S. Chowla: $\text{θ(k) = O(k}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext><mtext>+?</mtext>}}\text{)}$.     

Proof of a conjecture about rotation symmetric functions

Rotation symmetric Boolean functions have important applications in the design of cryptographic algorithms. We prove the conjecture about rotation symmetric Boolean functions (RSBFs) of degree 3 proposed in Cusick and St?nic? (2002) [2] and its generalization, thus the nonlinearity of such functions is determined.