Whiskers and sequentially Cohen-Macaulay graphs

We investigate how to modify a simple graph G combinatorially to obtain a sequentially Cohen-Macaulay graph. We focus on adding configurations of whiskers to G, where to add a whisker one adds a new vertex and an edge connecting this vertex to an existing vertex of G. We give various sufficient conditions and necessary conditions on a subset S of the vertices of G so that the graph G∪W(S), obtained from G by adding a whisker to each vertex in S, is a sequentially Cohen-Macaulay graph. For instance, we show that if S is a vertex cover of G, then G∪W(S) is a sequentially Cohen-Macaulay graph. On the other hand, we show that if G?S is not sequentially Cohen-Macaulay, then G∪W(S) is not a sequentially Cohen-Macaulay graph. Our work is inspired by and generalizes a result of Villarreal on the use of whiskers to get Cohen-Macaulay graphs.     

Cohen-macaulay bipartite graphs

Let G be a graph on the vertex set V={x ₁, ..., x _n}. Let k be a field and let R be the polynomial ring k[x ₁, ..., x _n]. The graph ideal I(G), associated to G, is the ideal of R generated by the set of square-free monomials x _ix_j so that x _i, is adjacent to x _j. The graph G is Cohen-Macaulay over k if R/I(G) is a Cohen-Macaulay ring. Let G be a Cohen-Macaulay bipartite graph. The main result of this paper shows that G{v} is Cohen-Macaulay for some vertex v in G. Then as a consequence it is shown that the Reisner-Stanley simplicial complex of I(G) is shellable. An example of N. Terai is presented showing these results fail for Cohen-Macaulay non bipartite graphs. Partially supported by COFAA-IPN, CONACyT and SNI, México.     

On bipartite zero-divisor graphs

A (finite or infinite) complete bipartite graph together with some end vertices all adjacent to a common vertex is called a complete bipartite graph with a horn. For any bipartite graph G, we show that G is the graph of a commutative semigroup with 0 if and only if it is one of the following graphs: star graph, two-star graph, complete bipartite graph, complete bipartite graph with a horn. We also prove that a zero-divisor graph is bipartite if and only if it contains no triangles. In addition, we give all corresponding zero-divisor semigroups of a class of complete bipartite graphs with a horn and determine which complete r-partite graphs with a horn have a corresponding semigroup for r≥3.     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

A Construction of Sequentially Cohen-Macaulay Graphs

