On Hamilton cycle decomposition of 6-regular circulant graphs

The circulant graph Sn, where S ⊆ Zn \ {0}, has vertex set Zn and edge set {{x, x + s}|x ∈ Zn, s ∈ S}. It is shown that there is a Hamilton cycle decomposition of every 6-regular circulant graph Sn in which S has an element of order n.

First-priority relation graph-based malicious users detection in mobile social networks

Mobile social networks (MSNs) consist of many mobile users (individuals) with social characteristics, that provide a variety of data delivery services involving the social relationship among mobile individuals. Because mobile users move around based on their common interests and contact with each other more frequently if they have more social features in common in MSNs. In this paper, we first propose the first-priority relation graph, say FPRG, of MSNs. However, some users in MSNs may be malicious. Malicious users can break the data delivery through terminating the data delivery or tampering with the data. Therefore, malicious users will be detected in the process of looking for the data delivery routing to obtain efficient and reliable data delivery routing along the first-priority relation graph. Secondly, we propose one hamiltonian cycle decomposition of FPRG-based adaptive detection algorithm based on in MSNs under the PMC detection model (the system-level detection model).

Generalized honeycomb torus is Hamiltonian

Generalized honeycomb torus is a candidate for interconnection network architectures, which includes honeycomb torus, honeycomb rectangular torus, and honeycomb parallelogramic torus as special cases. Existence of Hamiltonian cycle is a basic requirement for interconnection networks since it helps map a "token ring" parallel algorithm onto the associated network in an efficient way. Cho and Hsu [Inform. Process. Lett. 86 (4) (2003) 185-190] speculated that every generalized honeycomb torus is Hamiltonian. In this paper, we have proved this conjecture. (C) 2004 Elsevier B.V. All rights reserved.

Enumeration of inequivalent cycle decompositions

A k-cycle decomposition of order n is a partition of the edges of the complete graph on n vertices into k-cycles. In this report a backtracking algorithm is developed to count the number of inequivalent k-cycle decompositions of order n.

Common multiples of complete graphs and a 4-cycle

A graph G is a common multiple of two graphs H-1 and H-2 if there exists a decomposition of G into edge-disjoint copies of H-1 and also a decomposition of G into edge-disjoint copies of H-2. In this paper, we consider the case where H-1 is the 4-cycle C-4 and H-2 is the complete graph with n vertices K-n. We determine, for all positive integers n, the set of integers q for which there exists a common multiple of C-4 and K-n having precisely q edges. (C) 2003 Elsevier B.V. All rights reserved.

Some equitably 3-colourable cycle decompositions

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),..., c(k). If an m-cycle C in G has n(i) vertices coloured c(i), i = 1, 2,..., k, and (i) - n(j) less than or equal to 1 for any i, j is an element of {1, 2,..., k}, then C is equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in C is equitably k-coloured. For m = 4,5 and 6, we completely settle the existence problem for equitably 3-colourable m-cycle decompositions of complete graphs and complete graphs with the edges of a 1-factor removed. (C) 2004 Elsevier B.V. All rights reserved.

Some equitably 3-colourable cycle decompositions of complete equipartite graphs

Let G be a graph in which each vertex has been coloured using one of k colours, say c(1), c(2),.. , c(k). If an m-cycle C in G has n(i) vertices coloured c(i), i = 1, 2,..., k, and vertical bar n(i) - n(j)vertical bar <= 1 for any i, j is an element of {1, 2,..., k}, then C is said to be equitably k-coloured. An m-cycle decomposition C of a graph G is equitably k-colourable if the vertices of G can be coloured so that every m-cycle in W is equitably k-coloured. For m = 3, 4 and 5 we completely settle the existence question for equitably 3-colourable m-cycle decompositions of complete equipartite graphs. (c) 2005 Elsevier B.V. All rights reserved.

Preferential Field Coverage Through Detour-Based Mobility Coordination

Controlling the mobility pattern of mobile nodes (e.g., robots) to monitor a given field is a well-studied problem in sensor networks. In this setup, absolute control over the nodes’ mobility is assumed. Apart from the physical ones, no other constraints are imposed on planning mobility of these nodes. In this paper, we address a more general version of the problem. Specifically, we consider a setting in which mobility of each node is externally constrained by a schedule consisting of a list of locations that the node must visit at particular times. Typically, such schedules exhibit some level of slack, which could be leveraged to achieve a specific coverage distribution of a field. Such a distribution defines the relative importance of different field locations. We define the Constrained Mobility Coordination problem for Preferential Coverage (CMC-PC) as follows: given a field with a desired monitoring distribution, and a number of nodes n, each with its own schedule, we need to coordinate the mobility of the nodes in order to achieve the following two goals: 1) satisfy the schedules of all nodes, and 2) attain the required coverage of the given field. We show that the CMC-PC problem is NP-complete (by reduction to the Hamiltonian Cycle problem). Then we propose TFM, a distributed heuristic to achieve field coverage that is as close as possible to the required coverage distribution. We verify the premise of TFM using extensive simulations, as well as taxi logs from a major metropolitan area. We compare TFM to the random mobility strategy—the latter provides a lower bound on performance. Our results show that TFM is very successful in matching the required field coverage distribution, and that it provides, at least, two-fold query success ratio for queries that follow the target coverage distribution of the field.

