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.
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 vertex-set with two orbits of equal size. A bi-Cayley graph over a ...dicyclic group is called a bi-dicirculant. We give a classification of tetravalent connected vertex-transitive bi-dicirculants in this paper. As a byproduct, we prove that all connected tetravalent vertex-transitive bi-dicirculants are Cayley graphs.
Two-sided Group Digraphs and Graphs Iradmusa, Moharram N.; Praeger, Cheryl E.
Journal of graph theory,
07/2016, Volume:
82, Issue:
3
Journal Article
Peer reviewed
We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets L,R of a group G, we define the two‐sided group digraph 2S⃗(G;L,R) to have vertex ...set G, and an arc from x to y if and only if y=ℓ−1xr for some ℓ∈L and r∈R. In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which 2S⃗(G;L,R) may be viewed as a simple graph of valency |L|·|R|, and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.
A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal ...cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique
C in a vertex‐transitive graph
Γ is strong if and only if
∣
C
∣
∣
I
∣
=
∣
V
(
Γ
)
∣ for every maximal independent set
I of
Γ. On the basis of this result we prove that a vertex‐transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex‐transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5‐valent vertex‐transitive graphs admitting a strong clique. Our results imply that every vertex‐transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex‐transitive CIS graph which is not localizable.
The primary purpose of this paper is to report on the successful enumeration in Magma of representatives of the 195826352 conjugacy classes of transitive subgroups of the symmetric group S48 of ...degree 48. In addition, we have determined that 25707 of these groups are minimal transitive and that 713 of them are elusive. The minimal transitive examples have been used to enumerate the vertex-transitive groups of degree 48, of which there are 1538868366, all but 0.1625% of which arise as Cayley graphs. We have also found that the largest number of elements required to generate any of these groups is 10, and we have used this fact to improve previous general bounds of the third author on the number of elements required to generate an arbitrary transitive permutation group of a given degree. The details of the proof of this improved bound will be published as a separate paper.
Given a graph Γ, a perfect code in Γ is an independent set C of Γ such that every vertex outside C is adjacent to a unique vertex in C and a total perfect code in Γ is a set C of vertices of Γ such ...that every vertex of Γ is adjacent to a unique vertex in C. To study (total) perfect codes in vertex-transitive graphs, we generalize the concept of subgroup (total) perfect code of a finite group introduced by Huang et al. as follows: Given a finite group G and a subgroup H of G, a subgroup A of G containing H is called a subgroup (total) perfect code of the pair (G,H) if there exists a coset graph Cos(G,H,U) such that the set consisting of left cosets of H in A is a (total) perfect code in Cos(G,H,U). We give a necessary and sufficient condition for a subgroup A of G containing H to be a (total) perfect code of the pair (G,H) and generalize a few known results of subgroup (total) perfect codes of groups. We also construct some examples of subgroup perfect codes of the pair (G,H) and propose a few problems for further research.
Abstract
Let
$\Gamma $
be a graph of valency at least four whose automorphism group contains a minimally vertex-transitive subgroup
G
. It is proved that
$\Gamma $
admits a nowhere-zero
$3$
-flow if ...one of the following two conditions holds: (i)
$\Gamma $
is of order twice an odd number and
G
contains a central involution; (ii)
G
is a direct product of a
$2$
-subgroup and a subgroup of odd order.
In this paper, a complete classification of finite simple cubic vertex-transitive graphs of girth 6 is obtained. It is proved that every such graph, with the exception of the Desargues graph on 20 ...vertices, is either a skeleton of a hexagonal tiling of the torus, the skeleton of the truncation of an arc-transitive triangulation of a closed hyperbolic surface, or the truncation of a 6-regular graph with respect to an arc-transitive dihedral scheme. Cubic vertex-transitive graphs of girth larger than 6 are also discussed.
We describe two similar but independently-coded computations used to construct a complete catalogue of the transitive groups of degree less than 48, thereby verifying, unifying and extending the ...catalogues previously available. From this list, we construct all the vertex-transitive graphs of order less than 48. We then present a variety of summary data regarding the transitive groups and vertex-transitive graphs, focusing on properties that seem to occur most frequently in the study of groups acting on graphs. We illustrate how such catalogues can be used, first by finding a complete list of the elusive groups of order at most 47 and then by completely determining which groups of order at most 47 are CI groups.
In the generalized truncation construction, one replaces each vertex of a k-regular graph Γ with a copy of a graph ϒ of order k. We investigate the symmetry properties of the graphs constructed in ...this way, especially in connection to the symmetry properties of the graphs Γ and ϒ used in the construction. We demonstrate the usefulness of our results by using them to obtain a classification of cubic vertex-transitive graphs of girths 3, 4, and 5.
PDF
