On the classification of quartic half-arc-transitive metacirculants

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1 and n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ^m has at least one fixed vertex. In a recent paper Maruši? and the author showed that each connected quartic half-arc-transitive metacirculant belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph relative to the semiregular automorphism ρ. One of these classes coincides with the class of the so-called tightly-attached graphs, which have already been completely classified. In this paper a complete classification of the second of these classes, that is the class of quartic half-arc-transitive metacirculants for which the quotient graph relative to the semiregular automorphism ρ is a cycle with a loop at each vertex, is given.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

Tetravalent half-arc-transitive graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2p ² exist and a tetravalent half-arc-transitive graph of order 4p must be non-Cayley; such a non-Cayley graph exists if and only if p−1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41–76, 1998), in this paper the connected tetravalent half-arc-transitive graphs of order 2pq are classified for distinct odd primes p and q.     

Almost all quartic half-arc-transitive weak metacirculants of Class II are of Class IV

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. A weak metacirculant is a graph admitting a transitive metacyclic group that is a group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1 and n≥2, and where σ normalizes ρ. It was shown in [D. Maruši?, P. Šparl, On quartic half-arc-transitive metacirculants, J. Algebr. Comb. 28 (2008) 365-395] that each connected quartic half-arc-transitive weak metacirculant X belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph X_ρ relative to the semiregular automorphism ρ. The first of these classes, called Class I, coincides with the class of so-called tightly attached graphs. Class II consists of the quartic half-arc-transitive weak metacirculants for which the quotient graph X_ρ is a cycle with a loop at each vertex. Class III consists of those graphs for which each vertex of the quotient graph X_ρ is connected to three other vertices, to one with a double edge. Finally, Class IV consists of those graphs for which X_ρ is a simple quartic graph.This paper consists of two results concerning graphs of Class II. It is shown that, with the exception of the Doyle-Holt graph and its canonical double cover, each quartic half-arc-transitive weak metacirculant of Class II is also of Class IV. It is also shown that although quartic half-arc-transitive weak metacirculants of Class II which are not tightly attached exist they are “almost tightly attached”. More precisely, their radius is at most four times their attachment number.     

On quartic half-arc-transitive metacirculants

Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1, n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ ^m has at least one fixed vertex. A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In this article quartic half-arc-transitive metacirculants are explored and their connection to the so called tightly attached quartic half-arc-transitive graphs is explored. It is shown that there are three essentially different possibilities for a quartic half-arc-transitive metacirculant which is not tightly attached to exist. These graphs are extensively studied and some infinite families of such graphs are constructed. Both authors were supported in part by “ARRS – Agencija za znanost Republike Slovenije”, program no. P1-0285.     

Mixed sums of squares and triangular numbers (III)

In this paper we confirm a conjecture of Sun which states that each positive integer is a sum of a square, an odd square and a triangular number. Given any positive integer m, we show that p=2m+1 is a prime congruent to 3 modulo 4 if and only if Tm=m(m+1)/2 cannot be expressed as a sum of two odd squares and a triangular number, i.e., p²=x²+8(y²+z²) for no odd integers x,y,z. We also show that a positive integer cannot be written as a sum of an odd square and two triangular numbers if and only if it is of the form 2Tm(m>0) with 2m+1 having no prime divisor congruent to 3 modulo 4.     

Periodic solutions for a higher order p-Laplacian neutral functional differential equation with a deviating argument

In this paper, a higher order p-Laplacian neutral functional differential equation with a deviating argument:

[φ_p([x(t)−c(t)x(t−σ)]⁽ⁿ⁾)]^(m)+f(x(t))x^′(t)+g(t,x(t−τ(t)))=e(t)     

On correspondence between solutions of a family of cubic Thue equations and isomorphism classes of the simplest cubic fields

Let m?−1 be an integer. We give a correspondence between integer solutions to the parametric family of cubic Thue equations

X³−mX²Y−(m+3)XY²−Y³=λ     

