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.
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.
40411122
Super Restricted Edge Connectivity of Regular Graphs
An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these 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.
46002685
3-Restricted Edge Connectivity Of Vertex Transitive Graphs
45771940
Smoothing Tensor-Valued Images Using Anisotropic Geodesic Diffusion
This paper considers the feature space of DT-MRI as a differential manifold with an affine-invariant metric. We generalise Di Zenzo’s structure tensor to tensor-valued images for edge detection. To improve the quality of the edges, we develop a generalised Perona-Malik method for smoothing tensor images. We demonstrate our algorithm on both synthetic and real DT-MRI data.
46427487
The Clar Covering Polynomial of Hexagonal Systems I
Abstract In this paper the Clar covering polynomial of a hexagonal system is introduced. In fact it is a kind of F polynomial [4] of a graph, and can be calculated by recurrence relations. We show that the number of aromatic sextets (in a Clar formula), the number of Clar formulas, the number of Kekule structures and the first Herndon number for any Kekulean hexagonal system can be easily obtained by its Clar covering polynomial. In addition, we give some theorems to calculate the Clar covering polynomial of a hexagonal system. As examples we finally derive the explicit expressions of the Clar covering polynomials for some small hexagonal systems and several types of catacondensed hexagonal systems. A relation between the resonance energy and the Clar covering polynomial of a hexagonal system is considered in the next paper.
6097933
The Clar covering polynomial of hexagonal systems III
Abstract The Clar covering polynomial is a recently proposed concept of hexagonal systems by which some important topological indices such as perfect matching count, Clar number, first Herndon number, etc., can be easily obtained. In this paper we establish a relationship between the Clar covering polynomial and sextet polynomial. A lower bound of the Clar number and some properties of coefficients of the Clar covering polynomial are thus deduced. It is mentioned that the summation of coefficients of Clar covering polynomial can be used to calculate the number of perfect matchings of a certain kind of polyominoes relating to crystal physics.
44874837
Z-transformation graphs of perfect matchings of plane bipartite graphs
Abstract Let G be a plane bipartite graph with at least two perfect matchings. The Z -transformation graph, Z F ( G ), of G with respect to a specific set F of faces is defined as a graph on the perfect matchings of G such that two perfect matchings M 1 and M 2 are adjacent provided M 1 and M 2 differ only in a cycle that is the boundary of a face in F . If F is the set of all interior faces, Z F ( G ) is the usual Z -transformation graph; If F contains all faces of G it is a novel graph and called the total Z -transformation graph. In this paper, we give some simple characterizations for the Z -transformation graphs to be connected by applying the above new idea. Furthermore, we show that the total Z -transformation graph of G is 2-connected if G is elementary; the total Z -transformation digraph of G is strongly connected if and only if G is elementary.
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.