The structure of graphs with forbidden induced C4 , C4 , C5 , S3 , chair and co-chair

Salman Ghazal

Department of Mathematics Faculty of Sciences I, Lebanese University Beirut - Lebanon

salmanghazal@hotmail.com

We find the structure of graphs that have no C4, C4, C5, S3, chair and co-chair as induced subgraphs. Then we deduce the structure of the graphs having no induced C4, C4, S3, chair and co-chair and the structure of the graphs G having no induced C4, C⁴ and such that every induced P⁴ of G is contained in an induced C⁵ of G.

Keywords: forbidden subgraph, threshold graph, C4, P⁴

Mathematics Subject Classification : 05C75

DOI: 10.5614/ejgta.2018.6.2.2

1. Introduction

In this paper, graphs are finite and simple. The vertex set and edge set of a graph G are denoted by V (G) and E(G) respectively. Two edges of a graph G are said to be adjacent if they have a common endpoint and two vertices x and y are said to be adjacent if xy is an edge of G. The neighborhood of a vertex v in a graph G, denoted by NG(v), is the set of all vertices adjacent to v and its degree is dG(v) = |NG(v)|. We omit the subscript if the graph is clear from the context. For two set of vertices U and W of a graph G, let E[U, W] denote the set of all edges in the graph G that joins a vertex in U to a vertex in W. A graph is empty if it has no edges. For A ⊆ V (G), G[A] denotes the sub-graph of G induced by A. If G[A] is an empty graph, then A is called a

Received: 11 December 2016, Revised: 1 March 2018, Accepted: 28 March 2018.

stable set. While, if G[A] is a complete graph, then A is called a clique set, that is any two distinct vertices in A are adjacent. The complement graph of G is denoted by G and defined as follows: V (G) = V (G) and xy ∈ E(G) if and only if xy /∈ E(G). A graph H is called a forbidden subgraph of G if H is not (isomorphic to) an induced subgraph of G.

A cycle on n vertices is denoted by Cⁿ = v1v2...vnv¹ while a path on n vertices is denoted by Pⁿ = v1v2...vn. A chair is any graph on 5 distinct vertices x, y, z, t, v with exactly 5 edges xy, yz, zt and zv. The co-chair or chair is the complement of a chair. S³ is the graph on 6 vertices as indicated in Figure 1.

Figure 1. The graphs C4, C5, C¯ ⁴, S3, Chair and Co-chair.

Many graphs encountered in the study of graph theory are characterized by configurations or subgraphs they contain. However, there are occasions where it is easier to characterize graphs by sub-graphs or induced sub-graphs they do not contain. For example, trees are the connected graph without (induced) cycles. Bipartite graphs are those without (induced) odd cycles ([1]). Split graphs are those without induced C4, C⁴ and C5. Line graphs are characterized by the absence of only nine particular graphs as induced sub-graph (see [2]). Perfect graphs are characterized by C2n+1 and C2n+1 being forbidden, for all n ≥ 2 (see [3]). The purpose of this paper is to find the structure of graphs such that C4, C4, C5, S³ chair and co-chair are forbidden subgraphs. These graphs will be called generalized combs and they are generalization of generalized stars and generalization of combs (See [6, 8]). Seymour's Second Neighborhood Conjecture (see [9]) is proved for orientation of graphs obtained from the complete graph by deleting the edges of a generalized star and for those obtained by deleting the edges of a comb [6, 8]. Generalized stars (also called threshold graphs) are the graphs with C4, C⁴ and P⁴ forbidden. Finding the structure of the generalized comb, might give a clearer vision for an attempt to prove Seymour's conjecture for oriented graphs obtained from the complete graph by deleting the edges of a generalized comb.

2. Preliminary Definitions and Theorems

Definition 1. A graph G is a called a split graph if its vertex set is the disjoint union of a stable set S and a clique set K. In this case, G is called an {S, K}-split graph.

If G is an {S, K}-split graph and ∀s ∈ S, ∀x ∈ K we have sx ∈ E(G), then G is called a complete split graph.

