Two elements
g
,
h
of a permutation group
G
acting on a set
V
are said to be
intersecting
if
g
(
v
)
=
h
(
v
)
for some
v
∈
V
. More generally, a subset
F
of
G
is an
intersecting set
if every pair ...of elements of
F
is intersecting. The intersection density
ρ
(
G
)
of a transitive permutation group
G
is the maximum value of the quotient
|
F
|
/
|
G
v
|
where
F
runs over all intersecting sets in
G
and
G
v
is the stabilizer of
v
∈
V
. A vertex-transitive graph
X
is
intersection density stable
if any two transitive subgroups of
Aut
(
X
)
have the same intersection density. This paper studies the above concepts in the context of cubic symmetric graphs. While a 1-regular cubic symmetric graph is necessarily intersection density stable, the situation for 2-arc-regular cubic symmetric graphs is more complex. A necessary condition for a 2-arc-regular cubic symmetric graph admitting a 1-arc-regular subgroup of automorphisms to be intersection density stable is given, and an infinite family of such graphs is constructed.
A step forward is made in a long standing Lovász problem regarding existence of Hamilton paths in vertex-transitive graphs. It is shown that a vertex-transitive graph of order a product of two primes ...arising from a primitive action of PSL(2;
p
) on the cosets of a subgroup isomorphic to
D
p
−1
has a Hamilton cycle. Essential tools used in the proof range from classical results on existence of Hamilton cycles, such as Chvátal's theorem and Jackson's theorem, to certain results from matrix algebra, graph quotienting, and polynomial representations of quadratic residues in terms of primitive roots in finite fields. Also, Hamilton cycles are proved to exist in vertex-transitive graphs of order a product of two primes arising from a primitive action of either
PΩ
(2
d
; 2),
M
22
,
A
7
, PSL(2; 13), or PSL(2; 61). The results of this paper, combined together with other known results, imply that all connected vertex-transitive graphs of order a product of two primes, except for the Petersen graph, have a Hamilton cycle.
A finite simple graph is called a
k
-multicirculant if its automorphism group contains a cyclic semiregular subgroup having
k
orbits on the vertex set. It was shown by Giudici et al. that, if
k
is ...squarefree and coprime to 6, then a cubic arc-transitive
k
-multicirculant has at most
6
k
2
vertices (J. Combin. Theory Ser. B, 2017). In this paper, we classify the latter graphs under the assumption that their semiregular cyclic subgroups are contained in a soluble group of automorphisms acting transitively on the arc set of the graphs. As an application, cubic arc-transitive
p
-multicirculants are completely described for each odd prime
p
.
Symmetric cubic graphs via rigid cells Conder, Marston D. E.; Hujdurović, Ademir; Kutnar, Klavdija ...
Journal of algebraic combinatorics,
05/2021, Volume:
53, Issue:
3
Journal Article
Peer reviewed
Open access
Properties of symmetric cubic graphs are described via their
rigid cells
, which are maximal connected subgraphs fixed pointwise by some involutory automorphism of the graph. This paper completes the ...description of rigid cells and the corresponding involutions for each of the 17 ‘action types’ of symmetric cubic graphs.
In this article current directions in solving Lovász’s problem about the existence of Hamilton cycles and paths in connected vertex-transitive graphs are given.
We introduce a special kind of partial sum families, which we call equisizable partial sum families, that can be used to obtain directed strongly regular graphs admitting a semiregular group of ...automorphisms. We give a construction of an infinite family of equisizable partial sum families depending on two parameters that produce directed strongly regular graphs with new parameters. We also determine the automorphisms group of the associated directed strongly regular graphs in terms of the parameters.
QUASI m-CAYLEY STRONGLY REGULAR GRAPHS Kutnar, Klavdija; Malnic, Aleksander; Martinez, Luis ...
Journal of the Korean Mathematical Society,
11/2013, Volume:
50, Issue:
6
Journal Article
Peer reviewed
Open access
We introduce a new class of graphs, called quasi m-Cayleygraphs, having good symmetry properties, in the sense that they admita group of automorphisms G that fixes a vertex of the graph and ...actssemiregularly on the other vertices. We determine when these graphs arestrongly regular, and this leads us to define a new algebro-combinatorialstructure, called quasi-partial difference family, or QPDF for short. Wegive several infinite families and sporadic examples of QPDFs. We alsostudy several properties of QPDFs and determine, under several condi-tions, the form of the parameters of QPDFs when the group G is cyclic. KCI Citation Count: 5
An automorphism ρ of a graph X is said to be semiregular provided all of its cycles in its cycle decomposition are of the same length, and is said to be simplicial if it is semiregular and the ...quotient multigraph Xρ of X with respect to ρ is a simple graph, and thus of the same valency as X. It is shown that, with the exception of the complete graph K4, the Petersen graph, the Coxeter graph and the so called H-graph (alternatively denoted as S(17), the smallest graph in the family of the so called Sextet graphs S(p), p≡±1(mod16)), every cubic arc-transitive graph with a primitive automorphism group admits a simplicial automorphism.
When dealing with symmetry properties of mathematical objects, one of the fundamental questions is to determine their full automorphism group. In this paper this question is considered in the context ...of even/odd permutations dichotomy. More precisely: when is it that the existence of automorphisms acting as even permutations on the vertex set of a graph, called even automorphisms, forces the existence of automorphisms that act as odd permutations, called odd automorphisms. As a first step towards resolving the above question, complete information on the existence of odd automorphisms in cubic symmetric graphs is given.