PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 99(113) (2016), 203–209 DOI: 10.2298/PIM1613203H

VERTEX DECOMPOSABLE GRAPH

N. Hajisharifi and S. Yassemi

Abstract. Let G be a simple graph on the vertex set V (G) and S = {x_{11} , …, x_{n1} } a subset of V (G). Let m_{1}, …, m_{n} ⩾ 2 be integers and G_{1}, …, G_{n} connected simple graphs on the vertex sets V (G_{i}) = {x_{i1} , …, x_{im_{i}} } for i = 1, …, n. The graph G(G_{1}, …, G_{n}) is obtained from G by attaching G_{i} to G at the vertex x_{i1} for i = 1, …, n. We give a characterization of G(G_{1}, …, G_{n}) for being vertex decomposable. This generalizes a result due to Mousivand, Seyed Fakhari, and Yassemi.

1. Introduction

Let G be a finite simple graph (no loops or multiple edges) on the vertex set V (G) = {x_{1}, …, x_{m}} and edge set E(G). Adding a whisker to G at x_{i} means adding a new vertex y and edge {x_{i}, y} to G. Villarreal showed that the graph obtained from G by adding a whisker to every vertex of G is Cohen–Macaulay [7, Proposition 2.2]. Moreover, it was shown that this graph is also unmixed and vertex decomposable [4, Theorem 4.4]. Adding a whisker to a vertex of G is the same as saying that attaching the complete graph K_{2} to a vertex of G. Let S = {x_{11}, …, x_{n1} } be a subset of V (G). The graph G(G_{1}, …, G_{n}) is obtained from G by attaching G_{i} to G at the vertex x_{i1} for i = 1, …, n. Recently, Mousivand, Fakhari and Yassemi characterized when the graph obtained by attaching arbitrary graphs to every vertex of a given graph is vertex decomposable [6, Proposition 2.3]. We generalize this result (see Theorem 3.1).

2. Preliminaries

We recall some definitions and properties that will be used later. Let K be a field. To any finite simple graph G (no loops or multiple edges) with vertex set V (G) = {x_{1}, …, x_{m}} and edge set E(G) one associates edge ideal I(G) ⊂ K[x_{1}, …, x_{m}] whose generators are all monomials x_{i}x_{j} such that {x_{i}, x_{j} } ∈ E(G).

2010 Mathematics Subject Classification: Primary 13F55, 05E40; Secondary 05C70, 05C38.

Key words and phrases: vertex decomposable, Cohen–Macaulay.

The research of S. Yassemi was in part supported by a grant from university of Tehran.

Communicated by Slobodan Simić.

The graph G is called Cohen–Macaulay over K if K[x_{1}, …, x_{m}]/I(G) has this property.

Let G be a graph with the vertex set V (G) = {x_{1}, …, x_{m}} and the edge set E(G). The induced subgraph G|_{W} for W ⊆ V (G) is defined by

G|_{W} := (W, {e ∈ E(G); e ⊂ W }).

For W ⊆ V (G) we denote G|_{V (G)∖W} by G ∖ W. If W = {x}, we write G ∖ x instead of G ∖ {x}. For any x ∈ V (G) we denote the open neighbor set of x in G by N_{G}(x), i.e., N_{G}(x) := {y ∈ V (G) | {x, y} ∈ E(G)}, N_{G}[x] := N_{G}(x) ∪ {x}. For W ⊆ V (G), we set N_{G}[W] = ⋃ _{x∈W} N_{G}[x].

A graph is complete if every two of its vertices are adjacent. The complete graph with n vertices is denoted by K_{n}.

A simplicial complex Δ on a finite set V is a collection of subsets of V which is closed under inclusion. Members of Δ are called faces. The maximum faces of Δ with respect to the inclusion are called the facets. The dimension of a face F is |F | − 1 and the dimension of a complex Δ is the maximum of the dimensions of its facets. If all the facets of Δ have the same dimension we say that Δ is pure and a complex with a unique facet is called a simplex. Let Δ be a simplicial complex on the vertex set V. The induced subcomplex of Δ|_{S} for S ⊆ V is defined by Δ|_{S} := {F ∈ Δ | F ⊆ S}.

