Search

In this paper we consider the monoids of all partial endomorphisms, of all partial weak endomorphisms, of all injective partial endomorphisms, of all partial strong endomorphisms and of all partial strong weak endomorphisms of a star graph with a finite number of vertices. Our main objective is to determine their ranks. We also describe their Green's relations, calculate their cardinalities and study their regularity. [ABSTRACT FROM AUTHOR]

An orientable vertex primitive complete map is a two-cell embedding of a complete graph into an orientable surface such that the automorphism group of this map acts primitively on its vertex set. The paper is devoted to the problem of enumerating orientable vertex primitive complete maps. For a given integer n, we derive the number of different such maps with n vertices. Furthermore, we obtain explicit formulas for the numbers of non-isomorphic orientable vertex primitive complete maps with n vertices. [ABSTRACT FROM AUTHOR]

The derived graph of a voltage graph consisting of a single vertex and two loops of different voltages is a circulant graph with two generators. We characterize the automorphism groups of connected, two-generator circulant graphs, and give their determining and distinguishing number, and when relevant, their cost of 2-distinguishing. We do the same for the subdivisions of connected, two-generator circulant graphs obtained by replacing one loop in the voltage graph with a directed cycle. [ABSTRACT FROM AUTHOR]

Given a graph X with a Hamilton cycle C, the compression factor κ (X , C) of C is the order of the largest cyclic subgroup of Aut (C) ∩ Aut (X) , and the Hamilton compression κ (X) of X is the maximum of κ (X , C) where C runs over all Hamilton cycles in X. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor et al. (Ann Comb, arXiv:2205.08126v1, https://doi.org/10.1007/s00026-023-00674-y, 2023) whether for every positive integer k, there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to k. Since an infinite family of Cayley graphs with Hamilton compression equal to 1 was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products Z p ⋊ Z k where p is a prime and k ≥ 2 a divisor of p - 1 . Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to 1 are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given. [ABSTRACT FROM AUTHOR]

We present a new method for finding k shortest paths between any two vertices in the Cayley graph Cay (G , S) of a finite group G with its generating set S closed under inverses. By using a reduced convergent rewriting system R for G, we first find the lexicographically minimal shortest path between two vertices in Cay (G , S) . Then, by symmetrizing the length-preserving rules of R, we provide a polynomial time algorithm (in the size of certain rewrite rules, the lexicographically minimal shortest path, and k) for finding k shortest paths between two vertices in Cay (G , S) . Our implementation of finding k shortest paths between two vertices in Cay (G , S) is also discussed. [ABSTRACT FROM AUTHOR]

For a simple graph G with edge ideal I(G), we study the N -graded Betti numbers in the linear strand of the minimal free resolution of I (Γ (Z n)) , where Γ (Z n) is the zero divisor graph of the ring Z n . We present sharp bounds for the Betti numbers of Γ (Z n) and characterize the graphs attaining these bounds, thereby establishing the correct equality case for one of the results of the earlier published paper (Theorem 4.5, S. Pirzada and S. Ahmad, On the linear strand of edge ideals of some zero divisor graphs, Commun. Algebra 51(2) (2023) 620–632). Also, we present homological invariants of the edge rings of Γ (Z n) for n = p 2 q and pqr, with primes p < q < r. [ABSTRACT FROM AUTHOR]

For a simple graph G with edge ideal I(G), we study the N -graded Betti numbers in the linear strand of the minimal free resolution of I (Γ (Z n)) , where Γ (Z n) is the zero divisor graph of the ring Z n . We present sharp bounds for the Betti numbers of Γ (Z n) and characterize the graphs attaining these bounds, thereby establishing the correct equality case for one of the results of the earlier published paper (Theorem 4.5, S. Pirzada and S. Ahmad, On the linear strand of edge ideals of some zero divisor graphs, Commun. Algebra 51(2) (2023) 620–632). Also, we present homological invariants of the edge rings of Γ (Z n) for n = p 2 q and pqr, with primes p < q < r. [ABSTRACT FROM AUTHOR]

The spectral decomposition of graph adjacency matrices is an essential ingredient in the design of graph signal processing (GSP) techniques. When the adjacency matrix has multi-dimensional eigenspaces, it is desirable to base GSP constructions on a particular eigenbasis that better reflects the graph’s symmetries. In this paper, we provide an explicit and detailed representation-theoretic account for the spectral decomposition of the adjacency matrix of a weighted Cayley graph. Our method applies to all weighted Cayley graphs, regardless of whether they are quasi-Abelian, and offers detailed descriptions of eigenvalues and eigenvectors derived from the coefficient functions of the representations of the underlying group. Next, we turn our attention to constructing frames on Cayley graphs. Frames are overcomplete spanning sets that ensure stable and potentially redundant systems for signal reconstruction. We use our proposed eigenbases to build frames that are suitable for developing signal processing on Cayley graphs. These are the Frobenius–Schur frames and Cayley frames, for which we provide a characterization and a practical recipe for their construction. [ABSTRACT FROM AUTHOR]

For a chain of cycles Γ , we prove that Cliff (Γ) = gon (Γ) - 2 . [ABSTRACT FROM AUTHOR]

An automorphism of a graph describes its structural symmetry and the concept of fixing number of a graph is used for breaking its symmetries (except the trivial one). In this paper, we evaluate automorphisms of the co-normal product graph G 1 ∗ G 2 of two simple graphs G 1 and G 2 and give sharp bounds on the order of its automorphism group. We study the fixing number of G 1 ∗ G 2 and prove sharp bounds on it. Moreover, we compute the fixing number of the co-normal product of some families of graphs. [ABSTRACT FROM AUTHOR]

If G is a finite group, then the spectrum ω (G) is the set of all element orders of G. The prime spectrum π (G) is the set of all primes belonging to ω (G) . A simple graph Γ (G) whose vertex set is π (G) and in which two distinct vertices r and s are adjacent if and only if r s ∈ ω (G) is called the Gruenberg–Kegel graph or the prime graph of G. In this paper, we prove that if G is a group of even order, then the set of vertices which are non-adjacent to 2 in Γ (G) forms a union of cliques. Moreover, we decide when a strongly regular graph is isomorphic to the Gruenberg–Kegel graph of a finite group. [ABSTRACT FROM AUTHOR]

An H-decomposition of a graph Γ is a partition of its edge set into subgraphs isomorphic to H. A transitive decomposition is a special kind of H-decomposition that is highly symmetrical in the sense that the subgraphs (copies of H) are preserved and transitively permuted by a group of automorphisms of Γ . This paper concerns transitive H-decompositions of the graph K n □ K n where H is a path. When n is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are considerably large compared to the number of vertices. Our main result supports well-known Gallai's conjecture and an extended version of Ringel's conjecture. [ABSTRACT FROM AUTHOR]

AbstractLet S⊆N be a numerical semigroup with multiplicity m=min(S∖{0}) and conductor c=max(Z∖S)+1. Let P be the set of primitive elements, i.e. minimal generators, of S, and let L be the set of elements of S which are smaller than c. Wilf’s conjecture (1978) states that the inequality |P||L|≥c must hold. The conjecture has been shown to hold in case |P|≥m/2 by Sammartano in 2012, and subsequently in case |P|≥m/3 by the author in 2020. The main result in this paper is that Wilf’s conjecture holds in case |P|≥m/4 when m divides c. The proof uses divsets X, i.e. finite divisor-closed sets of monomials, as abstract models of numerical semigroups, and proceeds with estimates of the vertex-maximal matching number of the associated graph G(X). [ABSTRACT FROM AUTHOR]

AbstractThe inclusion graph of a group G, written as In(G), is defined to be an undirected graph with all nontrivial subgroups of G as its vertices, and two distinct subgroups H, K of G are adjacent if either H≤K or K≤H. A local inclusion graph of G with respect to a given subgroup S, written as In(G,S), is an induced subgraph of In(G) with vertex set consisting of all nontrivial subgroups of G properly containing S. Indeed, In(G) can be viewed as the special case when S is the identity subgroup. Let GLn(F) be the general linear group consisting of all n×n invertible matrices over a field F and Tn(F) the subgroup of all invertible lower triangular matrices in GLn(F). In this article, an arbitrary automorphism of In(GLn(F),Tn(F)) is determined and it is proved that the automorphism group of In(GLn(F),Tn(F)) is isomorphic to the direct product of Sn−1 and S2, where Sn−1 is the symmetric group of degree n−1. [ABSTRACT FROM AUTHOR]

AbstractLet G be a finite group and let e be its identity element. The intersection power graph of G is the undirected graph with vertex set G, in which two distinct vertices x and y are adjacent if either 〈x〉∩〈y〉≠{e} or one of x and y is e. In this paper, we first compute the strong metric dimension of the intersection power graph of a cyclic group, a dihedral group, and a generalized quaternion group. We also characterize all finite groups G whose intersection power graph has strong metric dimension |G|−2. Then, we give the sharp upper and lower bounds for the metric dimension of the intersection power graph of a finite group. As applications, we obtain the metric dimension of the intersection power graph of a cyclic group, a dihedral group, a generalized quaternion group, and a group of odd order. [ABSTRACT FROM AUTHOR]

Symmetry properties are of vital importance for graphs. The famous Cayley graph is a good mathematical model as its high symmetry. The normality of the graph can well reflect the symmetry of the graph. In this paper, we characterize the normality of the direct product of Cayley graphs and give a sufficient and necessary condition for the direct product of two graphs to be a Cayley graph. Moreover, a sufficient and necessary condition for judging the normality of the direct product of two graphs is given. [ABSTRACT FROM AUTHOR]

The average order of a finite group G is denoted by o(G). In this note, we classify groups whose average orders are less than o(S4), where S4 is the symmetric group on four elements. Moreover, we prove that G ≌ S4 if and only if o(G) = o(S4). As a consequence of our results we give a characterization for some finite groups by the average order. In [9, Theorem 1.2], the groups whose average orders are less than o(A4) are classified. It is worth mentioning that to get our results we avoid using the main theorems of [9] and our results leads to reprove those theorems. [ABSTRACT FROM AUTHOR]

In this work, we provide two applications of the eigenvalues of the unitary Cayley graphs over matrix rings over finite fields. For a ring R, $ J_R $ J R denotes the Jacobson radical of R. In 2012, Kiani and Aghaei conjectured that if R and S are finite rings and their unitary Cayley graphs are isomorphic, then $ R/J_R $ R / J R and $ S/J_S $ S / J S are isomorphic. If this conjecture holds and $ J_R = \{0\} $ J R = { 0 } , then R is characterized by its unitary Cayley graph, and we say that R is a ring determined by unitary Cayley graphs. Kiani and Aghaei showed that every finite commutative ring and $ \operatorname {\textnormal {M}}_n(\operatorname {\mathbb {F}}_q) $ M n ⁡ ( F q) are such rings. We examine the eigenvalues of $ \operatorname {\textnormal {M}}_n(\operatorname {\mathbb {F}}_q) $ M n ⁡ ( F q) and obtain many new families of rings determined by unitary Cayley graphs. In 2021, Podestá and Videla characterized all finite commutative rings R such that the graphs in the triple $ \{ \textnormal {C}_{R}, \textnormal {C}^+_R, \bar {\textnormal {C}}_R\} $ { C R , C R + , C ¯ R } are mutually equienergetic non-isospectral and Ramanujan where $ \textnormal {C}^+_R $ C R + is the unitary Cayley sum graph. We use the eigenvalues of the graph $ \textnormal {C}_{\operatorname {\textnormal {M}}_n(\operatorname {\mathbb {F}}_q)} $ C M n ⁡ ( F q) and some observation on the number of matrices of the given rank to extend Podestá and Videla's results by working on the finite non-commutative ring $ \operatorname {\mathcal {R}} $ R being a product of matrix rings over local rings. [ABSTRACT FROM AUTHOR]

The projective norm graphs are central objects to extremal combinatorics. They appear in a variety of contexts, most importantly they provide tight constructions for the Turán number of complete bipartite graphs K t , s with s > (t - 1) ! . In this note we deepen their understanding further by determining their automorphism group. [ABSTRACT FROM AUTHOR]

Let S be a groupoid (magma) with zero 0, and let R = ⊕ s ∈ S R s be a contracted S-graded ring, that is, an S-graded ring with R 0 = 0. By G (H R) we denote the undirected power graph of a multiplicative subsemigroup H R = ∪ s ∈ S R s of R, and by G * (H R) a graph obtained from G (H R) by removing 0 and its incident edges. If Re is a nonzero ring component of R, then G * (R e) denotes a subgraph of G * (H R) , induced by R e *. In this paper we address a problem raised in [Abawajy, J., Kelarev, A., Chowdhury, M.: Power Graphs: A Survey. Electron. J. Graph Theory Appl. 1(2), 125–147 (2013)]. Namely, let S be torsion-free, that is, s n = t n implies s = t for all s, t ∈ S , and all positive integers n, and let S be 0-cancellative, that is, for all s, t, u ∈ S , su = tu ≠ 0 implies s = t , and us = ut ≠ 0 implies s = t. Also, let R be semisimple Artinian. We prove that if G * (R e) is connected for every nonzero ring component Re of R, then the connected components of G * (H R) are precisely the graphs G * (R e). [ABSTRACT FROM AUTHOR]

We can define six classes of endomorphisms on a graph, and they always form a chain based on set inclusion. The concepts of endomorphism type and endomorphism spectrum were introduced by Böttcher and Knauer in 1992. They provided a systematic and organized approach to study endomorphisms of graphs. In this paper, we focus on the double vertex wheel graphs and provide a detailed description of their endomorphism spectra and endomorphism types. [ABSTRACT FROM AUTHOR]

The enhanced power graph of a group G is a graph with vertex set G, where two distinct vertices x and y are adjacent if and only if there exists an element w in G such that both x and y are powers of w . To obtain the proper enhanced power graph, we consider the induced subgraph on the set G \ D , where D represents the set of dominating vertices in the enhanced power graph. In this paper, we aim to determine the strong domination number of the proper enhanced power graphs of finite nilpotent groups. [ABSTRACT FROM AUTHOR]

In this paper, we consider endomorphisms of an undirected cycle graph from Semigroup Theory perspective. Our main aim is to present a process to determine sets of generators with minimal cardinality for the monoids wEndCn and EndCn of all weak endomorphisms and all endomorphisms of an undirected cycle graph Cn with n vertices. We also describe Green's relations and regularity of these monoids and calculate their cardinalities. [ABSTRACT FROM AUTHOR]

Let F be a field and $ M_n(F) $ M n (F) the ring of $ n \times n $ n × n matrices over F. Given a subset S of $ M_n(F) $ M n (F) , the null ideal of S is the set of all polynomials f with coefficients from $ M_n(F) $ M n (F) such that $ f(A) = 0 $ f (A) = 0 for all $ A \in S $ A ∈ S. We say that S is core if the null ideal of S is a two-sided ideal of the polynomial ring $ M_n(F)[x] $ M n (F) [ x ]. We study sufficient conditions under which S is core in the case where S consists of $ 3 \times 3 $ 3 × 3 matrices, all of which share the same irreducible characteristic polynomial. In particular, we show that if F is finite with q elements and $ |S| \ge q^3-q^2+1 $ | S | ≥ q 3 − q 2 + 1 , then S is core. As a byproduct of our work, we obtain some results on block Vandermonde matrices, invertible matrix commutators, and graphs defined via an invertible difference relation. [ABSTRACT FROM AUTHOR]

We construct a locally 5-arc transitive G-graph Δ, where G ∈ { PSU 3 (8) ⋊ C 2 , PSU 3 (8) ⋊ C 6 } . The corresponding vertex stabilizer amalgams are of local characteristic 3 but are not weak (B, N)-pairs. They are the first examples of this kind where there exists a vertex z such that the extension of G z / O p (G z [ 1 ]) over O p (G z [ 1 ]) is non-split. [ABSTRACT FROM AUTHOR]

The relative fixity of a digraph Γ is defined as the ratio between the largest number of vertices fixed by a nontrivial automorphism of Γ and the number of vertices of Γ . We characterize the vertex-primitive digraphs whose relative fixity is at least 1 3 , and we show that there are only finitely many vertex-primitive digraphs of bounded out-valency and relative fixity exceeding a positive constant. [ABSTRACT FROM AUTHOR]

A graph is said to be symmetric if its automorphism group is transitive on its arcs. Guo et al. (Pentavalent symmetric graphs of order 12p, Electron. J. Combin. 18 (2011), no. 1, #P233, DOI: https://doi.org/10.37236/720) and Ling (Classifying pentavalent symmetric graphs of order 24p, Bull. Iranian Math. Soc. 43 (2017), no. 6, 1855–1866) Li and Ling (Symmetric graphs and interconnection networks, Future Gener. Comput. Syst. 83 (2018), no. 1, 461–467, DOI: https://doi.org/10.1016/j.future.2017.05.016) determined all pentavalent symmetric graphs of order 12p12p, 24p24p, and 36p36p. In this article, we shall generalize these results by determining all connected pentavalent symmetric graphs of order 12pq12pq, where p>qp\gt q are distinct primes.

The computation of the clique number of a graph is a fundamental problem in graph theory, which has many applications in computational chemistry, bioinformatics, computer, and social networking. A subset [Formula: see text] of non-negative integers [Formula: see text] is called a numerical semigroup if it is a submonoid of [Formula: see text] and has a finite complement in [Formula: see text]. The graph associated with numerical semigroup [Formula: see text] is denoted by [Formula: see text] and is defined by the vertex set [Formula: see text] and the edge set [Formula: see text]. In this article, we compute the clique number and the minimum degree of those graphs, which can be associated with symmetric numerical semigroups of embedding dimension 2. Moreover, on this basis, we give some bounds for the atom-bond sum-connective index of graphs [Formula: see text] in terms of the harmonic index, the first Zagreb index, the sum-connectivity index, the maximum degree, the minimum degree, the chromatic number, and the clique number.

Let R be a commutative ring with unity. The prime ideal sum graph [Formula: see text] of the ring R is the simple undirected graph whose vertex set is the set of all nonzero proper ideals of R and two distinct vertices I and J are adjacent if and only if I + J is a prime ideal of R. In this paper, we study some interplay between algebraic properties of rings and graph-theoretic properties of their prime ideal sum graphs. In this connection, we classify non-local commutative Artinian rings R such that [Formula: see text] is of crosscap at most two. We prove that there does not exist a non-local commutative Artinian ring whose prime ideal sum graph is projective planar. Further, we classify non-local commutative Artinian rings of genus one prime ideal sum graphs.

In this article, we find the Randić spectrum of the weakly zero-divisor graph of a finite commutative ring [Formula: see text] with identity [Formula: see text], denoted as [Formula: see text], where [Formula: see text] is taken as the ring of integers modulo [Formula: see text]. The weakly zero-divisor graph of the ring [Formula: see text] is a simple undirected graph with vertices representing non-zero zero-divisors in [Formula: see text]. Two vertices, denoted as a and b, are connected if there are elements x in the annihilator of a and y in the annihilator of b such that their product xy equals zero. In particular, we examine the Randić spectrum of [Formula: see text] for specific values of [Formula: see text], which are products of prime numbers and their powers.

A subset Δ of non-negative integers [Formula: see text] is called a numerical semigroup if it is a submonoid of [Formula: see text] and has a finite complement in [Formula: see text]. A graph [Formula: see text] is called a [Formula: see text]-graph if there exists a numerical semigroup Δ with multiplicity α and embedding dimension β such that [Formula: see text] and [Formula: see text]. In this article, we compute the [Formula: see text]-graphs for irreducible and Arf numerical semigroups having a metric dimension of 2. It is proved that if Δ be an irreducible and arf numerical semigroup then there are exactly 2 and 8 non-isomorphic [Formula: see text]-graphs respectively, whose metric dimension is 2.

AbstractConsider a finite group G which acts on itself such that the relation ∼ on G, which is defined by x∼y iff x is a fixed point of y under this action, is both reflexive and symmetric. Let fix(G) represent the set of fixed points of G, i.e., fix(G)={x∈G | xg=x for all g∈G}. We associate with G a new graph using G∖fix(G) as its set of vertices, connecting vertices x,y∈G∖fix(G) iff x is a fixed point of y. This graph is referred to as the stabilizing graph of G and is denoted by Δs(G). Additionally, the complement of the stabilizing graph Δs(G), denoted by ∇s(G), is named the nonstabilizing graph of G. The aim of this study is to analyze various properties of the nonstabilizing graph ∇s(G) and to explore how this graph-theoretical concept relates to the broader understanding of group actions. [ABSTRACT FROM AUTHOR]

AbstractIn this paper, we construct a family of quasi-strongly regular Cayley graphs which is defined on a finite group G with respect to a proper subgroup H of G and denoted by ΓH(G) . We also compute the full automorphism group and characterize various transitivity properties of ΓH(G) for any group G and for any subgroup H of G. [ABSTRACT FROM AUTHOR]

Sandpile groups are a subtle graph isomorphism invariant, in the form of a finite abelian group, whose cardinality is the number of spanning trees in the graph. We study their group structure for graphs obtained by attaching a cone vertex to a tree. For example, it is shown that the number of generators of the sandpile group is at most one less than the number of leaves in the tree. For trees on a fixed number of vertices, the paths and stars are shown to provide extreme behavior, not only for the number of generators, but also for the number of spanning trees, and for Tutte polynomial evaluations that count the recurrent sandpile configurations by their numbers of chips. [ABSTRACT FROM AUTHOR]

A combinatorial approach is given to compute bases for eigenspaces of zero-divisor graphs of finite Boolean rings. A commutative monoid $ \mathcal {S} $ S of graphs is shown to contain a cyclic submonoid $ \mathcal {U} $ U that determines values of the entries of basis elements, while the members of its complement $ \mathcal {S}\setminus \mathcal {U} $ S ∖ U encode the supports of these elements. Furthermore, every member of $ \mathcal {S}\setminus \mathcal {U} $ S ∖ U is associated with a Catalan-triangle number, which counts the number of basis elements whose supports are determined by the given member. This is established by using a combinatorial interpretation of Catalan-triangle numbers to produce linearly independent sets of eigenvectors. [ABSTRACT FROM AUTHOR]

Let G be a finite non-abelian simple group, C a non-identity conjugacy class of G, and ΓC the Cayley graph of G based on C ∪ C − 1 . Our main result shows that in any such graph, there is an involution at bounded distance from the identity. [ABSTRACT FROM AUTHOR]

Let Γ be a simple finite graph with vertex set V (Γ) and edge set E (Γ) . Let R be an equivalence relation on V (Γ) . The R -super Γ graph Γ R is a simple graph with vertex set V (Γ) and two distinct vertices are adjacent if either they are in the same R -equivalence class or there are elements in their respective R -equivalence classes that are adjacent in the original graph Γ . We first show that Γ R is a generalized join of some complete graphs and using this we obtain the adjacency and Laplacian spectrum of conjugacy super commuting graphs and order super commuting graphs of dihedral group D 2 n (n ≥ 3) , generalized quaternion group Q 4 m (m ≥ 2) and the nonabelian group Z p ⋊ Z q of order pq, where p and q are distinct primes with q | (p - 1) . [ABSTRACT FROM AUTHOR]

Consider a commutative ring with unity denoted as R , and let W (R) represent the set of non-unit elements in R . The coannihilator graph of R , denoted as A G ′ (R) , is a graph defined on the vertex set W (R) ∗ . This graph captures the relationships among non-unit elements. Specifically, two distinct vertices, x and y, are connected in A G ′ (R) if and only if either x ∉ x y R or y ∉ x y R , where w R denotes the principal ideal generated by w ∈ R . In the context of this paper, the primary objective is to systematically classify finite rings R based on distinct characteristics of their coannihilator graph. The focus is particularly on cases where the coannihilator graph exhibits a genus or crosscap of two. Additionally, the research endeavors to provide a comprehensive characterization of finite rings R for which the connihilator graph A G ′ (R) attains an outerplanarity index of two. [ABSTRACT FROM AUTHOR]