Search

A simple graph is called semisymmetric if it is regular and edge-transitive but not vertex-transitive. Let p be an arbitrary prime. Folkman [J. Folkman, Regular line-symmetric graphs, J. Combinatorial Theory, 3 (1967) 215-232.] proved that there are no cubic semisymmetric graphs of order 2p or 2p². In this paper, an extension of his result in the case of cubic graphs of order 44p or 44p² is given. By using group theoretic methods, we prove that there are no connected cubic semisymmetric graphs of order 44p or 44p². [ABSTRACT FROM AUTHOR]

Let p be a prime. In this paper, a complete classification of edge-transitive N -covers of a cubic symmetric graph of order 2 p is given for the case when N is a two-generator 2-group whose derived subgroup is either isomorphic to Z 2 3 or generated by at most two elements. As an application, it is shown that 11 is the smallest value of n for which there exist infinitely many cubic semisymmetric graphs with order of the form 2 n p. [ABSTRACT FROM AUTHOR]

A regular graph is semisymmetric if its automorphism group acts transitively on the edge set but not on the vertex set. In this article, we give a complete list of connected semisymmetric graphs of square‐free order and valency 5. The list consists of a single graph, the incidence graph of a generalized hexagon of order (4,4) $(4,4)$, and an infinite family arising from some groups with cyclic Fitting subgroup. [ABSTRACT FROM AUTHOR]

As a variant of Q n , Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484–490] introduced the balanced hypercube B H n as an interconnection network topology for computing systems. In this paper, we show that B H n is a lexicographic product of two graphs, and using this, we show that every minimum cyclic vertex-cut of B H n isolates a 4-cycle, and prove that the edge neighbor connectivity of B H n is 2 n. [ABSTRACT FROM AUTHOR]

A simple graph is called semisymmetric if it is regular and edge-transitive but not vertex-transitive. Let p be an arbitrary prime. Folkman proved [Regular line-symmetric graphs, J. Combin. Theory 3 (1967) 215-232] that there is no semisymmetric graph of order 2p or 2p2. In this paper an extension of his result in the case of cubic graphs of order 20p2 is given. We prove that there is no connected cubic semisymmetric graph of order 20p2 or, equivalently, that every connected cubic edge-transitive graph of order 20p2 is necessarily symmetric. [ABSTRACT FROM AUTHOR]

A simple graph is called semisymmetric if it is regular and edge-transitive but not vertex-transitive. In this paper we classify all connected cubic semisymmetric graphs of order 20p, p prime. [ABSTRACT FROM AUTHOR]

A graph is called half-arc-transitive if its full automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, we classify hexavalent half-arc-transitive graphs of order 9 p for each prime p. As a result, there are four infinite families of such graphs: three defined on Z p ⋊ Z 27 with 27 | (p − 1) ; one defined on Z 3 p ⋊ Z 9 with 9 | (p − 1). [ABSTRACT FROM AUTHOR]

A graph is said to be a bi-Cayley graph over a group H if it admits H as a group of automorphisms acting semiregularly on its vertices with two orbits. A non-abelian group is called an inner-abelian group if all of its proper subgroups are abelian. In this article, we complete the classification of connected cubic edge-transitive bi-Cayley graphs over inner-abelian p-groups for an odd prime p. [ABSTRACT FROM AUTHOR]

An edge-transitive graph $$\varGamma $$ is called alternatively connected if a subgroup G of the automorphism group of $$\varGamma $$ has two orbits on the arc set of $$\varGamma $$ , and there exists an alternative walk (with respect to a given G-orbit on arcs) between every pair of vertices of $$\varGamma $$ . Employing the standard double covers of digraphs, we give some basic properties of alternatively connected edge-transitive graphs. The main result of this paper is a reduction result on alternatively connected edge-transitive graphs of square-free order. As an application of this result, we give a characterization for alternatively connected edge-transitive graphs of square-free order and valency 6. It is proved that such a graph is either a circulant or constructed from $$\mathrm{PSL}(2,p)$$ . [ABSTRACT FROM AUTHOR]

A connected graph G is strongly Menger edge connected (SM - λ for short) if any two of its vertices x , y are connected by min ⁡ { d (x) , d (y) } edge-disjoint paths, where d (x) is the degree of x. The maximum edge-fault-tolerant with respect to the SM - λ property of G , denoted by s m λ (G) , is the maximum integer m such that G − F is still SM - λ for any edge-set F with | F | ≤ m. In this paper, we give a sharp lower and upper bound for s m λ (G) , and give a characterization of the minimum upper bound. Furthermore, for k -regular graphs, we give some examples to show that s m λ (G) can reach every value between the lower bound and the upper bound when k is odd; show that s m λ (G) can reach every even value between the lower bound and the upper bound, and the only possible odd value is k − 1 if k is even. Moreover, we completely determine the exact value of s m λ (G) when G is a vertex-transitive graph or when it is an edge-transitive graph. [ABSTRACT FROM AUTHOR]

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G o H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G o H is non-trivial and complete, then G o H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao [11]. For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph. [ABSTRACT FROM AUTHOR]

