Pentavalent symmetric graphs of order 2p3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.     

Cubic vertex-transitive non-Cayley graphs of order 12<Emphasis Type="Italic">p</Emphasis>

A graph is said to be vertex-transitive non-Cayley if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive non-Cayley graphs of order 12p, where p is a prime, is given. As a result, there are 11 sporadic and one infinite family of such graphs, of which the sporadic ones occur when p equals 5, 7 or 17, and the infinite family exists if and only if p ≡ 1 (mod 4), and in this family there is a unique graph for a given order.     

Pentavalent symmetric graphs of order 16p

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, a complete classification of connected pentavalent symmetric graphs of order 16p is given for each prime p. It follows from this result that a connected pentavalent symmetric graph of order 16p exists if and only if p = 2 or 31, and that up to isomorphism, there are three such graphs.     

On Isomorphisms of Marušič–Scapellato Graphs

Maru?i?–Scapellato graphs are vertex-transitive graphs of order \(m(2^k + 1)\), where m divides \(2^k - 1\), whose automorphism group contains an imprimitive subgroup that is a quasiprimitive representation of \(\mathrm{SL}(2,2^k)\) of degree \(m(2^k + 1)\). We show that any two Maru?i?–Scapellato graphs of order pq, where p is a Fermat prime, and q is a prime divisor of \(p - 2\), are isomorphic if and only if they are isomorphic by a natural isomorphism derived from an automorphism of \(\mathrm{SL}(2,2^k)\). This work is a contribution towards the full characterization of vertex-transitive graphs of order a product of two distinct primes.     

Arc-Transitive Pentavalent Graphs of Square-Free Order

Hua et al. (Discrete Math 311, 2259–2267, 2011) and Yang et al. (Discrete Math. 339, 522–532, 2016) classify arc-transitive pentavalent graphs of order 2pq and of order 2pqr (with p, q, r distinct odd primes), respectively. In this paper, we extend their results by giving a classification of arc-transitive pentavalent graphs of any square-free order.     

Regular maps of graphs of order 4<Emphasis Type="Italic">p</Emphasis>

A 2-cell embedding f : X → S of a graph X into a closed orientable surface S can be described combinatorially by a pair M = (X;ρ ) called a map, where ρ is a product of disjoint cycle permutations each of which is the permutation of the arc set of X initiated at the same vertex following the orientation of S . It is well known that the automorphism group of M acts semi-regularly on the arc set of X and if the action is regular, then the map M and the embedding f are called regular. Let p and q be primes. Du et al. [J. Algebraic Combin., 19, 123-141 (2004)] classified the regular maps of graphs of order pq . In this paper all pairwise non-isomorphic regular maps of graphs of order 4 p are constructed explicitly and the genera of such regular maps are computed. As a result, there are twelve sporadic and six infinite families of regular maps of graphs of order 4 p ; two of the infinite families are regular maps with the complete bipartite graphs K2p,2p as underlying graphs and the other four infinite families are regular balanced Cayley maps on the groups Z4p , Z22 × Zp and D4p .     

Integral Modular Categories of Frobenius-Perron Dimension <Emphasis Type="Italic">pq</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Integral modular categories of Frobenius-Perron dimension pq ⁿ , where p and q are primes, are considered. It is already known that such categories are group-theoretical in the cases of 0 ≤ n ≤ 4. In the general case we determine that these categories are either group-theoretical or contain a Tannakian subcategory of dimension q ⁱ for i > 1. We then show that all integral modular categories \(\mathcal {C}\) with \(\text {FPdim}(\mathcal {C})=pq^{5}\) are group-theoretical, and, if in addition p < q, all with \(\text {FPdim}(\mathcal {C})=pq^{6}\) or pq ⁷ are group-theoretical. In the process we generalize an existing criterion for an integral modular category to be group-theoretical.     

Classification of tight regular polyhedra

A regular polyhedron of type \(\{p, q\}\) has at least 2pq flags, and it is called tight if it has exactly 2pq flags. The values of p and q for which there exist tight orientably regular polyhedra were previously known. We determine for which values of p and q there is a tight non-orientably regular polyhedron of type \(\{p, q\}\). Furthermore, we completely classify tight regular polyhedra in terms of their automorphism groups.     

Amply regular graphs with Hoffman’s condition

It is known that, if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition: for any generated complete bipartite subgraph K _1,3 (a 3-claw) with parts {p} and {q ₁, q ₂, q ₃}, any vertex distinct from p and adjacent to the vertices q ₁ and q ₂ is adjacent to p but not adjacent to q ₃. We prove the converse statement for amply regular graphs containing a 3-claw and satisfying the condition µ > 1.     

Minimal Translation Hypersurfaces in Euclidean Space

The graph of a function f defined in some open set of the Euclidean space of dimension (p + q) is said to be a translation graph if f may be expressed as the sum of two independent functions ? and ψ defined in open sets of the Euclidean spaces of dimension p and q, respectively. We obtain a useful expression for the mean curvature of the graph of f in terms of the Laplacian, the gradient of ? and ψ as well as of the mean curvatures of their graphs. We study translation graphs having zero mean curvature, that is, minimal translation graphs, by imposing natural conditions on ? and ψ, like harmonicity, minimality and eikonality (constant norm of the gradient), giving several examples as well as characterization results.     