Let F be a face of Δ. The link and the deletion of F from Δ are the simplicial complex defined by

link_{Δ} F := {G ∈ Δ | G ∩ F = ∅, G ∪ F ∈ Δ}, del_{Δ} F := {G ∈ Δ | F ⊈ G}.

If F = {x}, we write link_{Δ} x (resp. del_{Δ} x) instead of link_{Δ} {x} (resp. del_{Δ} {x}). See [5] for detailed information.

Let G = (V (G), E(G)) be a graph. A subset F of V (G) is called an independent set if no two vertices of F are adjacent. The independence complex of G, denoted by Ind(G), is the simplicial complex on the vertex set V (G), defined by

Ind(G) := {F ⊆ G | F is an independent set of G}.

A simplicial complex Δ is called vertex decomposable if it is a simplex or else has a vertex x such that

(1) both del_{Δ} x and link_{Δ} x are vertex decomposable, and

(2) there is no face of link_{Δ} x which is also a facet of del_{Δ} x. A shedding vertex is the vertex x which satisfies condition (2).

Remark 2.1. Our definition of shedding vertex is slightly different with the definition in [6], where a shedding vertex is the one which satisfies conditions (1) and (2).

Vertex decomposability was introduced in the pure case by Billera and Provan [2] and extended to nonpure complexes by Björner and Wachs [3]. A graph G is called vertex decomposable if Ind(G) has this property. In [8] Woodroofe translated the notion of vertex decomposability for graphs as follows.

A graph G is vertex decomposable if it is totally disconnected (with no edges) or else has some vertex x such that (1) both G ∖ N_{G}[x] and G ∖ x are vertex decomposable, and

(2) for every independent set S in G ∖ N_{G}[x], there exists some y ∈ N_{G}(x)

such that S ∪ {y} is independent in G ∖ x.

A vertex x which satisfies condition (2) is called a shedding vertex for G.

A graph G is called chordal if every induced cycle of G of length ⩾ 4 has a chord. In [8] Woodroofe proved that every chordal graph is vertex decomposable.

3. Vertex decomposable graph

Here we prove our main result. We write B ˙∪C for disjoint union.

Theorem 3.1. Let G be a simple graph on the vertex set V (G) and S = {x_{11}, …, x_{n1} } a subset of V (G). Let m_{1}, …, m_{n} ⩾ 2 be integers and G_{1}, …, G_{n} connected graphs on the vertex set V (G_{i}) = {x_{i1}, …, x_{im_{i}} } for i = 1, …, n and suppose that x_{i1} is a shedding vertex of G_{i} for i = 1, …, n. Then G(G_{1}, …, G_{n}) is vertex decomposable if and only if

(i) G_{i} ∖ x_{i1} and G_{i} ∖ N_{G_{i}} [x_{i1}] are vertex decomposable, for i = 1, …, n, and (ii) for any face μ of Δ = Ind(G) with μ ⊆ S, the complex link_{Δ} μ|S̄ is vertex

decomposable, where S̄ = V (G) ∖ S.

Proof. (⇐) The graph G(G_{1}, …, G_{n}) is obtained from G by attaching G_{i} to G at the vertex x_{i1} for i = 1, …, n. We prove the assertion by induction on n = |S|. Set G′ = G(G_{1}, …, G_{n}) . If S = ∅, then μ = ∅ , G′ = G and link_{Δ} μ|S̄ = Ind(G) is vertex decomposable by hypothesis.

