Search

A graph G of order n is said to be k -factor-critical for integers 1 ≤ k < n , if the removal of any k vertices results in a graph with a perfect matching. A k -factor-critical graph G is called minimal if for any edge e ∈ E (G) , G − e is not k -factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimal k -factor-critical graph of order n has minimum degree k + 1 and confirmed it for k = 1 , n − 2 , n − 4 and n − 6. By using a novel approach, we have confirmed it for k = n − 8 in a previous paper. Continuing with this method, we confirm the conjecture when k = n − 10 in this paper. [ABSTRACT FROM AUTHOR]

Let k be a positive integer and let G = (V (G) , E (G)) be a graph. A vertex set D is a k -component dominating set of G if every vertex outside D in G has a neighbor in D and every component of the subgraph G [ D ] of G induced by D contains at least k vertices. The minimum cardinality of a k -component dominating set of G is the k -component domination number γ k (G) of G. It was conjectured that if G is a connected graph of order n ≥ k + 1 , and minimum degree at least 2, then γ k (G) ≤ 2 k n 2 k + 3 except for a finite set of graphs. In this paper, we focus on the parameter γ 3 (G) of G. We first determine the exact values of 3-component domination numbers of paths and cycles. We then proceed to show that if G is a connected graph of order n with minimum degree at least 2 and maximum degree at most 3, then γ 3 (G) ≤ 2 n 3 , unless G is one of seven special graphs. This result provides positive support for the conjecture and also generalizes a result by Alvarado et al. (2016) [1]. [ABSTRACT FROM AUTHOR]

Let k ≥ 2 be an integer. We say that a graph G is (K 2 ∪ k K 1) -free if it does not contain K 2 ∪ k K 1 as an induced subgraph. Recently, Shi and Shan conjectured that every 1-tough and 2 k -connected (K 2 ∪ k K 1) -free graph is hamiltonian. In this paper, we solve this conjecture by proving that every 1-tough and k -connected (K 2 ∪ k K 1) -free graph with minimum degree at least 3 (k − 1) 2 is hamiltonian or the Petersen graph. [ABSTRACT FROM AUTHOR]

Let m 1 , m 2 , n be three positive integers, m 1 < m 2 ≤ n. A (m 1 , m 2) -near-Skolem sequence of order n with defects m 1 and m 2 is a sequence S = (s 1 , s 2 , ⋯ , s 2 n − 4) of 2 n − 4 positive integers which satisfies the following two conditions: (1) For every k ∈ { 1 , 2 , ⋯ , n } ∖ { m 1 , m 2 } there are exactly two elements s i , s j ∈ S , such that s i = s j = k ; (2) If s i = s j = k then | j − i | = k. In this paper, we mainly show the existence of (m 1 , m 2) -near-Skolem sequences with m 2 − m 1 ≤ 2. We also prove that there is a (m 1 , m 2) -near-Skolem sequence when n ≥ 3 m 2 + 1. [ABSTRACT FROM AUTHOR]

Cohen et al. conjectured that, for each oriented cycle C , there exists an integer f (C) such that any f (C) -chromatic strong digraph contains a subdivision of C as a subdigraph. In the same paper, Cohen et al. proved this conjecture for cycles with two blocks by showing that the chromatic number of strong digraphs that include no subdivision of a cycle with two blocks, with lengths of k 1 and k 2 , is bounded from above by O ((k 1 + k 2) 4). More recently, Kim et al. improved this upper bound to O ((k 1 + k 2) 2) for the class of strong digraphs and to O (k 1 + k 2) for the class of Hamiltonian digraphs. In this paper, we confirm Cohen et al.'s conjecture for Hamiltonian digraphs. We demonstrate a stronger version by showing that every 3 n -chromatic Hamiltonian digraph contains a subdivision for every oriented cycle of order n. [ABSTRACT FROM AUTHOR]

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]

For two positive integers a and b with a ≤ b , an [ a , b ] -factor of a graph is a spanning subgraph of the graph such that the degree of each vertex in the subgraph is between a and b. Recently, Cho, Hyun, O and Park posed a conjecture for the existence of [ a , b ] -factors in graphs under a spectral radius condition. We confirm this conjecture in this paper. [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]

