16653289
Reducible chains of planar 1-cycle resonant graphs
A connected graph G is said to be k-cycle resonant if, for 1≤t≤k, any t disjoint cycles in G are mutually resonant, that is, there is a perfect matching M of G such that each of the t cycles is an M-alternating cycle. The concept of k-cycle resonant graphs was introduced by the present authors in 1994. Some necessary and sufficient conditions for a graph to be k-cycle resonant were given. Recently, some necessary and sufficient conditions for a planar graph to be 1-cycle resonant and 2-cycle resonant were also given. In this paper, we investigate 1-cycle-resonant reducible (simply 1-CR-reducible) chains of planar 1-cycle resonant graphs. The upper and lower bounds of the numbers of 1-CR-reducible chains of planar 1-cycle resonant graphs are given. Consequently, it is shown that any planar 1-cycle resonant graph has an ear decomposition. Furthermore, a construction method of planar 1-cycle resonant graphs and an efficient algorithm for recognizing 1-cycle resonant graphs are established.
46002685
3-Restricted Edge Connectivity Of Vertex Transitive Graphs
205056734
Hamiltonicity of a Type of Interchange Graphs
Abstract Let R(r1,…, rm) and S(s1,…, sn) be two nonnegative integral vectors, and let U (R,S) denote the class of all m×n matrices of 0's and 1's having row sum vector R and column sum vector S. We prove that if s1s2⋯sn1, the interchange graph G(R,S) of U (R,S) is hamiltonian.
23589102
Bounds of the longest directed cycle length for minimal strong digraphs
Abstract In this paper we present the upper and lower bounds of the longest directed cycle length for minimal strong digraphs in terms of the numbers of vertices and arcs. These bounds are both sharp. In addition, we give analogous results for minimal 2-edge connected graphs.
5788058
Heredity of the index of convergence of the line digraph
Let D be a digraph, and let Ln(D) and k(D) denote the nth iterated line digraph of D and the index of convergence of D, respectively. We prove that if D contains neither sources nor sinks, then: (1) k(Ln(D))=k(D)=0 if every connected component of D is a directed cycle. (2) k(Ln(D))=k(D)+n if there exists at least one connected component of D that is not a directed cycle. Finally, we prove that if D has no sources or no sinks then k(D) ≤ k(L(D)) ≤ k(D)+1.
32475390
k-Cycle resonant graphs
Abstract A connected graph G is said to be k -cycle resonant if, for 1 ⩽ t ⩽ k , any t disjoint cycles in G are mutually resonant, that is, there is a perfect matching M of G such that each of the t cycles is an M -alternating cycle. In this paper, we at the first time introduce the concept of k -cycle resonant graphs, and investigate some properties of k -cycle resonant graphs. Some simple necessary and sufficient conditions for a graph to be k -cycle resonant are given. The construction of k -cycle resonant hexagonal systems are also characterized.
9458829
Face Tracing Based Geographic Routing in Nonplanar Wireless Networks
Scalable and efficient routing is a main challenge in the deployment of large ad hoc wireless networks. An essential element of practical routing protocols is their accommodation of realistic network topologies. In this paper, we study geographic routing in general large wireless networks. Geographic routing is a celebrated idea that uses the locations of nodes to effectively support routing. However, to guarantee delivery, recent geographic routing algorithms usually resort to perimeter routing, which requires the removal of communication links to get a planar sub-network on which perimeter routing is performed. Localized network planarization requires the wireless network to be a unit-disk graph (UDG) or its close approximation. For networks that significantly deviate from the UDG model, a common case in practice, substantially more expensive and non-localized network planarization methods have to be used. How to make such methods efficiently adaptable to network dynamics, and how to avoid the removal of an excessive number of links that leads to lowered routing performance, are still open problems. To enable efficient geographic routing in general wireless networks, we present face-tracing based routing, a novel approach that routes the message in the faces of the network that are virtually embedded in a topological surface. Such faces are easily recognizable and constructible, and adaptively capture the important geometric features in wireless networks - in particular, holes, -thus leading to very efficient routing. We show by both analysis and si mulations that the face-tracing based routing is a highly scalable routing protocol that generates short routes, incurs low overhead, adapts quickly to network dynamics, and is very robust to variations in network models.
15887745
The Rotation Graphs of Perfect Matchings of Plane Bipartite Graphs
Abstract In the present paper, the minimal proper alternating cycle (MPAC) rotation graph R(G) of perfect matchings of a plane bipartite graph G is defined. We show that an MPAC rotation graph R(G) of G is a directed rooted tree, and thus extend such a result for generalized polyhex graphs to arbitrary plane bipartite graphs. As an immediate result, we describe a one-to-one correspondence between MPAC systems and perfect matchings in G.
9404547
Blocking-aware processor voltage scheduling for real-time tasks
As mobile computing is getting popular, there is a growing need for techniques that minimize energy consumption on battery-powered mobile devices. Processor voltage scheduling can effectively reduce processor energy consumption by lowering the processor speed. In this paper, we study voltage scheduling for real-time periodic tasks with non-preemptible sections. Three schemes are proposed: The static speed algorithm derives the minimum static feasible speed based on the stack resource policy. Due to blocking, this static speed is usually higher than the speed required for scheduling fully preemptible tasks (called the utilization speed). Two dynamic speed algorithms are then introduced to further reduce energy consumption. The novel dual speed algorithm operates the processor at the utilization speed whenever possible and switches to the higher static speed only when blocking occurs. The dual speed dynamic reclaiming algorithm reserves time budget for each job, reclaims the unused time budget from completed jobs and redistributes it to subsequent jobs so they can run at a lower speed whenever possible. Feasibility conditions for real-time task sets have been derived and proved mathematically. Simulation results show that the proposed voltage scheduling algorithms dramatically reduce processor energy consumption over non-power-aware scheduling algorithms. Furthermore, the two dynamic speed algorithms consistently outperform the static speed scheme in a wide range of system and workload conditions.
33313231
Image Scale-Space from the Heat Kernel
In this paper, we show how the heat-kernel can be used to construct a scale-space for image smoothing and edge detection. We commence from an affinity weight matrix computed by exponentiating the difference in pixel grey-scale and distance. From the weight matrix, we compute the graph Laplacian. Information flow across this weighted graph-structure with time is captured by the heat-equation, and the solution, i.e. the heat kernel, is found by exponentiating the Laplacian eigen-system with time. Our scale-space is constructed by varying the time parameter of the heat-kernel. The larger the time the greater the the amount of information flow across the graph. The method has the effect of smoothing within regions, but does not blur region boundaries. Moreover, the boundaries do not move with time and this overcomes one of the problems with Gaussian scale-space. We illustrate the effectiveness of the method for image smoothing and edge detection.
29766053
Construction for bicritical graphs and k-extendable bipartite graphs
A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.