Discrete Mathematics

We study the trace reconstruction problem for spider graphs. Let n be the number of nodes of a spider and d be the length of each leg, and suppose that we are given independent traces of the spider from a deletion channel in which each ...

Let p be a prime and F p be a finite field of p elements. For a 1 , . . . , a k , b ∈ F p, let N F p ( a 1 , . . . , a n , b ) denote the number of the solutions ( x 1 , . . . , x n ) ∈ F p n to the following linear equations ...

The notion of a descent polynomial, a function in enumerative combinatorics that counts permutations with specific properties, enjoys a revived recent research interest due to its connection with other important notions in ...

For any odd integer n ≥ 3 a board (of size n) is a square array of n × n positions with a simple rule of how to move between positions. The goal of the game we introduce is to find a path from the upper left corner of a board to the ...

Let D be a simple digraph with n vertices and a arcs having eigenvalues z 1 , z 2 , … , z n. The eigenvalue with largest modulus is called spectral radius of D. The energy of D is defined as E ( D ) = ∑ i = 1 n | R e ( z i ) |, where R ...

In the 7-vertex triangulation of the torus, the 14 triangles can be partitioned as T 1 ⊔ T 2, such that each T i represents the lines of a copy of the Fano plane P G ( 2 , F 2 ). We generalize this observation by constructing, for each ...

Let k , a , b be positive integers with a + b = k. A k-uniform hypergraph is called an ( a , b )-cycle if there is a partition ( A 0 , B 0 , A 1 , B 1 , … , A t − 1 , B t − 1 ) of the vertex set with | A i | = a, | B i | = b such that ...

Let K n , m be an edge-colored complete bipartite graph with 1 ≤ n ≤ m and Δ mon ( K n , m ) be the number of the leaves of a maximum monochromatic star in K n , m. In this paper, we show that if Δ mon ( K n , m ) ≤ n − 2 k + 1, then K ...

New s-extremal extremal unimodular lattices in dimensions 38, 40, 42 and 44 are constructed from self-dual codes over F 5 by Construction A. In the process of constructing these codes, we obtain a self-dual [ 44 , 22 , 14 ] code over F ...

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Given a positive integer n and a graph G, the anti-Ramsey number a r ( n , G ) is the maximum number of colors in an edge-coloring of K n with no ...

A locating-dominating set of an undirected graph is a subset of vertices S such that S is dominating and for every u , v ∉ S, the neighbourhood of u and v on S are distinct (i.e. N ( u ) ∩ S ≠ N ( v ) ∩ S). Locating-dominating sets ...

We show that the average order of a dominating set of a forest graph G on n vertices with no isolated vertices is at most 2 n / 3. Moreover, the equality is achieved if and only if every non-leaf vertex of G is a support vertex with ...

A k-hypertournament H consists of a pair ( V ( H ) , A ( H ) ), where V ( H ) is a non-empty finite set of vertices and A ( H ) contains exactly one permutation of S as an arc for all k-subsets S of V ( H ). The irregularity of ...

Crapo found that single-element extensions of matroid are equivalent to modular cuts. This paper will study the single-element extension and co-extension of a matroid and establish the upper semi-continuity for the signless ...

Let F q be a finite field and t be a positive integer. We first generalize the construction of algebraic-geometric codes to the setting of F q-linear F q t-codes. Then we show that such codes arising from the projective line yield MDS (...

In this paper we introduce the notion of l k -convexity, a natural restriction of the monophonic convexity. Let G be a graph and k ≥ 2 an integer. A subset S ⊆ V ( G ) is l k -convex if and only if for any ...

The convex hull of a ball with an exterior point is called a spike (or cap). A union of finitely many spikes of a ball is called a spiky ball. If a spiky ball is convex, then we call it a cap body. In this note we upper bound the ...

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 ...

This paper generalizes the concept of SA-homotopy in finite topological adjacency category, which is introduced in our previous work, to graph category and discusses its properties. We prove that every SA-strong deformation retract of ...

An r-uniform hypergraph is linear if every two edges intersect in at most one vertex. Given a family of r-uniform hypergraphs F, the linear Turán number exr l i n ( n , F ) is the maximum number of edges of a linear r-uniform ...

The chain theorem of Tutte states that every 3-connected graph can be constructed from a wheel W n by repeatedly adding edges and splitting vertices. It is not difficult to prove the following strengthening of this theorem: every non-...

By giving previously unknown a pair of orthogonal orthomorphisms of cyclic groups of order 18 t + 9 for any positive integer t, we complete the existence spectrum of a pair of orthogonal orthomorphisms of cyclic groups. As a corollary, ...

Following recent work by Kollár and Sarnak, we study gaps in the spectra of large connected cubic and quartic graphs with minimum spectral gap. We focus on two sequences of graphs, denoted Δ n and Γ n which are more ‘symmetric’ ...

An edge (vertex) cut X of G is r-essential if G − X has two components each of which has at least r edges. A graph G is r-essentially k-edge-connected (resp. k-connected) if it has no r-essential edge (resp. vertex) cuts of size less ...

The independence equivalence class of a graph G is the set of graphs that have the same independence polynomial as G. A graph whose independence equivalence class contains only itself, up to isomorphism, is independence unique. Beaton, ...

A thrackle is a graph drawing in which every pair of edges meets exactly once. Conway's Thrackle Conjecture states that the number of edges of a thrackle cannot exceed the number of its vertices. Cairns et al. (2015) [1] prove that the ...

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of its Laplacian matrix. In this paper, we determine the graphs whose line graphs achieve the smallest ...

A mixed graph is said to be integral if all the eigenvalues of its Hermitian adjacency matrix are integers. The mixed circulant graph Circ ( Z n , C ) is a mixed graph on the vertex set Z n and edge set { ( a , b ) : b − ...

We establish a generalized Ihara zeta function formula for simple graphs with bounded degree. This is a generalization of the formula obtained by G. Chinta, J. Jorgenson and A. Karlsson from vertex-transitive graphs.