Interconnection networks for parallel molecular dynamics simulation based on hamiltonian cubic symmetric topology

A class of interconnection networks for efficient parallel MD simulations based on hamiltonian cubic symmetric graphs is presented. The cubic symmetric graphs have many desirable properties as interconnection networks since they have a low degree and are vertex- and edge-transitive. We present a method for scheduling collective communication routines that are used in parallel MD and are based on the property that the graphs in question have a Hamilton cycle, that is, a cycle going through all vertices of the graph. Analyzing these communication routines shows that hamiltonian cubic symmetric graphs of small diameter are good candidates for a topology that gives rise to an interconnection network with excellent properties, allowing faster communication and thus speeding up parallel MD simulation.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Symmetric cubic graphs via rigid cells

Journal of Algebraic Combinatorics - Properties of symmetric cubic graphs are described via their rigid cells, which are maximal connected subgraphs fixed pointwise by some involutory automorphism...     

Distance-balanced graphs: Symmetry conditions

A graph X is said to be distance-balanced if for any edge uv of X, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. A graph X is said to be strongly distance-balanced if for any edge uv of X and any integer k, the number of vertices at distance k from u and at distance k+1 from v is equal to the number of vertices at distance k+1 from u and at distance k from v. Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP(n,2), GP(5k+1,k), GP(3k±3,k), and GP(2k+2,k).     

Chirality of toroidal molecular graphs

Symmetry properties of a class of toroidal molecular graphs, arising as covers of certain bipartite cubic Cayley graphs of dihedral groups, are studied. Although these symmetries make all vertices and all edges indistinguishable, they imply intrinsic chirality.     

Hamilton paths and cycles in vertex-transitive graphs of order

It is shown that every connected vertex-transitive graph of order 6p, where p is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order 6p which is not genuinely imprimitive contains a Hamilton cycle.     

On the anti-Kekulé number of leapfrog fullerenes

The Anti-Kekulé number of a connected graph G is the smallest number of edges that have to be removed from G in such way that G remains connected but it has no Kekulé structures. In this paper it is proved that the Anti-Kekulé number of all fullerenes is either 3 or 4 and that for each leapfrog fullerene the Anti-Kekulé number can be established by observing finite number of cases not depending on the size of the fullerene.     

On decompositions of leapfrog fullerenes

It is shown that given a fullerene F with the number of vertices n divisible by 4, and such that no two pentagons in F share an edge, the corresponding leapfrog fullerene Le(F) contains a long cycle of length 3n − 6 missing out only one hexagon.     

Integral automorphisms of affine spaces over finite fields

A permutation of the point set of the affine space \({{\mathrm{AG}}}(n,q)\) is called an integral automorphism if it preserves the integral distance defined among the points. In this paper, we complete the classification of the integral automorphisms of \({{\mathrm{AG}}}(n,q)\) for \(n\ge 3\).