Search

Counting perfect matchings is an interesting and challenging combinatorial task. It has important applications in statistical physics and chemistry. As the general problem is #P-complete, it is usually tackled by randomized heuristics and approximation schemes. Let GG and HH be two graphs. Denote by G×HG\times H the Cartesian product of graphs GG and HH. The number of perfect matchings of some types of Cartesian product G×HG\times H is investigated by the Pfaffian method, where G≅P2G\cong {P}_{2}, P3{P}_{3}, P4{P}_{4} or C4{C}_{4}, and H≅TH\cong T or HH is a non-bipartite graph with a unique cycle. In this article, we construct a Pfaffian orientation of the graph G×P2G\times {P}_{2}, where GG is a non-bipartite graph with kk odd cycles. We obtain the counting formula on the number of perfect matchings of G×P2G\times {P}_{2}.

Graph polynomials is one of the important research directions in mathematical chemistry. The coefficients of some graph polynomials, such as matching polynomial and permanental polynomial, are related to structural properties of graphs. The Hosoya index of a graph is the sum of the absolute value of all coefficients for the matching polynomial. And the permanental sum of a graph is the sum of the absolute value of all coefficients of the permanental polynomial. In this paper, we characterize the second to sixth minimal Hosoya indices of all bicyclic graphs. Furthermore, using the results, the second to sixth minimal permanental sums of all bicyclic graphs are also characterized. [ABSTRACT FROM AUTHOR]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we first introduce a weighted derivation on algebras over an operad 풫, and prove that for the free 풫-algebra, its weighted derivation is determined by the restriction on the generators. As applications, we propose the concept of weighted differential (q-tri)dendriform algebras and study some basic properties of them. Then Novikov-(tri)dendriform algebras are initiated, which can be induced from differential (q-tri)dendriform of weight zero. Finally, the corresponding free objects are constructed, in both the commutative and noncommutative contexts. [ABSTRACT FROM AUTHOR]