Search

Let r ≥ 2 and r be even. An r -hypergraph G on n vertices is called odd-colorable if there exists a map φ : [ n ] → [ r ] such that for any edge { j 1 , j 2 , … , j r } of G , we have φ ( j 1 ) + φ ( j 2 ) + ⋅ ⋯ ⋅ + φ ( j r ) ≡ r ∕ 2 ( mod r ) . In this paper, we first determine that, if r = 2 q ( 2 t + 1 ) and n ≥ 2 q ( 2 q − 1 ) r , then the maximum chromatic number in the class of the odd-colorable r -hypergraphs on n vertices is 2 q , which answers a question raised by V. Nikiforov recently in Nikiforov (2017). We also study some applications of the spectral symmetry of the odd-colorable r -hypergraphs given in the same paper by V. Nikiforov. We show that the Laplacian spectrum S p e c ( L ( G ) ) and the signless Laplacian spectrum S p e c ( Q ( G ) ) of an r -hypergraph G are equal if and only if r is even and G is odd-colorable. As an application of this result, we give an affirmative answer for the remaining unsolved case r ⁄ ≡ 0 ( m o d 4 ) of a question raised in Shao et al. (2015) about whether S p e c ( L ( G ) ) = S p e c ( Q ( G ) ) implies that L ( G ) and Q ( G ) have the same H-spectrum. [ABSTRACT FROM AUTHOR]

This is a survey or exposition of a particular collection of results and open problems involving snarks — simple “cubic” (3-valent) graphs for which, for nontrivial reasons, the edges cannot be 3-colored. The results and problems here are rooted in a series of papers by László Kászonyi that were published in the early 1970s. The problems posed in this survey paper can be tackled without too much specialized mathematical preparation, and in particular seem well suited for interested undergraduate mathematics students to pursue as independent research projects. This survey paper is intended to facilitate research on these problems. [ABSTRACT FROM AUTHOR]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

In this paper we continue studying the independent transversal domination number in a graph, i.e., the cardinality of a smallest dominating set which intersects each maximum independent set. As our main result, we prove two upper bounds on the independent transversal domination number in terms of the order and minimum degree of a graph. [ABSTRACT FROM AUTHOR]

The spectrum of a first order sentence is the set of all α such that G ( n , n − α ) does not obey zero–one law with respect to this sentence. In this paper, we prove that the minimal number of quantifier alternations of a first order sentence with infinite spectrum equals 3. We have also proved that the spectrum of a first-order sentence with quantifier depth 4 has no limit points except possibly the points 1 ∕ 2 and 3 ∕ 5 . [ABSTRACT FROM AUTHOR]

An edge-coloured connected graph G is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses k colours then G is called k -rainbow connected. The rainbow connection number of G , denoted by rc ( G ) , is the minimum k such that G is k -rainbow connected. Even the problem to decide whether rc ( G ) = 2 is NP-complete. It has been shown that if G is a connected graph of order n and size m with n − 2 2 + 2 ≤ m ≤ n − 1 2 , then 2 ≤ rc ( G ) ≤ 3 . In this paper we will present sufficient conditions for graphs G of this size to fulfil rc ( G ) = 2 depending on vertex degrees. [ABSTRACT FROM AUTHOR]