Let be a finite simple graph with the vertex set and let be its edge ideal in the polynomial ring . We compute the depth and the Castelnuovo-Mumford regularity of when or is a graph obtained from Cohen-Macaulay bipartite graphs , by the operation or operation, respectively.
Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by has property . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.
We construct a locally compact Hausdorff topology on the path space of a finitely aligned k-graph Λ. We identify the boundary-path space ∂Λ as the spectrum of a commutative C*-subalgebra of C*(Λ). Then, using a construction similar to that of Farthing, we construct a finitely aligned k-graph Λ̃ with no sources in which Λ is embedded, and show that ∂Λ is homeomorphic to a subset of ∂Λ̃. We show that when Λ is row-finite, we can identify C*(Λ) with a full corner of C*(Λ̃), and deduce that is isomorphic...
The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S ⊆ V (G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i. In this note, we determine the path-distance-width of hypercubes.
The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices and five edges . A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from...
The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this...
The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like...