It is proved that in a finite field F of prime order p, where p is not one of finitely many exceptions, for every polynomial f(x) in F[x] of degree 4 that has a nonzero constant term and is not of the form ag(x)^2 there exists a primitive root b in F such that f(b) is a quadratic residue in F. This refines the result of Madden and Velez from 1982 about polynomials that represent quadratic residues at primitive roots and represents essential ingredient in the proof that connected graphs in a particular family of primitive vertex-transitive graphs of order a product of two primes admit Hamilton cycles.
COBISS.SI-ID: 1541859268
Tetravalent graphs admitting a half-arc-transitive subgroup of automorphisms, that is a subgroup acting transitively on its vertices and its edges but not on its arcs, are investigated. One of the most fruitful approaches for the study of structural properties of such graphs is the well known paradigm of alternating cycles and their intersections which was introduced by Marušič 20 years ago. In this paper a new parameter for such graphs, giving a further insight into their structure, is introduced. Various properties of this parameter are given and the parameter is completely determined for the tightly attached examples in which any two non-disjoint alternating cycles meet in half of their vertices. Moreover, the obtained results are used to establish a link between two frameworks for a possible classification of all tetravalent graphs admitting a half-arc-transitive subgroup of automorphisms, the one proposed by Marušič and Praeger in 1999, and the much more recent one proposed by Al-bar, Al-kenai, Muthana, Praeger and Spiga which is based on the normal quotients method. New results on the graph of alternating cycles of a tetravalent graph admitting a half-arc-transitive subgroup of automorphisms are obtained. A considerable step towards the complete answer to the question of whether the attachment number necessarily divides the radius in tetravalent half-arc-transitive graphs is made.
COBISS.SI-ID: 1540554436
Let p: Y -) X be a regular covering projection of connected graphs, where CT(p) denotes the group of covering transformations. Suppose that a group G ( Aut(X) lifts along p to a group H ( Aut(Y). The corresponding short exact sequence id -) CT(p) -) H -) G -) id is split sectional over a G-invariant subset S of vertices of X if there exists a sectional complement, that is, a complement G' to CT(p) with a G'-invariant section S' over S. Such lifts do not split just abstractly but also permutationally in the sense that they enable a nice combinatorial description. Sectional complements are characterized from several viewpoints. The connection between the number of sectional complements and invariant sections on one side, and the structure of the split extension itself on the other, is analyzed. In the case when CT(p) is abelian and the covering projection is given implicitly in terms of a voltage assignment on the base graph X, an efficient algorithm for testing whether H has a sectional complement is presented.
COBISS.SI-ID: 1540135364