Arc-regular cubic graphs of order four times an odd integer

A graph is arc-regular if its automorphism group acts sharply-transitively on the set of its ordered edges. This paper answers an open question about the existence of arc-regular 3-valent graphs of order 4m where m is an odd integer. Using the Gorenstein?CWalter theorem, it is shown that any such graph must be a normal cover of a base graph, where the base graph has an arc-regular group of automorphisms that is isomorphic to a subgroup of Aut(PSL(2,q)) containing PSL(2,q) for some odd prime-power?q. Also a construction is given for infinitely many such graphs??namely a family of Cayley graphs for the groups PSL(2,p ³) where p is an odd prime; the smallest of these has order?9828.     

Diameter vulnerability of graphs

Let f(t, D) denote the maximum possible diameter of a graph obtained from a (t+1)-edge-connected graph of diameter D by deleting t edges. F.R.K. Chung and M.R. Garey have shown that for D≥4,(t+1)(D?2)≤ f(t, D)≤(t+1)D+t. Here we consider the cases D=2 and D=3 and show that f(t,2)=4 and $\text{3}\text{2t}\text{?3≤f(t,3)≤3}\text{2t}\text{+4}$ if t is large enough. We solve also the problem for the directed case (answering a question of F.R.K. Chung and M.R. Garey) by showing that if D ≥ 3 the diameter of a diagraph obtained from a (t + 1)-arc-connected digraph of order n by deleting t arcs is at most n?2t+1. In the case D=.....2, the maximum possible diameter of the resulting digraph is (like in the undirected case) 4. We also consider the same problem for vertices.     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

Coprime ordering of cyclic planar difference sets

Motivated by a question about uniform dessins d’enfants, it is conjectured that every cyclic planar difference set of prime power order m≠4 can be cyclically ordered such that the difference of every pair of neighbouring elements is coprime to the module v?m²+m+1. We prove that this is the case whenever the number ω(v) of different prime divisors of v is less than or equal to 3. To achieve this we consider a graph related to the difference set and show that it is Hamiltonian.     

Proper partial geometries with Singer groups and pseudogeometric partial difference sets

A partial geometry admitting a Singer group G is equivalent to a partial difference set in G admitting a certain decomposition into cosets of line stabilizers. We develop methods for the classification of these objects, in particular, for the case of abelian Singer groups. As an application, we show that a proper partial geometry Π=pg(s+1,t+1,2) with an abelian Singer group G can only exist if t=2(s+2) and G is an elementary abelian 3-group of order ³(s+1) or Π is the Van Lint-Schrijver partial geometry. As part of the proof, we show that the Diophantine equation (m³−1)/2=(²rw−1)/(r²−1) has no solutions in integers m,r?1, w?2, settling a case of Goormaghtigh's equation.     

Construction of universal one-way hash functions: Tree hashing revisited

We present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t?2, our algorithm extends the domain from the set of all n-bit strings to the set of all ((2^t-1)(n-m)+m)-bit strings, where m is the length of the message digest. The associated increase in key length is 2m bits for t=2; m(t+1) bits for 3?t?6 and m×(t+⌊log₂(t-1)⌋) bits for t?7.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

On cycles in regular 3-partite tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

An algorithm for Gauss-Romberg integration

WhenR ^(m) f is anm copy version of a quadrature ruleRf, the error functional satisfies an asymptotic expansion $$R^{(m)} f - If \simeq d_2 h^2 + d_4 h^4 + ...,m = 1/h.$$ In the conventional form of Romberg Integration,Rf is the trapezoidal rule and early terms of this expansion are “eliminated.” For this purpose the Neville-Romberg algorithm is used to construct the conventionalT-table. IfRf is taken to be a ruleGf of polynomial degree 2t+1 the firstt terms in this expansion are in any case zero. A generalization of the Neville-Romberg algorithm is derived. This “eliminates” termsd _2s h ^2s ,s=t+1,t+2, ... An associatedG-table is defined and some of its properties are noted.