Discrete Mathematics

We provide a necessary and sufficient condition for stars to be the largest cross-intersecting families.

Let R be a finite commutative chain ring and γ be a fixed generator of the maximal ideal of R. For any unit w in R, ( 1 + w γ )-constacyclic codes over R as a generalization of negacyclic codes over Z 4 are a class of important linear ...

A major line of research is discovering Ramsey-type theorems, which are results of the following form: given a graph parameter ρ, every graph G with sufficiently large ρ ( G ) contains a particular induced subgraph H with large ρ ( H )...

We define a method for edge coloring signed graphs and what it means for such a coloring to be proper. Our method has many desirable properties: it specializes to the usual notion of edge coloring when the signed graph is all-negative, ...

Let S | T be a Galois extension of finite chain rings and consider H as its group of ring-automorphisms fixing the elements in T. In this paper we determine the stabilizer under such a group of any S-linear code. Using the so called ...

A Mendelsohn triple system MTS( v , b ) is a collection of b cyclic triples (blocks) on a set of v points. It is j-balanced for j = 1 , 2 , 3 when any two points, ordered pairs, or cyclic triples (resp.) are contained in the same or ...

A (proper) n-coloring c : V ( G ) → { 1 , … , n } of a graph G on a surface is a (proper) facial t -complete n -coloring if every t-tuple of colors appears on the boundary of some ...

Building on a bijection of Vandervelde, we enumerate certain unimodal sequences whose alternating sum equals zero. This enables us to refine the enumeration of strict partitions with respect to the number of parts and the BG-rank.

In Parts I–III we showed that the number of ways to place q nonattacking queens or similar chess pieces on an n × n chessboard is a quasipolynomial function of n whose coefficients are essentially polynomials in q.

In this ...

In 1976, Steinberg conjectured that every planar graph without 4-cycles and 5-cycles is 3-colorable, and in 2003, Borodin and Raspaud further conjectured that every planar graph without 5-cycles and K 4 − is 3-colorable. Both ...

Let n , s be integers, n ≥ 2 ( s + 1 ) ≥ 4. Let F , G ⊂ [ n ] 2 be two graphs. We determine the exact maximum of | F | + | G | subject to the condition that there is no matching of size s + 1 contained in F ∪ G and having non-empty ...

With a computer-aided approach based on connection with equitable partitions, we establish the uniqueness of the orthogonal array OA ( 1536 , 13 , 2 , 7 ), constructed in Fon-Der-Flaass (2017) as an equitable partition of the 13-cube ...

A well known result in the analysis of finite metric spaces due to Gromov says that given any metric space ( X , d X ) there exists a tree metric t X on X such that | d X − t X | ∞ is bounded above by twice hyp ( X ) ⋅ ...

One of the fundamental ways to construct De Bruijn sequences is by using a shift-rule. A shift-rule receives a word as an argument and computes the symbol that appears after it in the sequence. An optimal shift-rule for an ( n , k )-De ...

We say that a sequence ( x n ) n ∈ N in [ 0 , 1 ) has Poissonian pair correlations if lim N → ∞ 1 N # 1 ≤ l ≠ m ≤ N : ‖ x l − x m ‖ ≤ s N = 2 s for every s ≥ 0. The ...

In this paper, regular endomorphisms of a tree T are explored. We give conditions under which the regular endomorphisms of the tree form a monoid.

The classical Ore’s Theorem states that every graph G of order n ≥ 3 with σ 2 ( G ) ≥ n is hamiltonian, where σ 2 ( G ) = min { d G ( x ) + d G ( y ) : x , y ∈ V ( G ) , x ≠ y , x y ∉ E ( G ) }. Recently, Ferrara, Jacobson and Powell (...

The status of a vertex x in a graph is the sum of the distances between x and all other vertices. Let G be a connected graph. The status sequence of G is the list of the statuses of all vertices arranged in nondecreasing order. G is ...

A k-attack on a graph G is a set of k distinct vertices { a 1 , … , a k } which are said to be under attack. A k-attack A can be countered or defended by a subset of defender vertices X if and only if there exists an injective function ...

A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one another edge. In this work we prove that each 1-planar graph of minimum degree at least 3 contains an edge with degrees of its endvertices ...

Given a convex polygon of n sides, one can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the ...

In the paper we investigate the structure of i-components of two classes of codes: the Kerdock codes and the duals of the linear uniformly packed codes with parameters of the primitive double-error-correcting BCH code. We prove that ...

In this paper, claims by Lemmens and Seidel in 1973 about equiangular sets of lines with angle 1 ∕ 5 are proved by carefully analyzing pillar decomposition, with the aid of the uniqueness of two-graphs on 276 vertices. The Neumann ...

The signless Laplacian Estrada index of a graph G is defined as S L E E ( G ) = ∑ i = 1 n e q i, where q 1 , q 2 , … , q n are the eigenvalues of the signless Laplacian matrix of G. A k-tree is either a complete graph on k vertices or ...

A positive integer n is a super totient number if the set of positive integers less than n and relatively prime to n can be partitioned into two sets of equal sum. In this article, we give a complete classification of super totient ...

Imitating the binary inducibility, a recently introduced invariant of binary trees (Czabarka et al., 2017), we initiate the study of the inducibility of d-ary trees (rooted trees whose vertex outdegrees are bounded from above by d ≥ 2)...

In 1991, Shalaby conjectured that any additive group Z n, where n ≡ 1 or 3 (mod 8) and n ≥ 11, admits a strong Skolem starter and constructed these starters of all admissible orders 11 ≤ n ≤ 57. Only finitely many strong Skolem ...

A complete c-colouring of a graph is a proper colouring in which every pair of distinct colours from [ c ] = { 1 , 2 , … , c } appears as the colours of endvertices of some edge. We consider the following generalisation of this concept ...

In this paper, we state and prove two Fraïssé-style results that cover existence and uniqueness properties for twelve of the eighteen different notions of homomorphism–homogeneity as introduced by Lockett and Truss, and provide forward ...