Search

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]

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 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.

A graph Γ is G-symmetric if it admits G as a group of automorphisms acting transitively on the set of arcs of Γ , where an arc is an ordered pair of adjacent vertices. Let Γ be a G-symmetric graph such that its vertex set admits a nontrivial G-invariant partition B , and let D (Γ , B) be the incidence structure with point set B and blocks { B } ∪ Γ B (α) , for B ∈ B and α ∈ B , where Γ B (α) is the set of blocks of B containing at least one neighbor of α in Γ . In this paper, we classify all G-symmetric graphs Γ such that Γ B (α) ≠ Γ B (β) for distinct α , β ∈ B , the quotient graph of Γ with respect to B is a complete graph, and D (Γ , B) is isomorphic to the complement of a (G, 2)-point-transitive linear space. [ABSTRACT FROM AUTHOR]

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.