Assume that n ⩾ 1 and the assertion holds for any graph G and every S ⊆ V (G) such that |S| ⩽ n−1. Suppose S = {x_{11}, …, x_{n1} }. We prove that x_{11} is a shedding vertex of G′. Assume that A is an independent set in G′ ∖ N_{G′}[x_{11}]. We have A = B ˙∪C where B = A ∩ [V (G_{2}) ∪ ⋯∪ V (G_{n}) ∪ (V (G) ∖ {x_{21}, …, x_{n1} })] and C = A ∩ V (G_{1}). Since N_{G_{1}} [x_{11}] ⊆ N_{G′}[x_{11}], it follows that C is an independent set in G_{1} ∖ N_{G_{1}} [x_{11}]. There exists an x_{1k} ∈ N_{G_{1}} (x_{11}) such that C ∪ {x_{1k}} is independent set in G_{1} ∖ x_{11}, because x_{11} is a shedding vertex of G_{1}. For any y ∈ V (G_{2}) ∪ ⋯∪ V (G_{n}) ∪ (V (G) ∖ {x_{21}, …, x_{n1} }), we have {x_{1k}, y} ∉ E(G′). Thus A ∪ {x_{1k}} is independent in G′∖ x_{11} and so x_{11} is a shedding vertex of G′.

Set S_{1} = {x_{21}, …, x_{n1} } and Δ′ = Ind(G ∖ x_{11}). We have G′∖ x_{11} = G′_{1} ˙∪G′_{2} where G′_{1} = G_{1} ∖ x_{11} and G′_{2} = (G ∖ x_{11})(G_{2}, …, G_{n}). Let μ ∈ Δ′ with μ ⊆ S_{1}. Thus μ ∈ Δ and μ ⊆ S. We have

link_{Δ′} μ|S̄_{1} = {F ∈ Δ′ | F ⊆ S̄_{1}, F ∪ μ ∈ Δ′, F ∩ μ = ∅}
= {F ∈ Δ | F ⊆ S̄, F ∪ μ ∈ Δ, F ∩ μ = ∅} = link_{Δ} μ|S̄.

Thus we have that link_{Δ′} μ|S̄_{1} is vertex decomposable by hypothesis. Therefore G′_{2} is vertex decomposable by induction and G′_{1} is vertex decomposable by hypothesis. It now follows from [8, Lemma 20] that G′∖ x_{11} is vertex decomposable.

Now consider G′∖ N_{G′}[x_{11}]. If S ⊆ N_{G′}[x_{11}], then

G′∖ N_{G′}[x_{11}] = (G ∖ N_{G}[x_{11}]) ˙∪(G_{1} ∖ N_{G_{1}} [x_{11}] ˙∪G_{2} ∖ x_{21} ˙∪ ⋯˙∪G_{n} ∖ x_{n1} ).

Since S ⊆ V (G), it follows that S ⊆ N_{G}[x_{11}] and V (G ∖ N_{G}[x_{11}]) ⊆ S̄.

Set μ = {x_{11}}. We have μ ∈ Δ, μ ⊆ S and link_{Δ} μ|S̄ = Ind(G ∖ N_{G}[x_{11}]) is

vertex decomposable by hypothesis. Also, for 2 ⩽ i ⩽ n, G_{i} ∖x_{i1} and G_{1}∖N_{G_{1}} [x_{11}] are vertex decomposable and hence (G_{1} ∖ N_{G_{1}} [x_{11}] ˙∪G_{2} ∖ x_{21} ˙∪ ⋯˙∪G_{n} ∖ x_{n1} ) is vertex decomposable by [8, Lemma 20]. Thus G′∖N_{G′}[x_{11}] is vertex decomposable.

Assume S ⊄ N_{G′}[x_{11}]. After relabeling the vertices of G, we assume that S ∩ N_{G}[x_{11}] = {x_{11}, …, x_{l1}} and

G′∖ N_{G′}[x_{11}] = G_{0}(G_{l+1} , …, G_{n}) ˙∪(G_{1} ∖ N_{G_{1}} [x_{11}] ˙∪G_{2} ∖ x_{21} ˙∪ ⋯˙∪G_{l} ∖ x_{l1})

where G_{0} = (G ∖ N_{G}[x_{11}]). Set S_{1} = S ∖ N_{G}[x_{11}] = {x_{l+11} , …, x_{n1} }. Let μ ∈ link_{Δ} x_{11} and μ ⊆ S_{1}. We have