A vector is called nowhere-zero if it has no zero entry. In this article we search for graphs with nowhere-zero eigenvectors. We prove that distance-regular graphs and vertex-transitive graphs have nowhere-zero eigenvectors for all of their eigenvalues and edge-transitive graphs have nowhere-zero eigenvectors for all non-zero eigenvalues. Among other results, it is shown that a graph with three distinct eigenvalues has a nowhere-zero eigenvector for its smallest eigenvalue. [ABSTRACT FROM AUTHOR]

Abstract: A classification is given for connected edge-transitive tetravalent Cayley graphs of square-free order. The classification shows that, with a few exceptions, a connected edge-transitive tetravalent Cayley graph of square-free order is either arc-regular or edge-regular. It thus provides a generic construction of half-transitive graphs of valency 4. [Copyright &y& Elsevier]

Abstract: In this paper, we first prove that each biquasiprimitive permutation group containing a regular dihedral subgroup is biprimitive, and then give a classification of such groups. The classification is then used to classify vertex-quasiprimitive and vertex-biquasiprimitive edge-transitive dihedrants. Moreover, a characterization of valencies of normal edge-transitive dihedrants is obtained, and some classes of examples with certain valences are constructed. [Copyright &y& Elsevier]

Abstract: A regular cover of a graph is said to be an edge-transitive cover if the fibre-preserving automorphism subgroup acts edge-transitively on the covering graph. In this paper we classify edge-transitive regular -covers of the Heawood graph, and obtain a new infinite family of one-regular cubic graphs. Also, as an application of the classification of edge-transitive regular -covers of the Heawood graph, we prove that any bipartite edge-transitive cubic graph of order is isomorphic to a normal Cayley graph of dihedral group if the prime . [Copyright &y& Elsevier]

Abstract: Given natural numbers and , the rose window graph is a quartic graph with vertex set and edge set . In this paper rotary maps on rose window graphs are considered. In particular, we answer the question posed in [S. Wilson, Rose window graphs, Ars Math. Contemp. 1 (2008), 7–19. http://amc.imfm.si/index.php/amc/issue/view/5] concerning which of these graphs underlie a rotary map. [Copyright &y& Elsevier]

Abstract: A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. In this paper, we show that there is no tetravalent half-arc-transitive graph of order . [Copyright &y& Elsevier]

Abstract: For a connected finite graph and a subset of its vertex set, a distance-residual subgraph is a subgraph induced on the set of vertices at the maximal distance from . Some properties and examples of distance-residual subgraphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are presented. The relations between the distance-residual subgraphs of product graphs and their factors are explored. [Copyright &y& Elsevier]

An undirected graph without isolated vertices is said to be semisymmetric if its full automorphism group acts transitively on its edge set but not on its vertex set. In this paper, we inquire the existence of connected semisymmetric cubic graphs of order 16p². It is shown that for every odd prime p, there exists a semisymmetric cubic graph of order 16p² and its structure is explicitly specified by giving the corresponding voltage rules generating the covering projections. [ABSTRACT FROM AUTHOR]

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ℤd. In this article we prove that for each d > 1 the set of Cayley graphs of ℤd presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ℤd that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ℤd with crystallographic groups. [ABSTRACT FROM AUTHOR]

Abstract: A -arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In all previously known constructions of quartic -arc-transitive graphs, vertex stabilizers are isomorphic to or to . In this article, for each positive integer , an infinite family of quartic -arc-transitive graphs having vertex stabilizers isomorphic to is constructed. [Copyright &y& Elsevier]

An infinite family of cubic edge- but not vertex-transitive graphs is constructed. The graphs are obtained as regular Zn-covers of K3,3 where n=p1e1p2e2⋯pkek where pi are distinct primes congruent to 1 modulo 3, and ei&ges;1. Moreover, it is proved that the Gray graph (of order 54) is the smallest cubic edge- but not vertex-transitive graph. [Copyright &y& Elsevier]

An infinite familiy of 1/2-arc-transitive graphs of valency 4 with alternating cycles of length 4 is given. Besides, an infinite family of 1/2-arc-transitive graphs of valency 4 with alternating cycles of length 4 is given. Besides, an infinite family of 1/2-arc-transitive graphs of valency 4 with vertex stabilizer isomorphic to Z2×Z2 is constructed. [Copyright &y& Elsevier]