Discrete Mathematics, Algorithms and Applications

Given any fixed integer q ≥ 2, a q-monomial is of the format such that 1 ≤ s_j ≤ q - 1, 1 ≤ j ≤ t. q-monomials are natural generalizations of multilinear monomials. Recent research on testing multilinear monomials and q-monomials for prime q in multivariate polynomials relies on the property that Z_q is a field when q ≥ 2 is prime. When q > 2 is not prime, it remains open whether the problem of testing q-monomials can be solved in some compatible complexity. In this paper, we present a randomized O*(7.15^k) algorithm for testing q-monomials of degree k that are found in a multivariate polynomial that is represented by a tree-like circuit with a polynomial size, thus giving a positive, affirming answer to the above question. Our algorithm works regardless of the primality of q and improves upon the time complexity of the previously known algorithm for testing q-monomials for prime q > 7.

We consider the series of Fibonacci n-step numbers and a class of square matrix of order n based on Fibonacci n-step numbers with determinant +1 or -1. Thereby, we introduce a new coding theory called Fibonacci n-step coding theory and establish generalized relation among the code elements for all values of n. For n = 2, the correct ability of the method is 93.33%; for n = 3, the correct ability of the method is 99.80% and for n = 4, the correct ability of the method is 99.998%. In general, the correct ability of the method increases as n increases.

Consider a graph D and a family FI of connected edge subgraphs of D. Let GI(V, F) be the intersection graph of FI and G the overlap graph of FI. We describe polynomial time algorithms for subgraph overlap graphs G when their intersection graphs GI have specific hereditary properties. The algorithms are to find maximum induced complete bipartite subgraphs, maximum weight holes of a given parity, minimum dominating holes, antiholes of a given parity and some others. In addition, we define the family of subgraph filament graphs based on D, FI and GI, and prove it to be the same as the family of subgraph overlap graphs.

Partition of G into edge-disjoint H-factors is called H-factorization of G. Muthusamy and Paulraja have conjectured that for k ≥ 3, K_m□K_n has a P_k-factorization if and only if mn ≡ 0 (mod k) and k(m + n - 2) ≡ 0 (mod 2(k - 1)), where □ denote cartesian product of graphs. In this paper, it is shown that the necessary conditions mn ≡ 0 (mod 5) and 5(m + 1) ≡ 0 (mod 8) are sufficient for the existence of a P₅-factorization of K_m□C_n when

(i) m = 7, n ≡ 0 (mod 5),

(ii) m ≡ 175 (mod 280), n ≡ 0(mod 5).

Further, it is shown that the necessary conditions mn ≡ 0 (mod 5) and 5(m + n - 2) ≡ 0 (mod 8) are sufficient for the existence of a P₅-factorization of K_m□K_n in the following cases:

(i) m ≡ 5 (mod 40), n ≡ 5 (mod 40),

(ii) m ≡ 10 (mod 40), n ≡ 0 (mod 40),

(iii) m ≡ 15 (mod 120), n = 3 and m ≡ 15 (mod 120), n ≡ 75 (mod 120),

(iv) m ≡ 20 (mod 40), n ≡ 30 (mod 120),

(v) m ≡ 25 (mod 40), n ≡ 25 (mod 40),

(vi) m ≡ 30 (mod 120), n = 4 and m ≡ 30 (mod 120), n ≡ 20 (mod 40),

(vii) m ≡ 75 (mod 120), n ≡ 15 (mod 120),

(viii) m ≡ 0 (mod 40), n = 2 and m ≡ 0 (mod 40), n ≡ 10 (mod 40).

In fact our results partially answer the above conjecture when k = 5.

A k-partition V₁, V₂, …, V_k of a graph G is said to be balanced if -1 ≤ |V_i| - |V_j| ≤ 1 for 1 ≤ i, j ≤ k. The maximum balanced k-partition problem asks for a balanced k-partition V₁, V₂, …, V_k of a graph that maximizes e(V₁, V₂, …, V_k) which is the total number of edges with ends in distinct ones of V₁, V₂, …, V_k. Let G be a graph with m edges, and let r be the maximum number of vertex-disjoint 2-paths, where a 2-path stands for a path of length 2. We show that G admits a balanced 3-partition V₁, V₂, V₃ such that . We also present, for each real number 3 ≤ p < 6, a sufficient condition that G admits a maximum balanced 3-partition V₁, V₂, V₃ with , where e(V_i) denotes the number of edges of G with both ends in V_i.