link_{link_{Δ} x_{11}} μ|S̄_{1} = {F ∈ link_{Δ} x_{11} | F ⊆ S̄_{1}, F ∪ μ ∈ link_{Δ} x_{11}, F ∩ μ = ∅}
= {F ∈ Δ | F ⊆ S̄, F ∪ μ ∪ {x_{11}} ∈ Δ, F ∩ (μ ∪ {x_{11}}) = ∅}
= link_{Δ} (μ ∪ {x_{11}}) |S̄.

From hypothesis, we have that link_{Δ} (μ ∪ {x_{11}}) |S̄ is vertex decomposable and so link_{link_{Δ} x_{11}} μ|S̄_{1} is vertex decomposable for any face μ of link_{Δ} x_{11} with μ ⊆ S_{1}. Note that Ind(G_{0}) = link_{Δ} x_{11} and hence G_{0}(G_{l+1} , …, G_{n}) is vertex decomposable by induction. Also, G_{1} ∖ N_{G_{1}} [x_{11}], G_{2} ∖ x_{21}, …, G_{l} ∖ x_{l1} are vertex decomposable by hypothesis. Thus G′∖ N_{G′}[x_{11}] is vertex decomposable by [8, Lemma 20].

(⇒) Conversely, assume that G′ = G(G_{1}, …, G_{n}) is vertex decomposable. Set Δ′ = Ind(G′). After relabeling the vertices of G, we assume that μ = {x_{11}, …, x_{l1}} and μ ∈ Δ. Hence {x_{11}, …, x_{l1}} is independent set in G. We show that link_{Δ} (μ)|S̄ is vertex decomposable. For 1 ⩽ j ⩽ l, let A_{j} be a facet of Ind(G_{j}) with x_{j1} ∈ A_{j}. Note that for 1 ⩽ i ⩽ n, G_{i} is connected graph and hence has no isolated vertex. Thus Ind(G_{j}) has no cone point and let for l + 1 ⩽ j ⩽ n, A_{j} be a facet of Ind(G_{j}) with x_{j1} ∉ A_{j}. It follows that A = ⋃ _{j=1}^{n} A_{j} is a face of Δ′. One can check that link_{Δ} (μ)|S̄ = link_{Δ′} (A).

Suppose F ∈ link_{Δ} (μ)|S̄. It is clear that for 1 ⩽ i ⩽ n, x_{i} ∉ F and F ∪ μ ∈ Δ and so F ∪A is independent set in G′and hence F ∪A ∈ Δ′. Also, F ∩A = ∅ because F ∩ μ = ∅. Since Δ ⊆ Δ′ and F ∈ Δ, we have F ∈ Δ′ and so F ∈ link_{Δ′} (A).

We now consider the reverse inclusion. Let F ∈ link_{Δ′} (A). We have F ∩ A = ∅ and hence F ∩A_{j} = ∅ for 1 ⩽ j ⩽ n. We claim that for 1 ⩽ j ⩽ n, F ∩(V (G_{j})) = ∅. Let there exists an i ∈ {1, …, n} such that F ∩ V (G_{i}) ≠ ∅, and let x ∈ F ∩ V (G_{i}). Since F ∩ A_{i} = ∅, x ∉ A_{i}. On the other hand, one has F ∪ A ∈ Δ′. Therefore A_{i} ∪ {x} is an independent set in G_{i} and A_{i} ⊂ A_{i} ∪ {x}, that contradiction with facet A_{i} and so F ∩ (V (G_{i})) = ∅ and F ⊆ S̄. Since S̄ ⊆ V (G), we have F ⊆ V (G). Moreover, μ ⊆ A, F ∪ A ∈ Δ′ and Δ′ is simplicial complex, thus F ∪ μ ∈ Δ′. Also, F ∪ μ ∈ Δ, because F, μ ∈ Δ and Δ ⊆ Δ′. Since F ∩ A = ∅ and μ ⊆ A, we have F ∩ μ = ∅. Therefore F ∈ link_{Δ} (μ)|S̄. Since Δ′ = Ind(G′) is vertex decomposable, link_{Δ′} (A) is vertex decomposable by [1, Theorem 2.5] and so link_{Δ} (μ)|S̄ is vertex decomposable for any μ ⊆ S and μ ∈ Δ.

