Search

Abstract For a given pair of two graphs (F , H) , let R (F , H) be the smallest positive integer r such that for any graph G of order r , either G contains F as a subgraph or the complement of G contains H as a subgraph. Baskoro, Broersma and Surahmat (2005) conjectured that R (F ℓ , K n) = 2 ℓ (n − 1) + 1 for ℓ ≥ n ≥ 3 , where F ℓ is the join K 1 + ℓ K 2 of K 1 and ℓ K 2. In this paper, we prove that this conjecture is true for the case n = 6. [ABSTRACT FROM AUTHOR]

Abstract Let G be an additive finite abelian group with exponent exp (G) = n. For any positive integer k , the k th Erdős–Ginzburg–Ziv constant s k n (G) is defined as the smallest positive integer t such that every sequence S in G of length at least t has a zero-sum subsequence of length k n. It is easy to see that s k n (C n r) ≥ (k + r) n − r where n , r ∈ N. Kubertin conjectured that the equality holds for any k ≥ r. In this paper, we prove the following results: • [(1)] For every positive integer k ≥ 6 , we have s k n (C n 3) = (k + 3) n + O (n ln n). • [(2)] For every positive integer k ≥ 18 , we have s k n (C n 4) = (k + 4) n + O (n ln n). • [(3)] For n ∈ N , assume that the largest prime power divisor of n is p a for some a ∈ N. Forany fixed r ≥ 5 , if p t ≥ r for some t ∈ N , then for any k ∈ N we have s k p t n (C n r) ≤ (k p t + r) n + c r n ln n , where c r is a constant that depends on r. Our results verify the conjecture of Kubertin asymptotically in the above cases. [ABSTRACT FROM AUTHOR]

Abstract Given a positive integer p and a graph G with degree sequence d 1 , ... , d n , we define e p (G) = ∑ i = 1 n d i p. Caro and Yuster introduced a Turán-type problem for e p (G) : Given a positive integer p and a graph H , determine the function ex p (n , H) , which is the maximum value of e p (G) taken over all graphs G on n vertices that do not contain H as a subgraph. Clearly, ex 1 (n , H) = 2 ex (n , H) , where ex (n , H) denotes the classical Turán number. Caro and Yuster determined the function ex p (n , P ℓ) for sufficiently large n , where p ≥ 2 and P ℓ denotes the path on ℓ vertices. In this paper, we generalise this result and determine ex p (n , F) for sufficiently large n , where p ≥ 2 and F is a linear forest. We also determine ex p (n , S) , where S is a star forest; and ex p (n , B) , where B is a broom graph with diameter at most six. [ABSTRACT FROM AUTHOR]

The leaf distance of a tree is the maximum d such that the distance between any pair of leaves in the tree is at least d . Kaneko provided sufficient conditions to force the existence of a spanning tree with leaf distance at least d = 3 and conjectured that similar conditions suffice for larger d . The case when d = 4 was later proved by Kaneko, Kano, and Suzuki. In this paper, we show that when d ≥ 4 , a stronger form of this conjecture holds for graphs with independence number at most five. As an immediate corollary, we obtain that when d ≥ n ∕ 3 , this stronger version holds for all n -vertex graphs, consequently proving Kaneko’s conjecture for d ≥ n ∕ 3 . [ABSTRACT FROM AUTHOR]

Crnković (2014) introduced a self-orthogonal [ 2 q , q − 1 ] code and a self-dual [ 2 q + 2 , q + 1 ] code over the finite field F p arising from orbit matrices for Menon designs, for every prime power q , where q ≡ 1 ( mod 4 ) and p a prime dividing q + 1 2 . He showed that if q is a prime and q = 12 m + 5 , where m is a non-negative integer, then the self-dual [ 2 q + 2 , q + 1 ] code over F 3 is equivalent to a Pless symmetry code. However for other values of q , he remarked that these codes, up to his knowledge, do not belong to some previously known series of codes. In this paper, we describe an equivalence between his self-dual codes and the known codes introduced by Gaborit in 2002. On the other hand, Crnković (2014) also conjectured that if p = q + 1 2 is a prime, the self-orthogonal code and the self-dual code have minimum distance p + 3 . We disprove this conjecture by giving two counter-examples in the case of the self-orthogonal code and the self-dual code, respectively when q = 25 and p = 13 . [ABSTRACT FROM AUTHOR]

For integer k ≥ 2 and prime power q , Lazebnik and Ustimenko (1995) proposed an algebraic bipartite graph D ( k , q ) which is q -regular, edge-transitive and of large girth. Füredi et al. (1995) conjectured that D ( k , q ) has girth k + 5 for all odd k and all q ≥ 4 and, shown that this conjecture is true for the case that ( k + 5 ) / 2 divides q − 1 . Cheng et al. (2014) shown that this conjecture is true for the case that ( k + 5 ) / 2 is an arbitrary power of the characteristic of F q . In this paper, we propose a generalization for the binomial coefficients and show that this conjecture is true when ( k + 5 ) / 2 is the product of an arbitrary factor of q − 1 and an arbitrary power of the characteristic of F q . [ABSTRACT FROM AUTHOR]

In 1996, Bang-Jensen, Gutin, and Li proposed the following conjecture: If D is a strong digraph of order n where n ≥ 2 with the property that d (x) + d (y) ≥ 2 n − 1 for every pair of dominated non-adjacent vertices { x , y } , then D is hamiltonian. In this paper, we give an infinite family of counterexamples to this conjecture. In the same paper, they showed that for the above x , y , if they satisfy the condition either d (x) ≥ n , d (y) ≥ n − 1 or d (x) ≥ n − 1 , d (y) ≥ n , then D is hamiltonian. It is natural to ask if there is an integer k ≥ 1 such that every strong digraph of order n satisfying either d (x) ≥ n + k , d (y) ≥ n − 1 − k , or d (x) ≥ n − 1 − k , d (y) ≥ n + k , for every pair of dominated non-adjacent vertices { x , y } , is hamiltonian. In this paper, we show that k must be at most n − 5 and prove that every strong digraph with k = n − 4 satisfying the above condition is hamiltonian, except for one digraph on 5 vertices. [ABSTRACT FROM AUTHOR]

From an initial list of nonnegative integers, we form a Stanley sequence by recursively adding the smallest integer such that the list remains increasing and no three elements form an arithmetic progression. Odlyzko and Stanley conjectured that every Stanley sequence ( a n ) satisfies one of two patterns of asymptotic growth, with no intermediate behavior possible. Sequences of Type 1 satisfy α / 2 ≤ lim inf n → ∞ a n / n log 2 3 ≤ lim sup n → ∞ a n / n log 2 3 ≤ α , for some constant α , while those of Type 2 satisfy a n = Θ ( n 2 / log n ) . In this paper, we consider the possible values for α in the growth of Type 1 Stanley sequences. Whereas Odlyzko and Stanley considered only those Type 1 sequences for which α equals 1, we show that α can in fact be any rational number that is at least 1 and for which the denominator, in lowest terms, is a power of 3. [ABSTRACT FROM AUTHOR]

We raise the conjecture that every 3-regular digraph, except the digraphs D 7 3 , D 8 3 and D 2 n 2 for every integer n ≥ 2 , which are defined in the introduction of the paper, contains two vertex disjoint directed cycles of different lengths and give support for this conjecture by proving that every 3-regular digraph of girth 4 contains two vertex disjoint directed cycles of different lengths. [ABSTRACT FROM AUTHOR]