Search

Let S n be the symmetric group on [ n ] = { 1 , 2 , ⋯ , n } and C n (r) be the set of all r-cycles in S n that do not fix 1, i.e., C n (r) = { α ∈ S n ∣ α (1) ≠ 1 and α is an r - cycle } . In this paper, we give a reduction formula of the eigenvalues of the Cayley graph Γ (S n , C n (r)) . Then we apply it to determine all the eigenvalues of the Cayley graph Γ (S n , C n (r)) for r = 3 , n - 1 and n. [ABSTRACT FROM AUTHOR]

Let p be a prime and F p be the set of integers modulo p. Let χ p be a function defined on F p such that χ p (0) = 0 and for a ∈ F p \ { 0 } , set χ p (a) = 1 if a is a quadratic residue modulo p and χ p (a) = − 1 if a is a quadratic non-residue modulo p. Note that χ p (a) = a p is indeed the Legendre symbol. The image of χ p in the set of real numbers. In this paper, we consider the following sum ∑ x ∈ F p χ p ((x − a 1) (x − a 2) ... (x − a t)) where a 1 , a 2 , ... , a t are distinct elements in F p . [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on [ n ] = { 1 , 2 , ... , n } and Z n (s) = { α ∈ S n : α is an s -cycle } where 2 ≤ s ≤ n. In this paper, we determine all the partitions associated with the smallest eigenvalues of the Cayley graph Γ (S n , Z n (s)) for s = 3. [ABSTRACT FROM AUTHOR]

Let [ n ] = { 1 , 2 , ⋯ , n } . Let [ n ] k be the family of all subsets of [n] of size k. Define a real-valued weight function w on the set [ n ] k such that ∑ X ∈ [ n ] k w (X) ≥ 0 . Let U n , t , k be the set of all P = { P 1 , P 2 , ⋯ , P t } such that P i ∈ [ n ] k for all i and P i ∩ P j = ∅ for i ≠ j . For each P ∈ U n , t , k , let w (P) = ∑ P ∈ P w (P) . Let U n , t , k + (w) be set of all P ∈ U n , t , k with w (P) ≥ 0 . In this paper, we show that | U n , t , k + (w) | ≥ ∏ 1 ≤ i ≤ (t - 1) k (n - t k + i) (k !) t - 1 ((t - 1) !) for sufficiently large n. [ABSTRACT FROM AUTHOR]

Let [ n ] = { 1 , 2 , ⋯ , n } . For each i ∈ [ k ] and j ∈ [ n ] , let w i (j) be a real number. Suppose that ∑ i ∈ [ k ] , j ∈ [ n ] w i (j) ≥ 0 . Let F be the set of all functions with domain [k] and codomain [n]. For each f ∈ F , let w (f) = w 1 (f (1)) + w 2 (f (2)) + ⋯ + w k (f (k)). A function f ∈ F is said to be nonnegative if w (f) ≥ 0 . Let F + (w) be set of all nonnegative functions, i.e., F + (w) = { f ∈ F : w (f) ≥ 0 }. In this paper, we show that | F + (w) | ≥ n k - 1 for n ≥ 3 (k - 1) 2 . [ABSTRACT FROM AUTHOR]

Let Fq be the field of size q and SL(n, q) be the special linear group of order n over the field Fq. Assume that n is an even integer. Let Ai⊆SL(n,q) for i=1,2,⋯,k and |A1|=|A2|=⋯=|Ak|=l. The set {A1,A2,⋯,Ak} is called a k-cross (n, q)-Parsons set of size l, if for any pair of (i, j) with i≠j, A-B∈SL(n,q) for all A∈Ai and B∈Aj. Let m(k, n, q) be the largest integer l for which there is a k-cross (n, q)-Parsons set of size l. The integer m(k, n, q) will be called the k-cross (n, q)-Parsons numbers. In this paper, we will show that m(3,2,q)≤q. Furthermore, m(3,2,q)=q if and only if q=4r for some positive integer r. We will also show that if n is a multiple of q-1, then m(q-1,n,q)≥q12n(n-1). [ABSTRACT FROM AUTHOR]

Let Z be the set of integers and Zl be the set of integers modulo l. A set L⊆T=Zl1×Zl2×⋯×Zlm is called a line if there exist a,b∈T such that L={a+tb∈T:t∈Z}. A set X⊆T is called a no-three-in-line set if |X∩L|≤2 for all the lines L in T. The maximum size of a no-three-in-line set is denoted by τT. Let m≥2 and k1,k2,…,km be positive integers such that gcd(ki,kj)=1 for all i, j with i≠j. In this paper, we will show that τZk1n×Zk2n×⋯×Zkmn≤2nm-1.We will give sufficient conditions for which the equality holds. When k1=k2=⋯=km=1 and n=pl where p is a prime and l≥1 is an integer, we will show that equality holds if and only if p=2 and l=1, i.e., τZpl×Zpl×⋯×Zpl=2pl(m-1) if and only if p=2 and l=1. [ABSTRACT FROM AUTHOR]

Group signatures are a leading competing signature technique with a substantial amount of research. With group settings, group signatures provide user anonymity. Any group member with access to the group can generate a signature while remaining anonymous. The group manager, however, has the authority to expose and identify the signer if required. Since the privacy of the sender should be preserved, this is a conflict between privacy and accountability. Concerning high performance on security, we propose a novel, well-balanced security and privacy group signature scheme based on a general linear group over group ring. To the best of our knowledge, our work represents the first comprehensive framework for a group signature scheme that utilizes generic linear groups over group rings. We demonstrate that the competing security goals of message trustworthiness, privacy, and accountability are effectively resolved by our protocol. The results of the performance evaluation and simulation demonstrate that our protocol achieves strong security, system robustness, and high-performance efficiency, making it suitable for practical applications. [ABSTRACT FROM AUTHOR]

Let S n denote the set of permutations of [ n ] = { 1 , 2 , … , n } . For a positive integer k , define S n , k to be the set of all permutations of [ n ] with exactly k disjoint cycles, i.e., S n , k = { π ∈ S n : π = c 1 c 2 ⋯ c k } , where c 1 , c 2 , … , c k are disjoint cycles. The size of S n , k is given by [ n k ] = ( − 1 ) n − k s ( n , k ) , where s ( n , k ) is the Stirling number of the first kind. A family A ⊆ S n , k is said to be t -cycle-intersecting if any two elements of A have at least t common cycles. A family A ⊆ S n , k is said to be trivially t -cycle-intersecting if A is the stabiliser of t fixed points, i.e., A consists of all permutations in S n , k with some t fixed cycles of length one. For 1 ≤ j ≤ t , let Q j = { σ ∈ S n , k : σ ( i ) = i for all i ∈ [ k ] ∖ { j } } . For t + 1 ≤ s ≤ k , let B s = { σ ∈ S n , k : σ ( i ) = i for all i ∈ [ t ] ∪ { s } } . In this paper, we show that, given any positive integers k , t with k ≥ 2 t + 3 , there exists an n 0 = n 0 ( k , t ) , such that for all n ≥ n 0 , if A ⊆ S n , k is non-trivially t -cycle-intersecting, then | A | ≤ | B | , where B = ⋃ s = t + 1 k B s ∪ ⋃ j = 1 t Q j . Furthermore, equality holds if and only if A is a conjugate of B , i.e., A = β − 1 B β for some β ∈ S n . [ABSTRACT FROM AUTHOR]

This article introduces the concept of partially controlled J metric spaces; in particular, the J metric space with self-distance is not necessarily zero, which is important in computer science. We prove the existence of a unique fixed point for linear and nonlinear contractions, provide some examples to prove the existence of this metric space, and present some important applications in fractional differential equations, i.e., "Riemann–Liouville derivatives". [ABSTRACT FROM AUTHOR]

Let N 0 be the set of non-negative integers, and let P ( n , l ) denote the set of all weak compositions of n with l parts, i.e., P ( n , l ) = { ( x 1 , x 2 , … , x l ) ∈ N 0 l : x 1 + x 2 + ⋯ + x l = n } . For any element u = ( u 1 , u 2 , … , u l ) ∈ P ( n , l ) , denote its i th-coordinate by u ( i ) , i.e., u ( i ) = u i . Let l = min ( l 1 , l 2 , … , l r ) . Families A j ⊆ P ( n j , l j ) ( j = 1 , 2 , … , r ) are said to be r -cross t -intersecting if | { i ∈ [ l ] : u 1 ( i ) = u 2 ( i ) = ⋯ = u r ( i ) } | ≥ t for all u j ∈ A j . Suppose that l ≥ t + 2 . We prove that there exists a constant n 0 = n 0 ( l 1 , l 2 , … , l r , t ) depending only on l j ’s and t , such that for all n j ≥ n 0 , if the families A j ⊆ P ( n j , l j ) ( j = 1 , 2 , … , r ) are r -cross t -intersecting, then ∏ j = 1 r | A j | ≤ ∏ j = 1 r n j + l j − t − 1 l j − t − 1 . Moreover, equality holds if and only if there is a t -set T of { 1 , 2 , … , l } such that A j = { u ∈ P ( n j , l j ) : u ( i ) = 0 for all i ∈ T } for j = 1 , 2 , … , r . [ABSTRACT FROM AUTHOR]

For a finite commutative ring R, let a , b , c ∈ R be fixed elements. Consider the equation a x + b y = c z where x, y, and z are idempotents, units, and any element in the ring R, respectively. We say that R satisfies the r-monochromatic clean condition if, for any r-colouring χ of the elements of the ring R, there exist x , y , z ∈ R with χ (x) = χ (y) = χ (z) such that the equation holds. We define m (a , b , c) (R) to be the least positive integer r such that R does not satisfy the r-monochromatic clean condition. This means that there exists χ (i) = χ (j) for some i , j ∈ { x , y , z } where i ≠ j . In this paper, we prove some results on m (a , b , c) (R) and then formulate various conditions on the ring R for when m (1 , 1 , 1) (R) = 2 or 3, among other results concerning the ring Z n of integers modulo n. [ABSTRACT FROM AUTHOR]

In this manuscript, we establish a new type of metric space that is called controlled strong metric spaces by introducing a controlled function to the triangle inequality as follows: ℘ (s , r) ≤ ℘ (s , z) + η (z , r) ℘ (z , r) , and keeping the symmetry condition that is ℘ (s , r) = ℘ (r , s) for all r , s . We demonstrate the existence of the fixed point of self-mapping and its uniqueness in such spaces that satisfy linear and nonlinear contractions. Moreover, we provide three applications of results to polynomial equations of high degree, systems of linear equations, along with fractional differential equations. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we prove the Gallai–Edmonds structure theorem for weighted matching polynomials. Our result implies the Parter–Wiener theorem and its recent generalization about the existence of principal submatrices of a Hermitian matrix whose graph is a tree. [Copyright &y& Elsevier]

Abstract: Let be the set of non-negative integers, and let denote the set of all weak compositions of with parts, i.e., . For any element , denote its th-coordinate by , i.e., . A family is said to be -intersecting if for all . We prove that given any positive integers with , there exists a constant depending only on and , such that for all , if is -intersecting then Moreover, the equality holds if and only if for some -set of . [Copyright &y& Elsevier]

Abstract: Let be the set of positive integers, and let be the set of (ordered) partitions of . We show that there exist a rank function and orderings and such that the ranked poset is Macaulay. [Copyright &y& Elsevier]

Abstract: A graph has a perfect matching if and only if is not a root of its matching polynomial . Thus, Tutte’s famous theorem asserts that is not a root of if and only if for all , where denotes the number of odd components of . Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number as a root of . We also extend maximal non-matchable graphs to maximal -non-matchable graphs and determine the structure of such graphs. [Copyright &y& Elsevier]

Abstract: Let denote the collection of all set partitions of . Suppose is a non-trivial t-intersecting family of set partitions i.e. any two members of have at least t blocks in common, but there is no fixed set of t blocks of size one which belong to all of them. It is proved that for sufficiently large n depending on t, where is the n-th Bell number and is the number of set partitions of without blocks of size one. Moreover, equality holds if and only if is equivalent to where . This is an analogue of the Hilton–Milner theorem for set partitions. [Copyright &y& Elsevier]

Abstract: We give a new recurrence formula for the eigenvalues of the derangement graph. Consequently, we provide a simpler proof of the Alternating Sign Property of the derangement graph. Moreover, we prove that the absolute value of the eigenvalue decreases whenever the corresponding partition with a fixed first part decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales [C.Y. Ku, D.B. Wales, Eigenvalues of the derangement graph, J. Combin. Theory Ser. A 117 (2010) 289–312] regarding the lower and upper bounds for the absolute values of these eigenvalues. [Copyright &y& Elsevier]

By recalling van der Waerden theorem, there exists a least a positive integer w = w (k ; r) such that for any n ≥ w , every r-colouring of [ 1 , n ] admits a monochromatic k-term arithmetic progression. Let k ≥ 2 and r k (n) denote the minimum number of colour required so that there exists a r k (n) -colouring of [ 1 , n ] that avoids any monochromatic k-term arithmetic progression. In this paper, we give necessary and sufficient conditions for r k (n + 1) = r k (n) . We also show that r k (n) = 2 for all k ≤ n ≤ 2 (k − 1) 2 and give an upper bound for r p (p m) for any prime p ≥ 3 and integer m ≥ 2 . [ABSTRACT FROM AUTHOR]

Abstract: Recently, Bauer et al. [D. Bauer, H.J. Broersma, A. Morgana, E. Schmeichel, Tutte sets in graphs I: maximal Tutte sets and -graphs, J. Graph Theory 55 (2007) 343–358] introduced a graph operator , called the -graph of , which has been useful in investigating the structural aspects of maximal Tutte sets in with a perfect matching. Among other results, they proved a characterization of maximal Tutte sets in terms of maximal independent sets in the graph and maximal extreme sets in . This was later extended to graphs without perfect matchings by Busch et al. [A. Busch, M. Ferrara, N. Kahl, Generalizing -graphs, Discrete Appl. Math. 155 (2007) 2487–2495]. Let be a real number and be the matching polynomial of a graph . Let be the multiplicity of as a root of . We observe that the notion of -graph is implicitly related to . In this paper, we give a natural generalization of the -graph of for any real number , and denote this new operator by , so that coincides with when . We prove a characterization of maximal -Tutte sets which are -analogues of maximal Tutte sets in . In particular, we show that for any , , and any real number , if and only if for any , , thus extending the preceding work of Bauer et al. (2007)  and Busch et al. (2007)  which established the result for the case . Subsequently, we show that every maximal -Tutte set is matchable to an independent set in ; moreover, always contains an isomorphic copy of the subgraph induced by . To this end, we introduce another related graph which is a supergraph of , and prove that and have the same Gallai–Edmonds decomposition with respect to . Moreover, we determine the structure of in terms of its Gallai–Edmonds decomposition and prove that . [Copyright &y& Elsevier]

Abstract: Let G be a permutation group acting on and be a system of n subsets of . When is there an element so that for each ? If such a g exists, we say that G has a G-marriage subject to . An obvious necessary condition is the orbit condition: for any nonempty subset Y of , there is an element such that the image of Y under g is contained in . Keevash observed that the orbit condition is sufficient when G is the symmetric group ; this is in fact equivalent to the celebrated Hall''s Marriage Theorem. We prove that the orbit condition is sufficient if and only if G is a direct product of symmetric groups. We extend the notion of orbit condition to that of k-orbit condition and prove that if G is the cyclic group where or G acts 2-transitively on , then G satisfies the -orbit condition subject to if and only if G has a G-marriage subject to . [Copyright &y& Elsevier]

Abstract: In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to their connection to maximum matchings in a graph. For a root of the matching polynomial, we define -barrier and -extreme sets. We prove a generalized Berge–Tutte formula and give a characterization for the set of all -special vertices in a graph. [ABSTRACT FROM AUTHOR]

In 1977, Davis et al. proposed a method to generate an arrangement of [ n ] = { 1 , 2 , ... , n } that avoids three-term monotone arithmetic progressions. Consequently, this arrangement avoids k-term monotone arithmetic progressions in [ n ] for k ≥ 3 . Hence, we are interested in finding an arrangement of [ n ] that avoids k-term monotone arithmetic progression, but allows k − 1 -term monotone arithmetic progression. In this paper, we propose a method to rearrange the rows of a magic square of order 2 k − 3 and show that this arrangement does not contain a k-term monotone arithmetic progression. Consequently, we show that there exists an arrangement of n consecutive integers such that it does not contain a k-term monotone arithmetic progression, but it contains a k − 1 -term monotone arithmetic progression. [ABSTRACT FROM AUTHOR]

The Ramsey numbers R (T n , W 8) are determined for each tree graph T n of order n ≥ 7 and maximum degree Δ (T n) equal to either n - 4 or n - 5 . These numbers indicate strong support for the conjecture, due to Chen, Zhang and Zhang and to Hafidh and Baskoro, that R (T n , W m) = 2 n - 1 for each tree graph T n of order n ≥ m - 1 with Δ (T n) ≤ n - m + 2 when m ≥ 4 is even. [ABSTRACT FROM AUTHOR]

In this paper, we prove Erdős-Ko-Rado type results for (a) family of set partitions where the size of each block is a multiple of k ; and (b) family of set partitions with minimum block size k. [ABSTRACT FROM AUTHOR]

The key objective of this paper is to study the cyclic codes over mixed alphabets on the structure of F q P Q , where P = F q [ v ] 〈 v 3 − α 2 2 v 〉 and Q = F q [ u , v ] 〈 u 2 − α 1 2 , v 3 − α 2 2 v 〉 are nonchain finite rings and α i is in F q / { 0 } for i ∈ { 1 , 2 } , where q = p m with m ≥ 1 is a positive integer and p is an odd prime. Moreover, with the applications, we obtain better and new quantum error-correcting (QEC) codes. For another application over the ring P, we obtain several optimal codes with the help of the Gray image of cyclic codes. [ABSTRACT FROM AUTHOR]

The burning number b(G) of a graph G is used for measuring the speed of contagion in a graph. In this paper, we study the burning number of the generalized Petersen graph P(n, k). We show that for any fixed positive integer k, limn→∞b(P(n,k))nk=1. Furthermore, we give tight bounds for b(P(n, 1)) and b(P(n, 2)). [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on n -points. The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n and two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we give a recurrence formula for the eigenvalues of a class of regular subgraphs of F ( n , k ) . By using this recurrence formula, we will determine the smallest eigenvalues for this class of regular subgraphs of F ( n , 1 ) for sufficiently large n . [ABSTRACT FROM AUTHOR]

It was conjectured in the monograph [9] by Godsil and Meagher and in the article [10] by Lindzey that the perfect matching derangement graph M 2 n possesses the alternating sign property, that is, for any integer partition λ = (λ 1 , ... , λ r) ⊢ n , the sign of the eigenvalue η λ of M 2 n is given by sign (η λ) = (− 1) n − λ 1 . In this paper, we prove that the conjecture is true. Our approach yields a recurrence formula for the eigenvalues of the perfect matching derangement graph as well as a new recurrence formula for the eigenvalues of the permutation derangement graph. [ABSTRACT FROM AUTHOR]

The lazy cop number is the minimum number of cops needed for the cops to have a winning strategy in the game of Cops and Robbers where at most one cop may move in any round. This variant of the game of Cops and Robbers, called Lazy Cops and Robbers, was introduced by Offner and Ojakian, who provided bounds for the lazy cop number of the hypercube. In this paper, we are interested in the game of Lazy Cops and Robbers on generalized hypercubes. Generalizing existing methods, we will give asymptotic upper and lower bounds on the lazy cop number of the generalized hypercube. [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on [ n ] = { 1 , … , n } . The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n such that two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we show that for sufficiently large n in terms of k the smallest eigenvalue of F ( n , k ) occurs at the partition ( n − t 0 , t 0 ) where t 0 is the smallest positive integer satisfying ∑ r = 0 t 0 ( k r ) ( − 1 ) t 0 − r ( t 0 − r ) ! < 0 . It was conjectured by Ellis in Ellis (2014) that if A is an independent set in F ( n , k ) , then | A | ≤ ( n − k − 1 ) ! for sufficiently large n . Our result implies that | A | ≤ O k ( ( n − k − 1 2 ) ! ) for sufficiently large n . [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on { 1 , … , n } . The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n and two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we determine the smallest eigenvalue for F ( n , 1 ) . [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on [ n ] = { 1 , … , n } . The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n and two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we derive a recurrence formula for the eigenvalues of F ( n , k ) . Then we apply our result to determine the sign of the eigenvalues of F ( n , 1 ) . [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we show that the eigenvalues of certain classes of Cayley graphs are integers. The -arrangement graph is a graph with all the k-permutations of an n-element set as vertices where two k-permutations are adjacent if they differ in exactly r positions. We establish a relation between the eigenvalues of the arrangement graphs and the eigenvalues of certain Cayley graphs. As a result, the conjecture on integrality of eigenvalues of follows. [Copyright &y& Elsevier]

Given two simple graphs G and H , the Ramsey number R (G , H) is the smallest integer n such that for any graph of order n , either it contains G or its complement contains H. Let T n be a tree graph of order n and W s , m be the generalised wheel graph K s + C m. In this paper, we show that for n ≥ 5 , s ≥ 2 , R (T n , W s , 6) = (s + 1) (n − 1) + 1 and for n ≥ 5 , s ≥ 1 , R (T n , W s , 7) = (s + 2) (n − 1) + 1. We also determine the exact value of R (T n , W s , m) for large n and s. [ABSTRACT FROM AUTHOR]

Public announcement logic is a logic that studies epistemic updates. In this paper, we propose a sound and complete labelled natural deduction system for public announcement logic with the common knowledge operator (PAC). The completeness of the proposed system is proved indirectly through a Hilbert calculus for PAC known to be complete and sound. We conclude with several discussions regarding the system including some problems of the system in attaining normalisation and subformula property. [ABSTRACT FROM AUTHOR]