Generalized recursive circulant graphs (GRCGs for short) are a generalization of recursive circulant graphs and provide a new type of topology for interconnection networks. A graph of n vertices is said to be s-pancyclic for some $3leqslant sleqslant n$ if it contains cycles of every length t for $sleqslant tleqslant n$. The pancyclicity of recursive circulant graphs was investigated by Araki and Shibata (Inf. Process. Lett. vol.81, no.4, pp.187-190, 2002). In this paper, we are concerned with the s-pancyclicity of GRCGs.

A vertex subset F ⊆ V(G) is called a cyclic vertex-cut set of a connected graph G if G-F is disconnected such that at least two components in G-F contain cycles. The cyclic vertex connectivity is the cardinality of a minimum cyclic vertex-cut set. In this paper, we show that the cyclic vertex connectivity of the trivalent Cayley graphs TGn is equal to eight for n ≥ 4.

We have investigated the influence of the ferromagnet magnetization on the transport properties of intrinsic Josephson junctions in Co/Au/BSCCO/Au/Co hybrid structure under applied magnetic fields. The current-voltage characteristic at 77K in a zero-field showed the multiple quasiparticle branches with hysteresis similar to that of conventional intrinsic Josephson junctions. On the other hand, it was observed that the critical current shows a clear asymmetric field dependence with respect to the direction of the field sweep, resulting in hysteretic behavior. By comparing the field dependence of critical current with magnetization curve of the sample, we found that the critical current is strongly suppressed in the antiparallel configuration of the relative magnetization orientation of two Co layers due to the accumulation of spin-polarized quasiparticles in intrinsic Josephson junctions. The observed suppression of the critical current is as large as more than 20%.

The physics and applications of superconducting phase shifts and their control in superconducting systems are reviewed herein. The operation principle of almost all superconducting devices is related to the superconducting phase, and an efficient control of the phase is crucial for improving the performance and scalability. Furthermore, employing new methods to shift or control the phase may lead to the development of novel superconducting device applications, such as cryogenic memory and quantum computing devices. Recently, as a result of the progress in nanofabrication techniques, superconducting phase shifts utilizing π states have been realized. In this review, following a discussion of the basic physics of phase propagation and shifts in hybrid superconducting structures, interesting phenomena and device applications in phase-shifted superconducting systems are presented. In addition, various possibilities for developing electrically and magnetically controllable 0 and π junctions are presented; these possibilities are expected to be useful for future devices.

We present a concept of an advanced rapid single-flux-quantum (RSFQ) logic circuit family using the combination of 0-shifted and π-shifted Josephson junctions. A π-shift in the current-phase relationship can be obtained in several types of Josephson junctions, such as Josephson junctions containing a ferromagnet barrier layer, depending on its thickness and temperature. We use a superconducting quantum interference devices composed of a pair of 0- and π-shifted Josephson junctions (0-π SQUIDs) as a basic circuit element. Unlike the conventional RSFQ logic, bistability is obtained by spontaneous circular currents without using a large superconductor loop, and the state can be flipped by smaller driving currents. These features lead to energy- and/or space-efficient logic gates. In this paper, we show several example circuits where we represent signals by flips of the states of a 0-π SQUID. We obtained successful operation of the circuits from numerical simulation.

CMOS microprocessors are limited in their capacity for clock speed improvement because of increasing computing power, i.e., they face a power-wall problem. Single-flux-quantum (SFQ) circuits offer a solution with their ultra-fast-speed and ultra-low-power natures. This paper introduces our contributions towards ultra-high-speed cryogenic SFQ computing. The first step is to design SFQ microprocessors. From qualitatively and quantitatively evaluating past-designed SFQ microprocessors, we have found that revisiting the architecture of SFQ microprocessors and on-chip caches is the first critical challenge. On the basis of cross-layer discussions and analysis, we came to the conclusion that a bit-parallel gate-level pipeline architecture is the best solution for SFQ designs. This paper summarizes our current research results targeting SFQ microprocessors and on-chip cache architectures.

