204989114
On the numbers of spanning trees and Eulerian tours in generalized de Bruijn graphs
Abstract In this paper, we give the spectra and characteristic polynomials of generalized de Bruijn graphs. By Tutte's Theorem we can obtain the number of spanning trees and the number of Eulerian tours in such graphs.
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.
6664703
The number of spanning trees of plane graphs with reflective symmetry
A plane graph is called symmetric if it is invariant under the reflection across some straight line (called symmetry axis). Let G be a symmetric plane graph. We prove that if there is no edge in G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product the number of spanning trees of two smaller graphs. each of which has about half the number of vertices of G.
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.
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.
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.
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.
45226722
Enhancing Parallelism by Removing Cyclic Data Dependencies
The parallel execution of loop iterations often is inhibited by recurrence relations on scalar variables. Examples are the use of induction variables and recursive functions. Due to the cyclic dependence between the iterations, these loops have to be executed sequentially. A method is presented to convert a family of coupled linear recurrence relations into explicit functions of a loop index. When the cyclic dependency is the only factor preventing a parallel execution, the conversion effectively removes the dependency and allows the loop to be executed in parallel. The technique is based on constructing and solving a set of coupled linear difference equations at compile-time. The method is general for an arbitrary number of coupled scalar variables and can be implemented by a straight-forward algorithm. Results show that the parallelism of several sequential EISPACK do-loops is significantly enhanced by the converting them into do-all loops.
41201857
A Note on the Number of Perfect Matchings of Bipartite Graphs
Abstract Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s + 2, s ϵ {1, 2, …}, an elegant formula, i.e. det A = (−1)nK2, had been rigorously proved by Cvetkovic et al. (1982). For general bipartite graphs, this note contains a necessary and sufficient condition for the above relation to hold. A fast algorithm to check if a plane bipartite graph has such a relation is given.
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.
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.