Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc...Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.展开更多
In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the ab...In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.展开更多
We introduce the notion of a graph derangement, which naturally interpolates between perfect matchings and Hamiltonian cycles. We give a necessary and sufficient condition for the existence of graph derangements on a ...We introduce the notion of a graph derangement, which naturally interpolates between perfect matchings and Hamiltonian cycles. We give a necessary and sufficient condition for the existence of graph derangements on a locally finite graph. This result was first proved by W. T. Tutte in 1953 by applying some deeper results on digraphs. We give a new, simple proof which amounts to a reduction to the (Menger-Egerváry-K?nig-)Hall(-Hall) Theorem on transversals of set systems. We also consider the problem of classifying all cycle types of graph derangements on m × n checkerboard graphs. Our presentation does not assume any prior knowledge in graph theory or combinatorics: all definitions and proofs of needed theorems are given.展开更多
In this study, we consider the problem of triangulated graphs. Precisely we give a necessary and sufficient condition for a graph to be triangulated. This gives an alternative characterization of triangulated graphs. ...In this study, we consider the problem of triangulated graphs. Precisely we give a necessary and sufficient condition for a graph to be triangulated. This gives an alternative characterization of triangulated graphs. Our method is based on the so-called perfectly nested sequences.展开更多
文摘Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.
文摘In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.
文摘We introduce the notion of a graph derangement, which naturally interpolates between perfect matchings and Hamiltonian cycles. We give a necessary and sufficient condition for the existence of graph derangements on a locally finite graph. This result was first proved by W. T. Tutte in 1953 by applying some deeper results on digraphs. We give a new, simple proof which amounts to a reduction to the (Menger-Egerváry-K?nig-)Hall(-Hall) Theorem on transversals of set systems. We also consider the problem of classifying all cycle types of graph derangements on m × n checkerboard graphs. Our presentation does not assume any prior knowledge in graph theory or combinatorics: all definitions and proofs of needed theorems are given.
文摘In this study, we consider the problem of triangulated graphs. Precisely we give a necessary and sufficient condition for a graph to be triangulated. This gives an alternative characterization of triangulated graphs. Our method is based on the so-called perfectly nested sequences.