For every simple graph G,a class of multiple clique cluster-whiskered graphs Geπm is introduced,and it is shown that all such graphs are vertex decomposable;thus,the independence simplicial complex IndGeπm is sequentially Cohen-Macaulay.The properties of the graphs Geπm and Gπ constructed by Cook and Nagel are studied,including the enumeration of facets of the complex Ind Gπ and the calculation of Betti numbers of the cover ideal Ic(Geπ").We also prove that the complex △ =IndH is strongly shellable and pure for either a Boolean graph H =Bn or the full clique-whiskered graph H =Gw of G,which is obtained by adding a whisker to each vertex of G.This implies that both the facet ideal I(△) and the cover ideal Ic(H) have linear quotients.     

Graphic matroids,shellability and the Poincare Conjecture

In this paper we introduce a theory of edge shelling of graphs. Whereas the standard notion of shelling a simplicial complex involves a sequential removal of maximal simplexes, edge shelling involves a sequential removal of the edges of a graph. A necessary and sufficient condition for edge shellability is given in the case of 3-colored graphs, and it is conjectured that the result holds in general. Questions about shelling, and the dual notion of closure, are motivated by topological problems. The connection between graph theory and topology is by way of a complex ΔG associated with a graph G. In particular, every closed 2- or 3-manifold can be realized in this way. If ΔG is shellable, then G is edge shellable, but not conversely. Nevertheless, the condition that G is edge shellable is strong enough to imply that a manifold ΔG must be a sphere. This leads to completely graph-theoretic generalizations of the classical Poincaré Conjecture.     

A note on the strength and minimum color sum of bipartite graphs

The strength of a graph G is the smallest integer s such that there exists a minimum sum coloring of G using integers {1,…,s}, only. For bipartite graphs of maximum degree Δ we show the following simple bound: s≤⌈Δ/2⌉+1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree Δ≤4.     

Torus graphs and simplicial posets

For several important classes of manifolds acted on by the torus, the information about the action can be encoded combinatorially by a regular n-valent graph with vector labels on its edges, which we refer to as the torus graph. By analogy with the GKM-graphs, we introduce the notion of equivariant cohomology of a torus graph, and show that it is isomorphic to the face ring of the associated simplicial poset. This extends a series of previous results on the equivariant cohomology of torus manifolds. As a primary combinatorial application, we show that a simplicial poset is Cohen-Macaulay if its face ring is Cohen-Macaulay. This completes the algebraic characterisation of Cohen-Macaulay posets initiated by Stanley. We also study blow-ups of torus graphs and manifolds from both the algebraic and the topological points of view.     

Contractibility and the clique graph operator

To any graph G we can associate a simplicial complex Δ(G) whose simplices are the complete subgraphs of G, and thus we say that G is contractible whenever Δ(G) is so. We study the relationship between contractibility and K-nullity of G, where G is called K-null if some iterated clique graph of G is trivial. We show that there are contractible graphs which are not K-null, and that any graph whose clique graph is a cone is contractible.     

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.     

The clique operator on matching and chessboard graphs

Given positive integers m,n, we consider the graphs G_n and G_m,n whose simplicial complexes of complete subgraphs are the well-known matching complex M_n and chessboard complex M_m,n. Those are the matching and chessboard graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph G_m,n in terms of m and n, and show that G_m,n is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph G_n.     

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.     

Hamiltonicity in vertex envelopes of plane cubic graphs

In this paper we study a graph operation which produces what we call the “vertex envelope” G^∗_V from a graph G. We apply it to plane cubic graphs and investigate the hamiltonicity of the resulting graphs, which are also cubic. To this end, we prove a result giving a necessary and sufficient condition for the existence of hamiltonian cycles in the vertex envelopes of plane cubic graphs. We then use these conditions to identify graphs or classes of graphs whose vertex envelopes are either all hamiltonian or all non-hamiltonian, paying special attention to bipartite graphs. We also show that deciding if a vertex envelope is hamiltonian is NP-complete, and we provide a polynomial algorithm for deciding if a given cubic plane graph is a vertex envelope.     

Proper connection number of bipartite graphs

An edge-colored graph G is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph G, denoted by pc(G), is the smallest number of colors that are needed to color the edges of G in order to make it proper connected. In this paper, we obtain the sharp upper bound for pc(G) of a general bipartite graph G and a series of extremal graphs. Additionally, we give a proper 2-coloring for a connected bipartite graph G having δ(G) ≥ 2 and a dominating cycle or a dominating complete bipartite subgraph, which implies pc(G) = 2. Furthermore, we get that the proper connection number of connected bipartite graphs with δ ≥ 2 and diam(G) ≤ 4 is two.     

Chordal bipartite completion of colored graphs

Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.     

A class of h-perfect graphs

A graph is said to be h-perfect if the convex hull of its independent sets is defined by the constraints corresponding to cliques and odd holes, and the nonnegativity constraints. Series-parallel graphs and perfect graphs are h-perfect. The purpose of this paper is to extend the class of graphs known to be h-perfect. Thus, given a graph which is the union of a bipartite graph G₁ and a graph G₂ having exactly two common nodes a and b, and no edge in common, we prove that G is h-perfect if so is the graph obtained from G by replacing G₁ by an a-b chain (the length of which depends on G₁). This result enables us to prove that the graph obtained by substituting bipartite graphs for edges of a series-parallel graph is h-perfect, and also that the identification of two nodes of a bipartite graph yields an h-perfect graph (modulo a reduction which preserves h-perfection).