Circuit decompositions of join‐covered graphs

In this paper, we focus our attention on join‐covered graphs, that is, ±1‐weighted graphs, without negative circuits, in which every edge lies in a zero‐weight circuit. Join covered graphs are a natural generalization of matching‐covered graphs. Many important properties of matching covered graphs, such as the existence of a canonical partition, tight cut decomposition and ear decomposition, have been generalized to join covered graphs by A. Seb? [5]. In this paper we prove that any two edges of a join‐covered graph lie on a zero‐weight circuit (under an equivalent weighting), generalize this statement to an arbitrary number of edges, and characterize minimal bipartite join‐covered graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 220–233, 2009     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.     

A note on minimal matching covered graphs

A graph is called matching covered if for its every edge there is a maximum matching containing it. It is shown that minimal matching covered graphs without isolated vertices contain a perfect matching.     

Locally regular coloured graphs

In this work we introduce the concept of locally regular coloured graph as a generalization to any dimension of the concept of regularity for maps on surfaces of W. Threlfall. We prove that locally regular coloured graphs can be obtained from the classical spherical, euclidean and hyperbollic tessellations. Finally we describe locally regular coloured graphs on spherical 3-manifolds.Partially supported by British-Spanish Join Research Program and DGICYT.     

Chordal graphs and join spaces

A join space is an abstract model for partially ordered linear, spherical and projective geometries. A characterization for chordal graphs which are join spaces is given: a chordal graph is a join space if and only if it does not contain one of the two forbidden graphs as an induced subgraph.     

The Join of Split Graphs Whose Regular Endomorphisms Form a Monoid

In this paper, the regular endomorphisms of the join of split graphs are investigated. We give a condition under which the regular endomorphisms of the join of split graphs form a monoid.     

The join of split graphs whose half-strong endomorphisms form a monoid

In this paper, the half-strong endomorphisms of the join of split graphs are investigated. We give the conditions under which the half-strong endomorphisms of the join of split graphs form a monoid.     

匹配最大根小于等于2的图的匹配等价

给出了十六个匹配等价桥,证明了两个匹配最大根小于等于2的图匹配等价当且仅当它们之间可以由这十六个匹配等价桥进行等价转换,完整地刻画了这些图的补图的匹配等价图类,找到了这些图和它们的补图中的所有匹配唯一图．     

Graphs whose endomorphism monoids are regular

In this paper, we give several approaches to construct new End-regular (-orthodox) graphs by means of the join and the lexicographic product of two graphs with certain conditions. In particular, the join of two connected bipartite graphs with a regular (orthodox) endomorphism monoid is explicitly described.     

Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks

An algebraic Bayesian network (ABN) is a probabilistic-logic graphical model of bases of knowledge patterns with uncertainty. A primary structure of an ABN is a set of knowledge patterns, that are ideals of conjunctions of positive literals except the empty conjunction endowed with scalar or interval probability estimates. A secondary ABN structure is represented by a graph constructed over the primary structure, which is called a join graph. From the point of view of learning of a global ABN structure, of interest are join graphs with the minimum number of edges and irreducible join graphs. A theorem on the coincidence of the sets of minimal and irreducible join graphs over the same primary structure is proved. A greedy algorithm constructing an arbitrary minimal join graph from a given primary structure is described. A theorem expressing the number of edges in a minimal join graph as the sum of the ranks of the incidence matrices of strong restrictions of a maximal join graph minus the number of significant weights is stated and proved. A generalized graph of maximal knowledge patterns (GGMKP) is a graph with the same vertex set as the join graph which is not subject to any constraints concerning the possibility of joining two vertices by an edge. It is proved that the pair consisting of the edge set of a maximal GGMKP and the set of all subsets of this graph such that the subtraction of any such subset from the maximal GGMKP yields an edge of the join graph on the same vertex set is a matroid.     

Matchings on infinite graphs

Elek and Lippner (Proc. Am. Math. Soc. 138(8), 2939–2947, 2010) showed that the convergence of a sequence of bounded-degree graphs implies the existence of a limit for the proportion of vertices covered by a maximum matching. We provide a characterization of the limiting parameter via a local recursion defined directly on the limit of the graph sequence. Interestingly, the recursion may admit multiple solutions, implying non-trivial long-range dependencies between the covered vertices. We overcome this lack of correlation decay by introducing a perturbative parameter (temperature), which we let progressively go to zero. This allows us to uniquely identify the correct solution. In the important case where the graph limit is a unimodular Galton–Watson tree, the recursion simplifies into a distributional equation that can be solved explicitly, leading to a new asymptotic formula that considerably extends the well-known one by Karp and Sipser for Erd?s-Rényi random graphs.     

On the join of graphs and chromatic uniqueness

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let K_m denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of K_m + G where + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex-transitive graphs. © 1995 John Wiley & Sons, Inc.     

Topology of matching,chessboard, and general bounded degree graph complexes

We survey results and techniques in the topological study of simplicial complexes of (di-, multi-, hyper-)graphs whose node degrees are bounded from above. These complexes have arisen in a variety of contexts in the literature. The most well-known examples are the matching complex and the chessboard complex. The topics covered here include computation of Betti numbers, representations of the symmetric group on rational homology, torsion in integral homology, homotopy properties, and connections with other fields.In memory of Gian-Carlo Rota     

广义联图的正则性

讨论了两个图的广义联图的End-正则性,给出了当图X、Y的广义联图G（y1,…ym）End-正则时,图X也End-正则应满足的条件。     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

Higher-order matching polynomials and d-orthogonality

We show combinatorially that the higher-order matching polynomials of several families of graphs are d-orthogonal polynomials. The matching polynomial of a graph is a generating function for coverings of a graph by disjoint edges; the higher-order matching polynomial corresponds to coverings by paths. Several families of classical orthogonal polynomials—the Chebyshev, Hermite, and Laguerre polynomials—can be interpreted as matching polynomials of paths, cycles, complete graphs, and complete bipartite graphs. The notion of d-orthogonality is a generalization of the usual idea of orthogonality for polynomials and we use sign-reversing involutions to show that the higher-order Chebyshev (first and second kinds), Hermite, and Laguerre polynomials are d-orthogonal. We also investigate the moments and find generating functions of those polynomials.     

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.