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.
It has been conjectured that every fullerene, that is, every skeleton of a spherical trivalent graph whose set of faces consists of pentagons and hexagons alone, is Hamiltonian. In this article the ...validity of this conjecture is explored for the class of leapfrog-fullerenes. It is shown that, given an arbitrary fullerene F, the corresponding leapfrog-fullerene Le(F) contains a Hamilton cycle if the number of vertices of F is congruent to 2 modulo 4 and contains a long cycle missing out only two adjacent vertices, and thus also a Hamilton path, if the number of vertices of F is divisible by 4.
A graph-theoretic environment is used to study the connection between imprimitivity and semiregularity, two concepts arising naturally in the context of permutation groups. Among other, it is shown ...that a connected arc-transitive graph admitting a nontrivial automorphism with two orbits of odd length, together with an imprimitivity block system consisting of blocks of size 2, orthogonal to these two orbits, is either the canonical double cover of an arc-transitive circulant or the wreath product of an arc-transitive circulant with the empty graph
K
¯
2
on two vertices.
A nonidentity element of a permutation group is said to be semiregular provided all of its cycles in its cycle decomposition are of the same length. It is known that semiregular elements exist in ...transitive 2-closed permutation groups of square-free degree and in some special cases when the degree is divisible by a square of a prime. In this paper it is shown that semiregular elements exist in transitive 2-closed permutation groups of the following degrees
16p, where
is a prime,
where
is a prime,
12pq, where
are primes,
and either
or
18pq, where
are primes and
where
are primes, and
or qr < s, and
4pqrs, where
are primes, pqr < s,
and
As a corollary, a 2-closed transitive permutation group of degree
and different from 72 and 96 contains semiregular elements.
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.
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.
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.
PDF