Strongly regular graphs with Hoffman’s condition

It is known that if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition; i.e., for any generated complete bipartite subgraph K _1,3 with parts {p} and {q ₁, q ₂, q ₃}, any vertex distinct from p and adjacent to two vertices from the second part is not adjacent to the third vertex and is adjacent to p. We prove the converse statement, formulated for strongly regular graphs containing a 3-claw and satisfying the condition gm > 1.     

On one test for the switching separability of graphs modulo <Emphasis Type="Italic">q</Emphasis>

We consider graphs whose edges are marked by numbers (weights) from 1 to q - 1 (with zero corresponding to the absence of an edge). A graph is additive if its vertices can be marked so that, for every two nonadjacent vertices, the sum of the marks modulo q is zero, and for adjacent vertices, it equals the weight of the corresponding edge. A switching of a given graph is its sum modulo q with some additive graph on the same set of vertices. A graph on n vertices is switching separable if some of its switchings has no connected components of size greater than n - 2. We consider the following separability test: If removing any vertex from G leads to a switching separable graph then G is switching separable. We prove this test for q odd and characterize the set of exclusions for q even. Connection is established between the switching separability of a graph and the reducibility of the n-ary quasigroup constructed from the graph.     

Locally triangular graphs and normal quotients of the <Emphasis Type="Italic">n</Emphasis>-cube

For an integer \(n\ge 2\), the triangular graph has vertex set the 2-subsets of \(\{1,\ldots ,n\}\) and edge set the pairs of 2-subsets intersecting at one point. Such graphs are known to be halved graphs of bipartite rectagraphs, which are connected triangle-free graphs in which every 2-path lies in a unique quadrangle. We refine this result and provide a characterisation of connected locally triangular graphs as halved graphs of normal quotients of n-cubes. To do so, we study a parameter that generalises the concept of minimum distance for a binary linear code to arbitrary automorphism groups of the n-cube.     

Recognition of characteristically simple group <Emphasis Type="Italic">A</Emphasis><Subscript>5</Subscript> × <Emphasis Type="Italic">A</Emphasis><Subscript>5</Subscript> by character degree graph and order

The character degree graph of a finite group G is the graph whose vertices are the prime divisors of the irreducible character degrees of G and two vertices p and q are joined by an edge if pq divides some irreducible character degree of G. It is proved that some simple groups are uniquely determined by their orders and their character degree graphs. But since the character degree graphs of the characteristically simple groups are complete, there are very narrow class of characteristically simple groups which are characterizable by this method.We prove that the characteristically simple group A₅ × A₅ is uniquely determined by its order and its character degree graph. We note that this is the first example of a non simple group which is determined by order and character degree graph. As a consequence of our result we conclude that A₅ × A₅ is uniquely determined by its complex group algebra.     

Solvability of the problem of taking the discrete logarithm

It is proved that consideration of the solvability problem for taking the discrete logarithm in a residue ring modulo composite M can be reduced to consideration of a similar problem in residue rings modulo pq, where p and q are prime divisors of M. For moduli of form pq, necessary and sufficient conditions for solvability checking are obtained in some cases. In addition, the problem of raising a solution of an exponential comparison in a residue ring modulo p ^α is solved.     

Positive solutions of <Emphasis Type="Italic">p</Emphasis>-th Yamabe type equations on graphs

Let G = (V,E) be a finite connected weighted graph, and assume 1 ? α ? p ? q. In this paper, we consider the p-th Yamabe type equation ―?_pu+hu^q―1 = λfu^α―1 on G, where ?_p is the p-th discrete graph Laplacian, h < 0 and f > 0 are real functions defined on all vertices of G. Instead of H. Ge’s approach [Proc. Amer. Math. Soc., 2018, 146(5): 2219–2224], we adopt a new approach, and prove that the above equation always has a positive solution u > 0 for some constant λ ∈ ?. In particular, when q = p, our result generalizes Ge’s main theorem from the case of α ? p > 1 to the case of 1 ? α ? p, It is interesting that our new approach can also work in the case of α ? p > 1.     

The Number of Labeled Outerplanar <Emphasis Type="Italic">k</Emphasis>-Cyclic Graphs

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.     

Some remarks on symmetrical extensions of graphs

It is proved that results from a previous paper of the author on symmetrical 2-extensions of graphs can be extended to symmetrical p-extensions of graphs for any prime p. In particular, it is proved that, for any prime p, there are only finitely many symmetrical p-extensions of a locally finite graph with an abelian subgroup of finite index in its automorphism group. Some refinements of these results are also obtained. In addition, we consider the question on the possibility to represent symmetrical extensions of a d-dimensional grid (and similar graphs) in the d-dimensional affine Euclidean space in such a way that a corresponding vertex-transitive group of automorphisms of the extension is induced by some crystallographic group of motions of the space.     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-factorization of complete bipartite multigraphs

Let λK _m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K _p,q -factorization of λK _m,n is a set of edge-disjoint K _p,q -factors of λK _m,n which partition the set of edges of λK _m,n . When p = 1 and q is a prime number, Wang, in his paper [On K _1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K _1,q -factorization of K _m,n and gave a sufficient condition for such a factorization to exist. In papers [K _1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K _p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK _m,n to have a K _p,q -factorization. As a special case, it is shown that the necessary condition for the K _p,q -factorization of λK _m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.