Let γ(D) denote the domination number of a digraph D and let C_m ⊗ C_n denote the strong product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values Furthermore, we give a lower bound and an upper bound of γ(C_m1 ⊗ C_m2 ⊗ ⋯ ⊗ C_mn) and obtain that when at least n-2 integers of {m₁, m₂, …, m_n} are even (because of the isomorphism, we assume that m₃, m₄, …, m_n are even).

Task reassignments in two-dimensional (2D) mesh-connected systems (2D-MSs) have been researched for several decades. We propose a hierarchical 2D mesh-connected system (2D-HMS) in order to exploit the regular nature of a 2D-MS. In our approach priority-based task assignments and reassignments in a 2D-HMS are represented by tableaux and their algorithms. We show how task relocations for a priority-based task reassignment in a 2D-HMS are reduced to a jeu de taquin slide.

A plane graph G is entirely k-choosable if, for every list L of colors satisfying L(x) = k for x ∈ V(G) ∪ E(G) ∪ F(G), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In this paper, we show that every plane graph G with maximum degree Δ ≤ 5 is entirely (Δ + 5)-choosable.

A Boolean quasilattice is an algebra with hyperidentities of the variety of Boolean algebras. In this paper, we give a functional representation of the free n-generated Boolean quasilattice with two binary, one unary and two nullary operations. Namely, we define the concept of super-Boolean function and prove that the free Boolean quasilattice with two binary, one unary and two nullary operations on n free generators is isomorphic to the Boolean quasilattice of super-Boolean functions of n variables.

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. This paper characterizes claw-free cubic graphs whose 1-skeleton graphs of perfect matching polytopes have diameter 1.

A graph G is fractional independent-set-deletable k-factor-critical if G-I has a fractional k-factor for every independent set I of G. In this paper, we prove that if |V(G)| ≥ k + 2, and t(G) ≥ k² + 6k, then G is fractional ID-k-factor-critical.

In this paper, we construct a Cartesian authentication code from subspaces of singular symplectic space and compute its parameters. Assuming that the encoding rules of the transmitter and the receiver are chosen according to a uniform probability distribution, the probabilities of successful impersonation attack and substitution attack are also computed.

The unicyclic graph C_n,g obtained by appending a cycle C_g of length g to a pendent vertex of a path on n - g vertices is the lollipop graph on n vertices. In [Algebraic connectivity of lollipop graphs, Linear Algebra Appl.434 (2011) 2204–2210], Guo et al. proved that a(C_n,g-1) < a(C_n,g) for g ≥ 4, where a(C_n,g) is the algebraic connectivity of C_n,g. In this paper, we present a new approach which is quite different from that of Guo et al. in proving a(C_n,g-1) < a(C_n,g) for g ≥ 4.

In a simple connected graph, the average 2-degree of a vertex is the average degree of its neighbors. With the average 2-degree sequence and the maximum degree ratio of adjacent vertices, we present a sharp upper bound of the spectral radius of the adjacency matrix of a graph, which improves a result in [Y. H. Chen, R. Y. Pan and X. D. Zhang, Two sharp upper bounds for the signless Laplacian spectral radius of graphs, Discrete Math. Algorithms Appl.3(2) (2011) 185–191].

Linear codes constitute an important family of error-correcting codes and have a rich algebraic structure. Initially, these codes were studied with respect to the Hamming metric; while for the past few years, they are also studied with respect to a non-Hamming metric, known as the Rosenbloom–Tsfasman metric (also known as RT metric or ρ metric). In this paper, we introduce and study the split ρ weight enumerator of a linear code in the R-module M_n×s(R) of all n × s matrices over R, where R is a finite Frobenius commutative ring with unity. We also define the Lee complete ρ weight enumerator of a linear code in M_n×s(ℤ_k), where ℤ_k is the ring of integers modulo k ≥ 2. We also derive the MacWilliams identities for each of these ρ weight enumerators.