29378412
Vertex-primitive digraphs of prime-power order are hamiltonian
Abstract Witte [6] proved that every connected Cayley digraph of a p -group is hamiltonian. In this note we generalize Witte's result to connected vertex-primitive digraphs of prime-power order; namely, we prove that every connected vertex-primitive digraph of prime-power order is hamiltonian.
43124802
On the Isomorphisms of Cayley Graphs of Abelian Groups
Let G be a finite group, S a subset of G\{1}, and let Cay (G, S) denote the Cayley digraph of G with respect to S. If, for any subset T of G\{1}, Cay(G, S) ≅ Cay(G, T) implies that Sα = T for some α ∈ Aut(G), then S is called a CI-subset. The group G is called a CIM-group if for any minimal generating subset S of G, S ∪ S-1 is a CI-subset. In this paper, CIM-abelian groups are characterized.
206570343
Vertex-Primitive Graphs of Order a Product of Two Distinct Primes
Abstract Let k and p be odd primes with k p . All vertex-primitive graphs of order kp are classified, and those which are symmetric, or are edge-transitive but not symmetric. or are not Cayley graphs are identified. In addition, a classification is given of all vertex-primitive, edge-transitive lantisymmetric) directed graphs or order kp . The classification of the vertex-primitive symmetric graphs of order kp is used by the authors and others to complete the classification of symmetric graphs or order kp . The classification of the vertex-primitive non-Cayley graphs of order kp is used by B.D. McKay and the first author in an investigation of vertex-transitive non-Cayley graphs.
1185541
A serializability violation detector for shared-memory server programs
We aim to improve reliability of multithreaded programs by proposing a dynamic detector that detects potentially erroneous program executions and their causes. We design and evaluate a Serializability Violation Detector (SVD) that has two unique goals: (I) triggering automatic recovery from erroneous executions using backward error recovery (BER), or simply alerting users that a software error may have occurred; and (II) helping debug programs by revealing causes of error symptoms.Two properties of SVD help in achieving these goals. First, to detect only erroneous executions, SVD checks serializability of atomic regions, which are code regions that need to be executed atomically. Second, to improve usability, SVD does not require a priori annotations of atomic regions; instead, SVD approximates them using a heuristic. Experimental results on three widely-used multithreaded server programs show that SVD finds real bugs and reports modest false positives. The goal of this paper is to develop a detector suitable for (I) BER-based avoidance of erroneous program executions; and (II) alerting users as software errors occur. We argue that such a detector should have the following two properties.
872168
The super connectivity of shuffle-cubes
The shuffle-cube SQn, where n ≡ 2 (mod 4), a new variation of hypercubes proposed by Li et al. [T.-K. Li, J.J.M. Tan, L.-H. Hsu, T.-Y. Sung, The shuffle-cubes and their generalization, Inform. Process. Lett. 77 (2001) 35-41], is an n-regular n-connected graph. This paper determines that the super connectivity of SQn is 2n - 4 and the super edge-connectivity is 2n - 2 for n ≥ 6.
11401451
A regulated transitive reduction (RTR) for longer memory race recording
Now at VMware. Multithreaded deterministic replay has important applications in cyclic debugging, fault tolerance and intrusion analysis. Memory race recording is a key technology for multithreaded deterministic replay. In this paper, we considerably improve our previous always-on Flight Data Recorder (FDR) in four ways: •Longer recording by reducing the log size growth rate to approximately one byte per thousand dynamic instructions. •Lower hardware cost by reducing the cost to 24 KB per processor core. •Simpler design by modifying only the cache coherence protocol, but not the cache. •Broader applicability by supporting both Sequential Consistency (SC) and Total Store Order (TSO) memory consistency models (existing recorders support only SC).These improvements stem from several ideas: (1) a Regulated Transitive Reduction (RTR) recording algorithm that creates stricter and vectorizable dependencies to reduce the log growth rate; (2) a Set/LRU timestamp approximation method that better approximates timestamps of uncached memory locations to reduce the hardware cost; (3) an order-value-hybrid recording methodthat explicitly logs the value of potential SC-violating load instructions to support multiprocessor systems with TSO.
15417765
The proof of a conjecture of Bouabdallah and Sotteau
Let G be a connected graph of order n. A routing in G is a set of n(n 1) fixed paths for all ordered pairs of vertices of G. The edge-forwarding index of G, (G), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G, and ,n is the minimum of (G) taken over all graphs of order n with maximum degree at most . To determine n 2p 1,n for 4p 2p/3 1 ≤ n ≤ 6p, A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249–255]. The set 3 {1, 2, . . . , (4p)/3} can be partitioned into 2p pairs plus singletons such that the set of differences of the pairs is the set 2 {1, 2, . . . , p}. This article gives a proof of this conjecture and determines that n 2p 1,n is equal to 5 if 4p 2p/3 1 ≤ n ≤ 6p and to 8 if 3p p/3 1 ≤ n ≤ 3p (3p)/5 for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004
7849638
Edge-fault-tolerant edge-bipancyclicity of hypercubes
In this paper, we consider the problem embedding a cycle into the hypercube Q"n with existence of faulty edges and show that for any edge subset F of Q"n with |F|==4 and all edges in F are not incident with the same vertex. This result improves some known results.