The k-edge-connectivity augmentation problem with multipartition constraints (kECAMP, for short) is defined by “Given a multigraph G=(V,E) and a multipartition π={V1,...,Vr} (r≥2) of V, that is, $V = igcup_{h = 1}^r V_h$ and Vi∩Vj=∅ (1≤i

A widely-used query on a graph is a regular path query (RPQ) whose answer is a set of tuples of nodes connected by paths corresponding to a given regular expression. Traditionally, evaluating an RPQ on a large graph takes substantial memory spaces and long response time. Recently, several studies have focused on improving response time for evaluating an RPQ by splitting an original RPQ into smaller subqueries, evaluating them in parallel and combining partial answers. In these works, how to choose split labels in an RPQ is one of key points of the performance of RPQ evaluation, and rare labels of a graph can be used as split labels. However there is still a room for improvement, because a rare label cannot guarantee the minimum evaluation cost all the time. In this paper, we propose a novel approach of selecting split labels by estimating evaluation cost of each split subquery with a unit-subquery cost matrix (USCM), which can be obtained from a graph in prior to evaluate an RPQ. USCM presents the evaluation cost of a unit-subquery which is the smallest possible subquery, and we can estimate the evaluation cost of an RPQ by decomposing into a set of unit-subqueries. Experimental results show that our proposed approach outperforms rare label based approaches.

Cayley hash functions are a family of cryptographic hash functions constructed from Cayley graphs, with appealing properties such as a natural parallelism and a security reduction to a clean, well-defined mathematical problem. As this problem involves non-Abelian groups, it is a priori resistant to quantum period finding algorithms and Cayley hash functions may therefore be a good foundation for post-quantum cryptography. Four particular parameter sets for Cayley hash functions have been proposed in the past, and so far dedicated preimage algorithms have been found for all of them. These algorithms do however not seem to extend to generic parameters, and as a result it is still an open problem to determine the security of Cayley hash functions in general. In this paper, we study the case of Chiu's Ramanujan graphs. We design a polynomial time preimage attack against the resulting Cayley hash function, showing that these particular parameters like the previous ones are not suitable for the construction. We extend our attacks on hash functions based on similar Cayley graphs as Chiu's Ramanujan graphs. On the positive side, we then suggest some possible ways to construct the Cayley hashes that may not be affected by this type of attacks. Our results contribute to a better understanding of the hard problems underlying the security of Cayley hash functions.

Let G be a graph and K be a set of target vertices of G. Assume that all vertices of G, except the vertices in K, may fail with given probabilities. The K-terminal reliability of G is the probability that all vertices in K are mutually connected. This reliability problem is known to be #P-complete for general graphs. This work develops the first polynomial-time algorithm for computing the K-terminal reliability of circular-arc graphs.

We have developed software that uses the R statistics software environment to automatically generate tactile graphs — i.e. graphs that can be read by blind people using their sense of touch. We released this software as a Web application to make it available to anyone, from anywhere. This Web application can automatically generate images for tactile graphs from numerical data in a CSV file. It is currently able to generate four types of graph — scatter plots, line graphs, bar charts and pie charts. This paper describes the Web application's functions, operating procedures and the results of evaluation experiments.

We have studied ultra-low-power superconductor circuits using adiabatic quantum flux parametron (AQFP) logic. Latches, which store logic data in logic circuits, are indispensable logic elements in the realization of AQFP computing systems. Among them, feedback latches, which hold data by using a feedback loop, have advantages in terms of their wide operation margins and high stability. Their drawbacks are their large junction counts and long latency. In this paper, we propose a majority gate-based feedback latch for AQFP logic with a reduced number of junctions. We designed and fabricated the proposed AQFP latches using a standard National Institute of Advanced Industrial Science and Technology (AIST) process. The measurement results showed that the feedback latches operate with wide operation margins that are comparable with circuit simulation results.

This letter deals with direction-of-arrival (DOA) estimate problem based on gravitational search algorithm (GSA) with multiple signal classification (MUSIC) criterion for code-division multiple access (CDMA) signals. It has been shown that the estimate accuracy of the searching-based MUSIC estimator strictly depends on the number of search grids used during the search process, which is time consuming and the required number of search grids is not clear to determine. In conjunction with the GSA-based optimization, the high resolution DOA estimation can be obtained; meanwhile the searching grid size is no need to know previously. In this letter, we firstly present a GSA-based DOA estimator with MUSIC criterion under high interferer-to-noise ratio circumstances. Second, for the purpose to increase the estimation accuracy, we also propose an improved GSA with adaptive multiple accelerations, which depend on Newton-Raphson method. Several computer simulations are provided for illustration and comparison.

A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n3) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.

