Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
It is known that finding a perfect matching in a general graph is AC0-equivalent to finding a perfect matching in a 3-regular (i.e. cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence and construction...
Perfect matching preservers.
Perfect matchings and -decomposability of increasing trees.
Perfect matchings for the three-term Gale-Robinson sequences.
Perfect Matchings in a Class of Bipartite Graphs
Perfect matchings in claw-free cubic graphs.
Perfect matchings in -regular graphs.
Perfect Set of Euler Tours of Kp,p,p
Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.
Perfect transversal in some graph products.
Perfectly balanced partitions of smoothed graphs.
Perfectly matchable subgraph problem on a bipartite graph
We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph G=(UV,E) with respect to given nonnegative weights of its edges. We show that G has a perfect matching if and only if some vector indexed by the nodes in UV is a base of an extended polymatroid associated with a submodular function defined on the subsets of UV. The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on G. In this paper, we give...
Periodic graphs.
Permanents of Hessenberg (0,1)-matrices.
Permanents, Pfaffian orientations, and even directed circuits.
Permutation separations and complete bipartite factorisations of .
Permutations planaires généralisées
Persistency in the Traveling Salesman Problem on Halin graphs
For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition , , of the edge set E, where: = e ∈ E, e belongs to all optimum solutions, = e ∈ E, e does not belong to any optimum solution and = e ∈ E, e belongs to some but not to all optimum solutions.
Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs.
Pinning lag synchronization between two dynamical networks with non-derivative and derivative couplings
In this paper, we study lag synchronization between two dynamical networks with non-derivative and derivative couplings via pinning control. We design two types of pinning control schemes, including linear and adaptive feedback controllers. With the corresponding control algorithms, we obtain two theorems on the lag synchronization based on Schur complement and Barbalat's lemma. In addition, we obtain the domain for the linear feedback gains. Finally, we provide two numerical examples to show the...