Now, we prove that G_{i} ∖x_{i1} and G_{i} ∖N_{G_{i}} [x_{i1}] are vertex decomposable for 1 ⩽ i ⩽ n. Assume G is a connected graph (otherwise consider connected components of G). Then there exists a y ∈ V (G) such that x_{i1}y ∈ E(G). Also, link_{Δ′} y and link_{Δ′} x_{i1} are vertex decomposable, because Δ′is vertex decomposable [1, Theorem 2.5]. Note that G_{i} ∖ x_{i1} and G_{i} ∖ N_{G_{i}} [x_{i1}] are respectively connected components of link_{Δ′} y and link_{Δ′} x_{i1} and so they are vertex decomposable [8, Lemma 20]. □

Let S = {x_{11}, …, x_{n1} } be a subset of V (G). The graph G ∪ W (S) is obtained from G by adding a whisker to every vertex of S.

Corollary 3.1. [1, Theorem 4.4] Let Ind(G) be the independence complex of a graph G on a vertex set V (G) and let S ⊆ V (G). Then Ind(G ∪ W (S)) is vertex decomposable if and only if Ind((G ∖ N_{G}[μ])|S̄) is vertex decomposable for all μ ∈ Ind(G) with μ ⊆ S.

Proof. Adding a whisker to a vertex of G is the same as attaching the complete graph K_{2} to a vertex of G, and we have G ∪ W (S) = G(\underbrace{K_{2}, …, K_{2}}_{n times}).

Note that link_{Ind (G)} (μ)|S̄ = Ind(G ∖ N_{G}[μ])|S̄ = Ind((G ∖ N_{G}[μ])|S̄). Now, apply Theorem 3.1. □

The cycle of length n is denoted by C_{n}. The induced cycle C_{n} of G is called chordless cycle of length n. In [8, Theorem 1] Woodroofe showed that if G is a graph with no chordless cycles of length other from 3 or 5, then G is vertex decomposable.

Corollary 3.2. Let G be a simple graph on the vertex set V (G) and S = {x_{11}, …, x_{n1} } a subset of V (G). Let m_{1}, …, m_{n} ⩾ 2 be integers and G_{1}, …, G_{n} connected simple graphs on the vertex sets V (G_{i}) = {x_{i1}, …, x_{im_{i}} } for i = 1, …, n. Assume that x_{i1} is a shedding vertex of G_{i} for i = 1, …, n. If G_{i} ∖ x_{i1} and G_{i} ∖ N_{G_{i}} [x_{i1}] for i = 1, …, n are vertex decomposable and G ∖ S is a graph with no chordless cycles of length other than 3 or 5, then G(G_{1}, …, G_{n}) is vertex decomposable.

Proof. Note that link_{Ind (G)} (μ)|S̄ = Ind(G ∖ N_{G}[μ])|S̄ = Ind((G ∖ N_{G}[μ])|S̄). For every μ ⊆ S, (G∖N_{G}[μ])|S̄ is an induced subgraph of G|S̄, so it is a graph with no chordless cycles of length other from 3 or 5, and hence it is vertex decomposable by [8, Theorem 1]. Now, apply Theorem 3.1. □

Therefore, we infer the following result.

Corollary 3.3. Let G be a simple graph on the vertex set V (G) and let S ⊆ V (G). If G ∖ S is a graph with no chordless cycles of length other than 3 or 5, then G ∪ W (S) is a vertex decomposable graph.

Corollary 3.4. Let G be a simple graph on the vertex set V (G) and S = {x_{11}, …, x_{n1} } a subset of V (G) with |S| ⩾ |V (G)| − 3. Let m_{1}, …, m_{n} ⩾ 2 be integers and G_{1}, …, G_{n} connected simple graphs on the vertex sets V (G_{i}) = {x_{i1}, …, x_{im_{i}} } for i = 1, …, n. Assume x_{i1} is a shedding vertex of G_{i} for i = 1, …, n. Moreover, let G_{i} ∖ x_{i1} and G_{i} ∖ N_{G_{i}} [x_{i1}] for i = 1, …, n be vertex decomposable. Then G(G_{1}, …, G_{n}) is vertex decomposable.