If G is an {S, K}-split graph and E[S, K] forms a perfect matching of G, then G is called a perfect split graph.

Theorem 2.1. (Foldes and Hammer [4]) ¨ G is a split graph if and only if C4, C⁴ and C⁵ are forbidden subgraphs of G.

Definition 2. ([5]) A threshold graph G can be defined as follows:

• 1) V (G) = n[ +1 i=1 (Xⁱ ∪ Ai−1), where the Ai's and Xi's are pair-wisely disjoint sets.
• 2) K := n[ +1 i=1 Xi is a clique and the Xi's are nonempty, except possibly Xn+1.
• 3) ^S := [ⁿ i=0 Ai is a stable set and the Ai's are nonempty, except possibly A0.
• 4) ∀ i, j ∈ [1, n] and j ≤ i, G[Aⁱ ∪ X^j ] is a complete split graph.
• 5) The only edges of G are the edges of the subgraphs mentioned above.

In this case, G is called an {S, K}-threshold graph.

In fact, threshold graphs are exactly the generalized stars defined in [6].

Theorem 2.2. (Hammer and Chvatal [5]) ` G is a threshold graph if and only if C4, C⁴ and P⁴ are forbidden subgraphs of G.

Theorem 2.3. ([7]) C4, C⁴ are forbidden subgraphs of a graph G if and only if V (G) is disjoint union of three sets S, K and C such that:

• 1) G[S ∪ K] is an {S, K}-split graph;
• 2) G[C] is empty or isomorphic to the cycle C5;
• 3) every vertex in C is adjacent to every vertex in K but to no vertex in S.

3. Main Results

Lemma 3.1. Suppose that C4, C4, C5, chair and co-chair are forbidden subgraphs of G. If the path mbb⁰m⁰ is an induced subgraph of G, then:

\[N(m) - \{b\} = N(m') - \{b'\}\]

and

\[N(b) - \{m\} = N(b') - \{m'\}.\]

Proof. Since C4, C⁴ and C⁵ are forbidden, then G is an {S, K}-split graph for some stable set S and a clique set K. Since mbb⁰m⁰ is an induced subgraph of G, then m, m⁰ ∈ S and b, b ⁰ ∈ K.

Assume that there is x ∈ N(m) − {b} but x /∈ N(m⁰ ) − {b ⁰}. Since xm is an edge of G and S is stable, then we must have x ∈ K. But K is a clique, then x is adjacent to b and b 0 . Thus G[{x, m, b, b⁰ , m⁰}] is a co-chair. Contradiction. So N(m) − {b} ⊆ N(m⁰ ) − {b ⁰}. By symmetry, N(m⁰ ) − {b ⁰} ⊆ N(m) − {b}. Thus N(m) − {b} = N(m⁰ ) − {b 0}.

Assume that there is x ∈ N(b) − {m} but x /∈ N(b 0 ) − {m⁰}. Suppose that x ∈ S. Then G[{x, m, b, b⁰ , m⁰}] is a chair. Contradiction. Thus x ∈ K. But K is a clique. Whence x ∈ N(b 0 ){m⁰}. Thus N(b) − {m} ⊆ N(b 0 ) − {m⁰}. By symmetry, N(b 0 ) − {m⁰} ⊆ N(b) − {m}. Therefore N(b) − {m} = N(b 0 ) − {m⁰}.

Proposition 3.1. If P⁴ is a forbidden subgraph of an {S, K}-split graph G, then G is an {S, K}-threshold graph.

Proof. We prove this by induction on the number of vertices of G. This is clearly true for small graphs. Suppose that P⁴ is a forbidden subgraph of an {S, K}-split graph G. It is clear that G is a threshold graph. We have to prove that G is {S, K}-threshold graph. Let x ∈ K be a vertex with minimum degree in G, that is dG(x) = min{dG(y); y ∈ K} and G⁰ := G − x be the graph induced by the vertices of G except x (If K = φ, then the statement is true). Then P⁴ is a forbidden subgraph of the {S, K − {x}}-split graph G⁰ . By the induction hypothesis, G⁰ is an {S, K − {x}} threshold graph. We follow the notations in Definition 2. Assume that ∃a ∈ S − Aⁿ such that ax ∈ E(G). Let xⁿ ∈ Xn. Since d(xn) ≥ d(x), then there is aⁿ ∈ Aⁿ such that anxⁿ ∈ E(G) but anx /∈ E(G). Then axxnaⁿ is an induced P⁴ in G. Contradiction. Thus we may suppose that N(x) ∩ S ⊆ An. If N(x) ∩ Aⁿ = φ, then we add x to Xn+1. If N(x) ∩ Aⁿ = An, then we add xⁿ to Xn. Otherwise φ ( N(x) ∩ Aⁿ ( An. In this case we do the following: remove from Aⁿ the element of N(x) ∩ An, create An+1 = N(x) ∩ An, remove the elements of Xn+1 to the new set Xn+2 and add x to Xn+1 (so that the new Xn+1 = {x}). Then G is {S, K}-threshold graph.

Definition 3. A graph G is called a generalized comb if:

1) V (G) is disjoint union of sets A0, ..., An, M1, ..., M^l , X1, ...., Xn+1, Y2, ..., Yl+2. Let Y¹ = X¹ (These sets are called the sets of the generalized comb G).

2) \[S := A \cup M\] is a stable set, where \(M = \bigcup_{i=1}^{l} M_i\) and \(A = \bigcup_{i=0}^{n} A_i\).

The structure of graphs with forbidden induced C4, C4, C5, S3, chair and co-chair | S. Ghazal

3) \[K:=X\cup Y\] is a clique, where \(X=\bigcup_{i=1}^{n+1}X_i\) and \(Y=\bigcup_{i=1}^{l+2}Y_i\).

• 4) ∀ i, j ∈ [1, n] and j ≤ i, G[Aⁱ ∪ X^j ] is a complete split graph.
• 5) G[A ∪ Y ] is a complete split graph.
• 6) ∀ i ∈ [1, l], G[Yⁱ ∪ Mⁱ ] is a perfect split graph or Mⁱ = φ.
• 7) ∀ i, j ∈ [1, l + 1] and i < j, G[Y^j ∪ Mⁱ ] is a complete split graph.
• 8) Xn+1, Yl+2, Yl+1 and A⁰ are the only possibly empty sets among the X⁰ i s, Y 0 i s, A⁰ i s.
• 9) The only edges of G are the edges of the subgraphs mentioned above.

In this case, we say that G is an {S, K}-generalized comb. Note, that we may assume that no two consecutive sets Mⁱ and Mi+1 are both empty. We use this assumption in the rest.

Figure 2. Generalized Comb, with n = l = 3, Xn+1 = Yl+2 = φ, A ∪ M is stable, X ∪ Y is a clique. Any 2 vertices in 2 sets joined by a thick bold edge are adjacent.

It is clear that the comb defined in [8] is a particular case of the generalized comb (see Figure 3). Moreover, we have the following:

Lemma 3.2. Every {S, K}-threshold graph is an {S, K}-generalized comb.

Proof. Let G be an {S, K}-threshold graph defined as in Definition 2. Following the notations in Definition 3, we take l = 1 and M^l = Yl+1 = Yl+2 = φ. This shows that G is an {S, K} generalized comb.

Figure 3. Comb G. X ∪ Y is a clique, G[X ∪ M] is a perfect split graph, no edges between Y and M.

Theorem 3.1. If S3, chair and co-chair are forbidden subgraphs of an {S, K}-split graph G, then G is an {S, K}-generalized comb.

Proof. We prove the statement by induction on the number of vertices. The statement is true for small graphs. Suppose that S3, chair and co-chair are forbidden subgraphs of an {S, K}-split graph G. If P⁴ is also a forbidden subgraph of G, then G is an {S, K}-threshold graph, and hence, G is an {S, K}-generalized comb. So we may suppose that G contains at least one induced path of length four.

Suppose that G has exactly one induced path of length four, say mbb⁰m⁰ . Suppose N(m) = {b}. Then N(m⁰ ) = {b ⁰}. Let H = G[K ∪ S − {m, m⁰}]. By induction hypothesis, we have H is {S − {m, m⁰}, K}-generalized comb. But H has no induced P4, then H is in fact {S − {m, m⁰}, K} threshold graph. We use the nation in the definition of threshold graph, in what follows. Assume that ∃i ≥ 2 such that b ∈ Xⁱ . Let x ∈ X¹ and a ∈ A1. Then mbxa is induced P⁴ in G, a contradiction. So b ∈ X1. Then also b ⁰ ∈ X1, because b and b ⁰ have the same neighborhood in H. Define Y² = φ, M¹ = {m, m⁰}, Y³ = X¹ − {b, b⁰} and the new X¹ is the {b, b⁰}. Then G is an {S, K}-generalized comb with l = 1 and Yl+1 = φ.

Otherwise, G has at least two induced P4. Let m be a vertex of G such that d(m) = min{d(z); z is a leaf of an induced P⁴ in G} and let P = mbb⁰m⁰ be an induced P4. Note that d(m) = d(m⁰ ). Let Q = udd⁰u ⁰ be an induced P⁴ distinct from P (Note that m, m⁰ , u, u⁰ ∈ S while b, b⁰ , d, d⁰ ∈ K). Either m /∈ {u, u⁰} or m⁰ ∈ { / u, u⁰}, since N(m) − {b} = N(m) − {b ⁰} (Lemma 3.1). We may assume without loss of generality that m /∈ {u, u⁰} and let H = G[(S − m⁰ ) ∪ (K − b 0 )]. By the induction hypothesis, H is an {S − m⁰ , K − b ⁰}−generalized comb.

Suppose first that m⁰ ∈ {u, u⁰} and assume without loss of generality that m⁰ = u 0 . Assume that b ⁰ 6= d 0 . If b = d, then by using Lemma 3.1 repeatedly, we can prove easily that G[{m⁰ , m, u, b, b⁰ , d⁰}] is an S3, a contradiction. So b 6= d. Note that b ⁰ 6= d, because u 0 b ⁰ = mb⁰ ∈ E(G), while u ⁰d /∈ E(G). By applying Lemma 3.1 repeatedly, we have the following: Since u 0 b ⁰ = m⁰ b ⁰ ∈ E(G), then ub⁰ ∈ E(G), thus ub ∈ E(G), whence u 0 b ∈ E(G), therefore m0 b ∈ E(G), which is a contradiction. Therefore, b ⁰ = d 0 . Note that b 6= d, since otherwise, we

get u ∈ N(b) − {m}, thus by Lemma 3.1, we get u ∈ N(b 0 ) − {m⁰} = N(d 0 ) − {u ⁰}, whence ud⁰ ∈ E(G), a contradiction. Since udd⁰u ⁰ = udb⁰m⁰ is an induced path of length four of G, then by Lemma 3.1 also udbm is an induced path of G and thus of H. Then, by the definition of the generalized comb H, ∃i; u, m ∈ Mⁱ (We follow the notations of definition 3.). In this case we add m0 to Mⁱ and b 0 to Yⁱ . This shows that G is an {S, K}−generalized comb.

Now, suppose that m⁰ ∈ { / u, u⁰}. Assume that m ∈ A. By definition of the generalized comb H and since udd⁰u 0 is an induced P⁴ of H, we get that NH(u) ⊆ NH(m) and d ⁰ ∈ NH(m) − NH(u). So dH(u) < dH(m). Assume that b /∈ NH(u). Then b /∈ N(u) and thus by Lemma 3.1, we get b ⁰ ∈/ N(u). Therefore, dG(u) = dH(u) < dH(m) = dG(m), which is a contradiction to the choice of m. Hence, b ∈ NH(u) and so, by Lemma 3.1, we get b, b⁰ ∈ N(u) ∩ N(u 0 ). Note that d, d⁰ ∈ N(m) and hence d, d⁰ ∈ N(m⁰ ). Thus G[{u, d⁰ , m⁰ , b, m, b⁰}] is an induced S³ in G, a contradiction.

So m ∈ M. Let l be the greatest such that M^l 6= φ. Suppose that m /∈ M^l . Let m⁰⁰ ∈ M^l and b ⁰⁰ ∈ Y^l be its neighbor. ∃i < l such that m ∈ Mⁱ . Then b ⁰⁰m ∈ E(G) and NH(m⁰⁰) ⊆ NH(m). Let c ∈ Yⁱ be the neighbor of m. Let k be the smallest such that k > i and M^k 6= φ (Note that k exists and i < k ≤ l, moreover we may assume k = i + 1 or k = i + 2).

Suppose b ∈ N(m⁰⁰). Then also b ⁰ ∈ N(m⁰⁰). If b 6= b ⁰⁰, then ∃j > k such that b ∈ Y^j . Then by using Lemma 3.1, we can prove easily that G[{m, m⁰ , m⁰⁰, b, b⁰ , c}] is an induced S³ of G, a contradiction. However, if b = b 0 , then also by using Lemma 3.1, we can observe that G[{m, m⁰ , m⁰⁰, b, b⁰ , c}] is an induced S³ in G, a contradiction.

Suppose b /∈ N(m⁰⁰). Then b ⁰ ∈/ NH(m) − NH(m⁰⁰), b 6= b ⁰⁰ and ∃i < j ≤ k such that b ∈ Y^j . Thus d(m⁰⁰) = dH(m⁰⁰) < dH(m) = dG(m), a contradiction is reached if m⁰⁰ is a leaf of an induced P⁴ of G. So, we have m⁰⁰ is not a leaf of an induced P⁴ of G and thus of H and thus M^k = {m⁰⁰} and j < k. If c = b, then we add b 0 to Yⁱ and m⁰ to Mⁱ and thus G is an {S, K}−generalized comb. So suppose c 6= b. Assume there is mcm⁰⁰⁰b ⁰⁰⁰ an induced P⁴ in H. Then m⁰⁰⁰ ∈ Mⁱ and b ⁰⁰⁰ ∈ Yⁱ . Then by using Lemma 3.1, we can observe that G[{m, m⁰ , m⁰⁰⁰, b, b⁰ , c}] is an induced S³ in G, a contradiction. Thus m is not a leaf of an induced P⁴ of H, that is Mⁱ = {m}. By definition of k, we get M^j = φ. Thus j = i+ 1 and k = i+ 2. Now, to Yi+1 we add c and remove b, while to Yⁱ we add b and remove c. Then, we can add b 0 to Yⁱ and m⁰ to Mⁱ to get that G is an {S, K}−generalized comb.

Therefore m ∈ M^l . Let Y^l ∩ N(m) = {c}. If b = c, then we add b 0 to Y^l and m⁰ to M^l and thus G is {S, K}-generalized comb. Now suppose that b 6= c. Suppose that c is not the only vertex in Y^l and thus there is an induced path mcc⁰⁰m⁰⁰ with c, c⁰⁰ ∈ Y^l and m⁰⁰ ∈ Y^l . By using Lemma 3.1, we can prove easily that G[{b, b⁰ , c, m, m⁰ , m⁰⁰}] is an induced S³ of G a contradiction. Therefoe c is the only vertex in Y^l . Since bm ∈ E(H), then b ∈ Yl+1. We do the following: To Yl+1 add c and remove b and to Y^l add b and remove c. Then we add b 0 to Y^l and m⁰ to M^l (as in the case b = c) and this shows that G is an {S, K}-generalized comb.

Corollary 3.1. G is a generalized comb if and only if C4, C4, C5, S³ chair and co-chair are forbidden subgraphs of G.

Proof. The necessary condition is obvious by the definition of the generalized comb. For the sufficient condition it is enough to note that the statement C4, C4, C5, S3, chair and co-chair are

forbidden subgraphs of G is equivalent to the statement that G is a split graph and S3, chair and co-chair are forbidden subgraphs of G.

Corollary 3.2. G is a generalized comb if and only if every induced subgraph of G is a generalized comb.

Proof. Let G⁰ be an induced subgraph of a generalized comb G. It is clear that G⁰ contains no induced C4, C4, C5, chair and co-chair. Thus G⁰ is a generalized comb. The sufficient condition is clear.

Corollary 3.3. C4, C4, S3, chair and co-chair are forbidden subgraphs of a graph G if and only if V (G) is disjoint union of three sets S, K and C such that:

• 1) G[S ∪ K] is an {S, K}-generalized comb;
• 2) G[C] is empty or isomorphic to the cycle C5;
• 3) every vertex in C is adjacent to every vertex in K but to no vertex in S.

Proof. The sufficient condition is clear by construction of G. We prove the necessary condition. Suppose that C4, C4, S3, chair and co-chair are forbidden subgraphs of a graph G. Then by Theorem 2.3, V (G) is disjoint union of three sets S, K and C such that:

• 1) G[S ∪ K] is an {S, K}-split graph;
• 2) G[C] is empty or isomorphic to the cycle C5;
• 3) every vertex in C is adjacent to every vertex in K but to no vertex in S.

Then C4, C4, C5, S³ chair and co-chair are forbidden subgraphs of G[S ∪ K]. Thus G[S ∪ K] is an {S, K}-generalized comb.

Corollary 3.4. C4, C⁴ are forbidden subgraphs of G and every induced P⁴ of G is contained in an induced C⁵ of G if and only if V (G) is disjoint union of three sets S, K and C such that:

• 1) G[S ∪ K] is an {S, K}-threshold;
• 2) G[C] is empty or isomorphic to the cycle C5;
• 3) every vertex in C is adjacent to every vertex in K but to no vertex in S.

Proof. The sufficient condition is clear by construction of G. We prove the necessary condition. Suppose that C4, C⁴ are forbidden subgraphs of a graph G and every induced P⁴ of G is contained in an induced C⁵ of G. Then by Theorem 2.3, V (G) is disjoint union of three sets S, K and C such that:

• 1) G[S ∪ K] is an {S, K}-split graph;
• 2) G[C] is empty or isomorphic to the cycle C5;
• 3) every vertex in C is adjacent to every vertex in K but to no vertex in S.

Then G[C] is the unique induced C⁵ of G or G has no induced C5. Then C4, C4, P⁴ are forbidden subgraphs of G[S ∪ K]. Thus G[S ∪ K] is an {S, K}-threshold graph.

References

• [1] D. Ko, Theorie der endlichen und unendlechen Graphen, ¨ Akademische Verllagsgesellschaft (1936) (reprinted Chelsea 1950).
• [2] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory 9 (2) (1970), 129–135.
• [3] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51–229.
• [4] S. Foldes, P.L. Hammer, Split graphs, ¨ Congr. Numer. 19 (1977), 311–315.
• [5] P.L. Hammer, V, Chvatal, Aggregation of inequalities in integer programming, ` Annals of Discrete Math. 1 (1977), 145–162.
• [6] S. Ghazal: Seymour's second neighborhood conjecture in tournaments missing a generalized star, J. Graph Theory 71 (2012), 89–94.
• [7] Z. Blazsik, M. Hujter, A. Pluh ´ ar, and Z. Tuza, Graphs with no induced ´ C⁴ and 2K2, Discrete Math. 115 (1-3) (1993), 51–55.
• [8] S. Ghazal, A contribution to the second neighborhood problem, Graphs Combin. 29 (2013), 1365–1375.
• [9] N. Dean and B.J. Latka, Squaring the tournament: an open problem, Congr. Numer. 109 (1995), 73–80.