8214002
Hamilton cycles in Euler tour graph
Abstract In this paper we define the Euler tour graph of an Eulerina graph by K -transformations, which was introduced by Kotzig in 1966 ( in “Theory of Graphs” (P. Erdos and G. Katona, Eds.), Proc., Colloq., Tihany, Hungary, September, 1966, Akad. Kaido, Hungarian Academy of Sciences, Budapest, 1968 ) and prove that any edge in an Euler tour graph is in a Hamilton cycle.
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.
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.
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.
46002685
3-Restricted Edge Connectivity Of Vertex Transitive Graphs
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.
15237049
Riemannian Graph Diffusion for DT-MRI Regularization
A new method for diffusion tensor MRI (DT-MRI) regularization is presented that relies on graph diffusion. We represent a DT image using a weighted graph, where the weights of edges are functions of the geodesic distances between tensors. Diffusion across this graph 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. Tensor regularization is accomplished by computing the Riemannian weighted mean using the heat kernel as its weights. The method can efficiently remove noise, while preserving the fine details of images. Experiments on synthetic and real-world datasets illustrate the effectiveness of the method.
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.
44967148
PVM Code Generator for the Fortran Parallel Transformer
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.
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.