Proof. Since |S| ⩾ |V (G)| − 3, G ∖ S is a graph on at most 3 vertices. So G ∖ S is either a tree, edgeless graph, K_{2} ˙∪K_{1} or C_{3}. Thus G ∖ S is chordal and the assertion holds by Corollary 3.2. □

Therefore the following result holds.

Corollary 3.5. Let G be a simple graph, and let S ⊂ V (G). Assume that |S| ⩾ |V (G)| − 3. Then G ∪ W (S) is a vertex decomposable graph.

In the following example it is shown that the bound |V (G)| − 3 in Corollary 3.4 is sharp.

Example 3.1. Let G and G_{1} be graphs shown in the figure below, and let S = {x_{1}}. Note that the only shedding vertices of G(G_{1}) are x_{1}, y and z. Then G(G_{1}) is not vertex decomposable, because G(G_{1}) ∖ N[y] = G(G_{1}) ∖ N[z] = C_{4} and G(G_{1}) ∖ x_{1} = K_{2} ˙∪C_{4} are not vertex decomposable.

Corollary 3.6. Let G be a simple graph on the vertex set V (G) and S = {x_{11}, …, x_{n1} } a subset of V (G). Let m_{1}, …, m_{n} ⩾ 2 be integers and G_{1}, …, G_{n} connected simple graphs on the vertex sets V (G_{i}) = {x_{i1}, …, x_{im_{i}} } for i = 1, …, n. Assume that x_{i1} is a shedding vertex of G_{i} for i = 1, …, n. Moreover, let G_{i}, G_{i} ∖ x_{i1} and G_{i} ∖ N_{G_{i}} [x_{i1}] for i = 1, …, n be vertex decomposable. Then

(i) If S is a vertex cover of G, then G(G_{1}, …, G_{n}) is vertex decomposable. (ii) If G ∖ S is a forest, then G(G_{1}, …, G_{n}) is vertex decomposable. (iii) If G = C_{n} is a cycle and x a vertex of C_{n}, then G(G_{1}) is vertex decom-

posable.

Proof. If S is a vertex cover of G, then G ∖ S is an edgeless graph and so it is a chordal graph. Also, every forest is a chordal graph. Now, (i) and (ii) follow from Corollary 3.2. Finally, the resulting graph of removing a vertex from C_{n} is a tree and hence (iii) follows from (ii). □

References

1. J. Biermann, C. A Francisco, H. T. Há, A. Van Tuyl, Colorings of simplicial complexes and vertex decomposability, J. Commut. Algebra 7 (2015), 337–352.

2. L. J. Billera, J. S. Provan, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5(4) (1980), 576–594.

3. A. Björner, M. Wachs, Shellable nonpure complexes and posets I, Trans. Am. Math. Soc. 348 (1996), 1299–1327.

4. A. Dochtermann, A. Engström, Algebraic properties of edge ideals via combinatorial topology, Electron. J. Comb. 16(2) (2009), research paper 2, 24 pp.

5. J. Herzog, T. Hibi, Monomial Ideals, Grad. Texts Math. 260, Springer-Verlag, 2010.

6. M. Mousivand, S. A. Seyed Fakhari, S. Yassemi, A new construction for Cohen–Macaulay graphs, Commun. Algebra 43(12) (2015), 5104–5112.

7. R. H. Villarreal, Cohen–Macaulay graphs, Manuscr. Math 66 (1990), 277–293.

8. R. Woodroofe, vertex decomposable graphs and obstructions to shellability, Proc. Am. Math. Soc 137 (2009), 3235–3246.

Young Researchers and Elite Club (Received 31 12 2014) Khomein Branch (Revised 15 10 2015) Islamic Azad University Khomein Iran

hajisharifi@iaukhomein.ac.ir

School of Math. Stat. Comp. Sci. College of Science University of Tehran Tehran Iran

yassemi@ut.ac.ir