Discrete Applied Mathematics

For an arbitrary invariant ρ ( G ) of a graph G the ρ-vertex stability number vs ρ ( G ) (ρ-edge stability number es ρ ( G )) is the minimum number of vertices (edges) whose removal results in a graph H ⊆ G with ρ ( H ) ≠ ρ ( G ). If such a ...

The Maker–Breaker domination game is played on a graph G by two players, called Dominator and Staller, who alternately choose a vertex that has not been played so far. Dominator wins the game if his moves form a dominating set. Staller wins if ...

Let τ ( G ) and τ G ( e ) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G ( e ) = τ G ( e ) / τ ( G ) is called the spanning tree edge density, or simply density, of e. ...

The concept of jump system, introduced by Bouchet and Cunningham (1995), is a set of integer points satisfying a certain exchange property. We consider the minimization of a separable convex function on a jump system. It is known that the problem ...

Let K p be a complete graph of order p ≥ 2. A K p-free k-coloring of a graph H is a partition of V ( H ) into V 1 , V 2 … , V k such that H [ V i ] does not contain K p for each i ≤ k. In 1977 Borodin and Kostochka conjectured that any graph H ...

Given two non-empty t-uniform hypergraphs G ( t ) , H ( t ) and a positive integer k, the hypergraph Gallai–Ramsey number gr k G ( t ) : H ( t ) is defined as the minimum positive integer N such that for all n ≥ N, every k-hyperedge-coloring of t-...

Let N ≥ 2 be an integer, a (1, N)-periodic graph G is a periodic graph whose vertices can be partitioned into two sets V 1 = { v ∣ σ ( v ) = v } and V 2 = { v ∣ σ i ( v ) ≠ v for any 1 < i < N }, where σ is an automorphism with order N of G. The ...

Consider an arbitrary n-dimensional lattice Λ such that Z n ⊂ Λ ⊂ Q n. Such lattices are called rational and can always be obtained by adding m ≤ n rational vectors to Z n. The defect d ( E , Λ ) of the standard basis E of Z n (n unit vectors ...

In this paper, we establish some relations between irreducible polynomials over a finite field F q and its quadratic extension F q 2. First we consider a relation between the numbers of irreducible polynomials of a fixed degree over F q and F q 2,...

The Eulerian polynomials A n ( x ) give the distribution of descents over permutations. It is also known that the distribution of descents over stack-sortable permutations (i.e. permutations sortable by a certain algorithm whose internal storage ...

A strong edge-coloring of a graph G is a proper edge-coloring such that any two edges with distance at most 2 receive different colors. The strong chromatic index of G, denoted by χ s ′ ( G ), is the least possible number of colors in a strong ...

Let P n and K n denote the induced path and complete graph on n vertices, respectively. The kite is the graph obtained from a P 4 by adding a vertex and making it adjacent to all vertices in the P 4 except one vertex with degree 1. A graph is (P ...

With the fast development of quantum computer technology, one has to focus on the security of information running in real networks. Topological coding is a technology of basic topological structure, number theory and algebra has potential ...

The Wiener index, W ( G ), of a connected graph G is the sum of distances between its vertices. In 2021, Akhmejanova et al. posed the problem of finding graphs G with large R m ( G ) = | { v ∈ V ( G ) ∣ W ( G ) − W ( G − v ) = m ∈ Z } | / | V ( G ...

A graph G is k-vertex-critical if χ ( G ) = k but χ ( G − v ) < k for all v ∈ V ( G ) where χ ( G ) denotes the chromatic number of G. We show that there are only finitely many k-vertex-critical ( P 3 + ℓ P 1 )-free graphs for all k ≥ 1 and all ℓ ...

Given a digraph D, a diclique is a maximal pair of vertex sets ( X , Y ) satisfying x ∈ X , y ∈ Y ⟹ x → y. The diclique digraph of D, K ⃗ ( D ), has the dicliques of D as vertices two of them being adjacent, ( X , Y ) → ( X ′ , Y ′ ), if and only ...

We introduce and enumerate weighted α-distanced words. We show their connection to the unified Apostol-type polynomials and provide combinatorial proofs of certain identities.

A rainbow-free coloring of a k-uniform hypergraph H is a vertex-coloring which uses k colors but with the property that no edge of H attains all colors. Koerkamp and Z̆ivný showed that p = ( k − 1 ) ( log n ) / n is the threshold function for the ...

A family of sets is called a star if there exists an element (a center) in each of its sets. Given a graph G and an integer r ⩾ 1 , let I r ( G ) be the family of independent sets of size r of G . A star S of I r ( G ) is maximum if no star of I ...

The atom-bond sum-connectivity index (A B S index) of a graph G = ( V , E ) is defined as A B S ( G ) = ∑ ξ ζ ∈ E ( G ) d ξ + d ζ − 2 d ξ + d ζ , where d ξ represents the degree of vertex ξ ∈ V. By using A B S index, the heat of formation of ...