Estimating exchange rate responsiveness to shocks

The goal of this paper is to examine the importance of permanent and transitory shocks using a more efficient trend-cycle decomposition of the real exchange rate series. Our main contribution is that in measuring the impact of shocks, we not only impose common trend restrictions but also common cycle restrictions. We later confirm, through a post sample forecasting exercise, the efficiency gains from imposing common cycle restrictions. Our results indicate that permanent shocks are responsible for the bulk of the real exchange rate variations for Japan, Italy, Germany, France, and the UK vis-à-vis the US dollar over short horizons. For Canada, however, transitory shocks are dominant over the short horizon. In sum, while for Japan, France, and Italy, around 15% of the variation in real exchange rate is due to transitory shocks, for Canada, Germany and the UK, over 25% of the variations over the short horizon are due to transitory shocks. Thus, we claim that the role of transitory shocks should not be ignored.

What drives stock markets over short horizons? Evidence from emerging markets

The goal of this paper is to examine the importance of permanent and transitory shocks in explaining variations in stock prices for Singapore, Taiwan, and South Korea using a trend-cycle decomposition technique. This study is novel in that in measuring the impact of shocks we not only impose common trend restrictions but also common cycle restrictions. We later undertake a post-sample forecasting exercise to confirm the efficiency gains from imposing common cycle restrictions. We find that over short horizons, transitory shocks are the dominant source of variations in stock prices for South Korea, while permanent shocks explain the bulk of the variations in stock price of Singapore and Taiwan.

Common trends and common cycles in stock markets

In this paper we examine the role of permanent and transitory shocks in explaining variations in the S&P 500, Dow Jones and the NASDAQ. Our modeling technique involves imposing both common trend and common cycle restrictions in extracting the variance decomposition of shocks. We find that: (1) the three stock price indices are characterized by a common trend and common cycle relationship; and (2) permanent shocks explain the bulk of the variations in stock prices over short horizons.

Estimating sectoral cycles using cointegration and common features

This paper investigates the degree of short run and long run co-movement in U.S. sectoral output data by estimating sectoraI trends and cycles. A theoretical model based on Long and Plosser (1983) is used to derive a reduced form for sectoral output from first principles. Cointegration and common features (cycles) tests are performed; sectoral output data seem to share a relatively high number of common trends and a relatively low number of common cycles. A special trend-cycle decomposition of the data set is performed and the results indicate a very similar cyclical behavior across sectors and a very different behavior for trends. Indeed. sectors cyclical components appear as one. In a variance decomposition analysis, prominent sectors such as Manufacturing and Wholesale/Retail Trade exhibit relatively important transitory shocks.

Common cycles in macroeconomic aggregates

Reduced form estimation of multivariate data sets currently takes into account long-run co-movement restrictions by using Vector Error Correction Models (VECM' s). However, short-run co-movement restrictions are completely ignored. This paper proposes a way of taking into account short-and long-run co-movement restrictions in multivariate data sets, leading to efficient estimation of VECM' s. It enables a more precise trend-cycle decomposition of the data which imposes no untested restrictions to recover these two components. The proposed methodology is applied to a multivariate data set containing U.S. per-capita output, consumption and investment Based on the results of a post-sample forecasting comparison between restricted and unrestricted VECM' s, we show that a non-trivial loss of efficiency results whenever short-run co-movement restrictions are ignored. While permanent shocks to consumption still play a very important role in explaining consumption’s variation, it seems that the improved estimates of trends and cycles of output, consumption, and investment show evidence of a more important role for transitory shocks than previously suspected. Furthermore, contrary to previous evidence, it seems that permanent shocks to output play a much more important role in explaining unemployment fluctuations.

On the welfare costs of business cycles in the 20th century

Lucas (1987) has shown a surprising result in business-cycle research, that the welfare cost of business cycles are relatively small. Using standard assumptions on preferences and a reasonable reduced form for consumption, we computed these welfare costs for the pre- and post-WWII era, using three alternative trend-cycle decomposition methods. The post-WWII period is very era this basic result is dramatically altered. For the Beveridge and Nelson decomposition, and reasonable preference parameter and discount values, we get a compensation of about 5% of consumption, which is by all means a sizable welfare cost (about US$ 1,000.00 a year).