Let G be a finite group and Irr (G) be the set of all complex irreducible characters of G. The character-graph Δ (G) associated to G , is a graph whose vertex set is the set of primes which divide the degrees of some characters in Irr (G) and two distinct primes p and q are adjacent in Δ (G) if the product pq divides χ (1) , for some χ ∈ Irr (G). Tong-Viet posed the conjecture that if Δ (G) is k -regular for some integer k ⩾ 2 , then Δ (G) is either a complete graph or a cocktail party graph. In this paper, we show that his conjecture is true for all regular character-graphs whose eigenvalues are in the interval [ − 2 , ∞). [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 2020, Bennett, Carrillo, Machacek and Sagan gave a polynomial generalization of the Narayana numbers and conjectured that these polynomials have positive integer coefficients for 1 ≤ k ≤ n and for n ≥ 1. In 2020, Sagan and Tirrell used a powerful algebraic method to prove this conjecture (in fact, they extend and prove the conjecture for more than just the type A case). In this paper we give a combinatorial proof of a formula satisfied by the Lucas-Narayana polynomials described by Bennett et al. This gives a combinatorial proof that these polynomials have positive integer coefficients. A corollary of our main result establishes a parallel theorem for the FiboNarayana numbers N n , k , F , providing a combinatorial proof of the conjecture that these are positive integers for n ≥ 1. [ABSTRACT FROM AUTHOR]

Euler's identity equates the number of partitions of any non-negative integer n into odd parts and the number of partitions of n into distinct parts. Beck conjectured and Andrews proved the following companion to Euler's identity: the excess of the number of parts in all partitions of n into odd parts over the number of parts in all partitions of n into distinct parts equals the number of partitions of n with exactly one even part (possibly repeated). Beck's original conjecture was followed by generalizations and so-called "Beck-type" companions to other identities. In this paper, we establish a collection of Beck-type companion identities to the following result mentioned by Lehmer at the 1974 International Congress of Mathematicians: the excess of the number of partitions of n with an even number of even parts over the number of partitions of n with an odd number of even parts equals the number of partitions of n into distinct, odd parts. We also establish various generalizations of Lehmer's identity, and prove related Beck-type companion identities. We use both analytic and combinatorial methods in our proofs. [ABSTRACT FROM AUTHOR]

Let d ≥ 4 be an fixed integer. Lee, Loh and Sudakov (2016) [17] conjectured that every directed graph D with m arcs and minimum outdegree at least d admits a bipartition V (D) = V 1 ∪ V 2 such that min ⁡ { e (V 1 , V 2) , e (V 2 , V 1) } ≥ (d − 1 2 (2 d − 1) + o (1)) m , where e (V i , V j) denote the number of arcs in D from V i to V j for { i , j } = { 1 , 2 }. Let K d , 2 → denote the directed graph obtained by orienting each edge of a bipartite graph K 2 , d from the part of size d to the other part. In this paper, we show that the conjecture holds for K d , 2 → -free directed graphs. Then, we prove that the conjecture holds under the additional condition that the minimum indegree is also at least d − 1 , which improves a result given by Hou, Ma, Yu and Zhang. [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]

In 1967 Harary, Hedetniemi, and Prins showed that every graph G admits a complete t -coloring for every t with χ (G) ≤ t ≤ ψ (G) , where χ (G) denotes the chromatic number of G and ψ (G) denotes the achromatic number of G which is the maximum number r for which G admits a complete r -coloring. Recently, Edwards and Rza̧żewski (2020) showed that this result fails for hypergraphs by proving that for every integer k with k ≥ 9 , there exists a k -uniform hypergraph H with a complete χ (H) -coloring and a complete ψ (H) -coloring, but no complete t -coloring for some t with χ (H) < t < ψ (H). They also asked whether there would exist such an example for 3-uniform hypergraphs and posed another problem to strengthen their result. In this paper, we generalize their result to all cases k with k ≥ 3 and settle their problems by giving several examples of 3-uniform hypergraphs. In particular, we disprove a recent conjecture due to Matsumoto and Ohno (2020) who suggested a special family of 3-uniform hypergraph to satisfy the desired interpolation property. [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]

The conjecture, still widely open, posed by Marco Buratti, Peter Horak and Alex Rosa states that a list L of v − 1 positive integers not exceeding ⌊ v 2 ⌋ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set { 0 , 1 , ... , v − 1 } if and only if, for every divisor d of v , the number of multiples of d appearing in L is at most v − d. In this paper we present new methods that are based on linear realizations and can be applied to prove the validity of this conjecture for a vast choice of lists. As example of their flexibility, we consider lists whose underlying set is one of the following: { x , y , x + y } , { 1 , 2 , 3 , 4 } , { 1 , 2 , 4 , ... , 2 x } , { 1 , 2 , 4 , ... , 2 x , 2 x + 1 }. We also consider lists with many consecutive elements. [ABSTRACT FROM AUTHOR]

Let G be a t -uniform hypergraph, and let c (G) denote the cyclic index of the adjacency tensor of G. Let m , s be positive integers such that s ≥ 2 and m = s t. The generalized power G m , s of G is obtained from G by blowing up each vertex into an s -set and preserving the adjacency relation. It was conjectured that c (G m , s) = s ⋅ c (G). In this paper, by using a matrix equation over Z m that characterizes the spectral symmetry or cyclic index of an m -uniform hypergraph, we give an equivalent condition for the equality in the conjecture. Finally we show that the conjecture is false by a counterexample. [ABSTRACT FROM AUTHOR]

In 2002, Björner and de Longueville showed the neighborhood complex of the 2-stable Kneser graph K G (n , k) 2 − s t a b has the same homotopy type as the (n − 2 k) -sphere. A short time ago, an analogous result about the homotopy type of the neighborhood complex of almost s -stable Kneser graph has been announced by the second author. Combining this result with the famous Lovász's topological lower bound on the chromatic number of graphs yielded a new way for determining the chromatic number of these graphs which was determined a bit earlier by Chen. In this paper we present a common generalization of the mentioned results. For given an integer vector s → = (s 1 , ... , s k) , first we define s → -stable Kneser graph K G (n , k) s → − s t a b as an induced subgraph of the Kneser graph K G (n , k). Then, we show that the neighborhood complex of K G (n , k) s → − s t a b has the same homotopy type as the n − ∑ i = 1 k − 1 s i − 2 -sphere for some specific values of the parameter s →. In particular, this implies that χ K G (n , k) s → − s t a b = n − ∑ i = 1 k − 1 s i for those parameters. Moreover, as a simple corollary of this result, we give a lower bound on the chromatic number of 3-stable Kneser graphs which is just one less than the number conjectured in this regard. [ABSTRACT FROM AUTHOR]

Let r be a positive integer. The Bermond–Thomassen conjecture states that, a digraph of minimum out-degree at least 2 r − 1 contains r vertex-disjoint directed cycles. A digraph D is called a local tournament if for every vertex x of D , both the out-neighbours and the in-neighbours of x induce tournaments. Note that tournaments form the subclass of local tournaments. In this paper, we verify that the Bermond–Thomassen conjecture holds for local tournaments. In particular, we prove that every local tournament D with δ + (D) ≥ 2 r − 1 contains r disjoint cycles C 1 , C 2 , ... , C r , satisfying that either C i has the length at most 4 or is a shortest cycle of the original digraph of D − C 1 − ... − C i − 1 for 1 ≤ i ≤ r. [ABSTRACT FROM AUTHOR]

For two s -uniform hypergraphs H and F , the Turán number e x s (H , F) is the maximum number of edges in an F -free subgraph of H. Let s , r , k , n 1 , ... , n r be integers satisfying 2 ≤ s ≤ r and n 1 ≤ n 2 ≤ ⋯ ≤ n r . De Silva, Heysse and Young determined e x 2 (K n 1 , ... , n r , k K 2) and De Silva, Heysse, Kapilow, Schenfisch and Young determined e x 2 (K n 1 , ... , n r , k K r). In this paper, as a generalization of these results, we consider three Turán-type problems for k disjoint cliques in r -partite s -uniform hypergraphs. First, we consider a multi-partite version of the Erdős matching conjecture and determine e x s (K n 1 , ... , n r (s) , k K s (s) ) for n 1 ≥ s 3 k 2 + s r. Then, using a probabilistic argument, we determine e x s (K n 1 , ... , n r (s) , k K r (s) ) for all n 1 ≥ k. Recently, Alon and Shikhelman determined asymptotically, for all F , the generalized Turán number e x 2 (K n , K s , F) , which is the maximum number of copies of K s in an F -free graph on n vertices. Here we determine e x 2 (K n 1 , ... , n r , K s , k K r) with n 1 ≥ k and n 3 = ⋯ = n r . Utilizing a result on rainbow matchings due to Glebov, Sudakov and Szabó, we determine e x 2 (K n 1 , ... , n r , K s , k K r) for all n 1 , ... , n r with n 4 ≥ r r (k − 1) k 2 r − 2 . [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]