The complexity of the graph isomorphism problem for trapezoid graphs has been open over a decade. This paper shows that the problem is GI-complete. More precisely, we show that the graph isomorphism problem is GI-complete for comparability graphs of partially ordered sets with interval dimension 2 and height 3. In contrast, the problem is known to be solvable in polynomial time for comparability graphs of partially ordered sets with interval dimension at most 2 and height at most 2.

Irreversible k-conversion set is introduced in connection with the mathematical modeling of the spread of diseases or opinions. We show that the problem to find a minimum irreversible 2-conversion set can be solved in O(n2log 6n) time for graphs with maximum degree at most 3 (subcubic graphs) by reducing it to the graphic matroid parity problem, where n is the number of vertices in a graph. This affirmatively settles an open question posed by Kyncl et al. (2014).

Graphical User Interfaces (GUIs) are critical for the security, safety and reliability of software systems. Injection attacks, for instance via SQL, succeed due to insufficient input validation and can be avoided if contract-based approaches, such as Design by Contract, are followed in the software development lifecycle of GUIs. This paper proposes a model-based testing approach for detecting GUI data contract violations, which may result in serious failures such as system crash. A contract-based model of GUI data specifications is used to develop test scenarios and to serve as test oracle. The technique introduced uses multi terminal binary decision diagrams, which are designed as an integral part of decision table-augmented event sequence graphs, to implement a GUI testing process. A case study, which validates the presented approach on a port scanner written in Java programming language, is presented.

A hinge vertex is a vertex in an undirected graph such that there exist two vertices whose removal makes the distance between them longer than before. Identifying hinge vertices in a graph can help detect critical nodes in communication network systems, which is useful for making them more stable. For finding them, an O(n3) time algorithm was developed for a simple graph, and, linear time algorithms were developed for interval and permutation graphs, respectively. Recently, the maximum detour hinge vertex problem is defined by Honma et al. For a hinge vertex u in a graph, the detour degree of u is the largest value of distance between any pair of x and y (x and y are adjacent to u) by removing u. A hinge vertex with the largest detour degree in G is defined as the maximum detour hinge vertex of G. This problem is motivated by practical applications, such as network stabilization with a limited cost, i.e., by enhancing the reliability of the maximum detour hinge vertex, the stability of the network is much improved. We previously developed an O(n2) time algorithm for solving this problem on an interval graph. In this study, we propose an algorithm that identifies the maximum detour hinge vertex on a permutation graph in O(n2) time, where n is the number of vertices in the graph.

Suppose one of the edges is attacked in a graph G, where some number of guards are placed on some of its vertices. If a guard is placed on one of the end-vertices of the attacked edge, she can defend such an attack to protect G by passing over the edge. For each of such attacks, every guard is allowed either to move to a neighboring vertex, or to stay at where she is. The eternal vertex cover number τ∞(G) is the minimum number of guards sufficient to protect G from any length of any sequence of edge attacks. This paper derives the eternal vertex cover number τ∞(G) of such graphs constructed by replacing each edge of a tree by an arbitrary elementary bipartite graph (or by an arbitrary clique), in terms of easily computable graph invariants only, thereby showing that τ∞(G) can be computed in polynomial time for such graphs G.

For k ≥ 3, a convex geometric graph is called k-locally outerplanar if no path of length k intersects itself. In [D. Boutin, Convex Geometric Graphs with No Short Self-intersecting Path, Congressus Numerantium 160 (2003) 205-214], Boutin stated the results of the degeneracy for 3-locally outerplanar graphs. Later, in [D. Boutin, Structure and Properties of Locally Outerplanar Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 60 (2007) 169-180], a structural property on k-locally outerplanar graphs was proposed. These results are based on the existence of “minimal corner pairs”. In this paper, we show that a “minimal corner pair” may not exist and give a counterexample to disprove the structural property. Furthermore, we generalize the result on the degeneracy with respect to k-locally outerplanar graphs.