Printer Friendly

On probe 2-clique graphs and probe diamond-free graphs.

1 Introduction

Let G be a class of graphs. A graph G = (V, E) is probe G if its vertices can be partitioned into probe vertices (P) and a stable set of nonprobe vertices (N) in such a way that there exists a set of non-edges F of G, whose endpoints belong to N, such that [G.sup.*] = (V,E [union] F) is in G. The graph [G.sup.*] is defined to be a probe G completion of G, if there is no confusion we just call it a completion of G. By (N, P), we denote a probe partition of G. A graph is interval if it is the intersection graph of intervals in the real line. Probe interval graphs were defined by Zhang [19]. He introduced them to deal with a problem concerning DNA mapping. A graph G = (P [union] N, E) is said to be a partitioned graph if its vertex set is partitioned into two sets: a set P of probe vertices and a stable set N of nonprobe vertices. We say that G is a partitioned probe G graph if there exists a completion [G.sup.*] = (P [union] N, E [union] F) of G belonging to G, where all the edges belonging to F have both endpoints in N. We will call nonpartitioned probe G graphs to those probe G graphs without a prescribed probe partition, when it is clear from the context we will just call them probe G graphs. In the case of G being the class of interval graphs, many progresses have been reached in the study of the class of probe G graphs, known as probe interval graphs. Given a graph a G with a prescribed partition (P, N) of its vertex set into probe (P) and nonprobe (N) vertices, the problem of decided whether there exists a completion of G = (P [union] N, E) into an interval graph [G.sup.*] = (P [union] N, E [union] F) can be solved in O([n.sup.2])-time [13], this algorithm involves modified PQ-trees. Another algorithm, which deals with this problem, is the one presented in [16] that uses modular decomposition and whose complexity is O(n + m log(n)). In the case of nonpartitioned probe interval graphs, an O([m.sup.2]) recognition algorithm was found when the input graph is restricted to cocomparability graphs [3]. In [7] is presented a polynomial-time algorithm to recognize nonpartitioned probe interval graphs, but the complexity of this algorithm is not given.

Recently, several researchers have started to study probe partitioned and nonpartitioned G graphs for different kind of classes G of graphs (see e.g., [1], [4], [6] [9], [10]). In this work, we present a structural result on probe 2-clique graphs that leads to a polynomial-time recognition algorithm for this class, and a forbidden induced subgraph characterization of probe diamond-free graphs implying a forbidden induced subgraph characterization for probe block graphs. In [5], it is given a polynomial-time recognition algorithm for deciding if a given graph is probe block. In this article are considered both the partitioned and the nonpartitioned problem. Later, a linear-time algorithm is presented in [15]. The recognition complexity for probe chordal graphs given a partition of its vertices into probe and nonprobe is O([absolute value of P][absolute value of E]) [2], whereas in the case that no partition is given the complexity is O([[absolute value of E].sup.2]) [2].

For concepts and notation not defined here we refer the reader to [18]. All graphs in this paper are without loops and without multiple edges. Given a graph G = (V, E) and a set A C V, we denote by G[A] the subgraph of G induced by A. A graph H is a spanning subgraph of G if V(H) = V(G) and E(H) [subset or equal to] E(G). Spanning subgraphs are not necessarily induced. By [C.sub.n] we denote a chordless cycle on n vertices. By [d.sub.G](v), we denote the degree of a vertex v in G. A clique is a set of pairwise adjacent vertices. The complete graph is a graph whose vertices are pairwise adjacent. The complete graph on n vertices is denoted by [K.sub.n]. Complete graphs on three vertices are called triangles. By [N.sub.G](v), we denote the neighborhood of a vertex v in a graph G, if it is clear from the context we may use N(v). By [N.sub.G][v] = [N.sub.G](v) [union] {v}, we denote the closed neighborhood of v. Given a set of graphs H, we denote by H-free the family of those graphs that do not contain any graph in H as induced subgraph. If H consists of a single element H, we use H-free for short. A vertex v is said to be complete (anticomplete) to a set of vertices A, if v is adjacent (nonadjacent) to all the vertices of A.

The graph [K.sub.4] - e is called diamond (see the graph Hi in Figure 1). A graph G is a block graph if every connected induced subgraph of it either is a complete graph or has a cut-vertex. In [14] it is proved that block graphs are exactly the diamond-free chordal graphs. A graph is chordal if it has no [C.sub.n] with n [greater than or equal to] 4 as an induced subgraph. A graph is Ptolemaic if it is chordal and gem-free. (A gem is the graph F2 in Figure 2). A graph is split if its vertex set can be partitioned into a clique and a stable set; more details on this class of graphs can be found in [8]. A graph is 2-clique also referred, in the literature, as co-bipartite) if its vertices can be partitioned into two cliques. This graph class has been studied in connection with circular-arc graphs in [12, 17]

The article is organized as follows. In Section 2, we present a structural result on probe 2-clique graphs. Such a result leads to a polynomial-time algorithm to recognize the class. In Section 3, we present a characterization by forbidden structures for partitioned probe diamond-free graphs, which is used in Section 4 to characterize probe diamond-free graphs by forbidden induced subgraphs. Besides, it is shown that the class of probe block graphs is exactly the intersection between the classes of chordal graphs and probe diamond-free graphs. We conclude the article with a section of further remarks.

2 Probe 2-clique graphs

Denote by T(G) the spanning subgraph of G whose edge set contains precisely the edges that are contained in some triangle of G.

Notice that if G is probe 2-clique then we can add some set of edges C (possibly empty), whose endpoints form a stable set S in G, so that the resulting graph is 2-clique. Since the fact of adding edges to a 2-clique graph gives a 2-clique graph, we could add to G all the edges whose endpoints belong to S and the resulting graph would be also 2-clique. Therefore, if G is probe 2-clique, then there exists a complete graph C', contained in [bar.G], having a set of edges E(C') such that [bar.G] - E(C') is bipartite. As every subgraph of a bipartite graph is bipartite, [bar.G] - E (C') is also bipartite. Moreover, for any complete graph C containing C', [bar.G] - E(C) is bipartite.

Consequently, we have the following results.

Lemma 1 Let G be a graph such that [bar.G] is triangle-free. Then, G is probe 2-clique if and only if [bar.G] contains an edge e such that [bar.G] - e is bipartite.

Proof: If G is a graph with no edge the result is satisfied trivially, so we will consider that the graph G contains at least an edge. Let G be a probe 2-clique graph such that [bar.G] is triangle-free. Since G is triangle-free and thus the only complete graphs in [bar.G] are its edges, by the observation above, there exists an edge e such that G - e is bipartite. Conversely, if there exists an edge e such that [bar.G] - e is bipartite, then (since the edge e is a clique in [bar.G]) G is probe 2-clique.

For instance, the graph [bar.[C.sub.7]], whose complement graph is clearly triangle-free, is not 2-clique and its complement graph which is not bipartite becomes bipartite by deleting any of its edges and therefore [bar.[C.sub.7]] is probe 2-clique.

Lemma 2 Let G be such that [bar.G] contains triangles. Then, G is probe 2-clique if and only if T(G) has a complete subgraph C such that [bar.G] - E(C) is bipartite.

Proof: Let G be a graph such that [bar.G] contains a triangle H. Suppose that G is probe 2-clique. Then, G has a complete subgraph C such that [bar.G] - E(C) is bipartite. If [absolute value of (V(C))]| [greater than or equal to] 3, each edge of C is contained in a triangle of [bar.G], and C is a complete subgraph of T([bar.G]). If [absolute value of (V(C))]| [less than or equal to] 2, then C must be an edge of H, thus a complete subgraph of T([bar.G]). Conversely, suppose T([bar.G]) has a complete subgraph C such that [bar.G] - E(C) is bipartite. Clearly, any complete subgraph of T([bar.G]) is also a complete subgraph of G. Consequently, [bar.G] has a complete subgraph C such that [bar.G] - E(C) is bipartite, meaning that G is probe 2-clique.

For instance, the graph [C.sub.6] is not 2-clique and, since T([bar.[C.sub.6]]) is the disjoint union of two copies of [K.sub.3], [C.sub.6] is not probe 2-clique. Notice also that, in Lemma 2 complete subgraph can be replaced by maximal complete subgraph and the lemma is still true. This observation is crucial to obtain a polynomial-time algorithm to recognize the class of probe 2-clique graphs.

Theorem 3 Let G be a probe 2-clique graph such that [bar.G] contains triangles. Then, T([bar.G]) is a split graph.

Proof: By Lemma 2, T([bar.G]) has a complete subgraph C such that [bar.G] - E(C) is bipartite. Let S be the subset of vertices of T([bar.G]) not contained in V(C). Suppose T([bar.G]) has an edge e linking two vertices of S. Then e forms a triangle in [bar.G] with some vertex v. However, such a triangle has none of its edges in E(C) and thus [bar.G] - E(C) cannot be bipartite, a contradiction. Therefore, T([bar.G]) is a split graph.

Algorithmic aspects: If [bar.G] is triangle-free, then check if for some edge e of [bar.G], [bar.G] - e is bipartite. Otherwise, find all the triangles of [bar.G] and construct T([bar.G]). If T([bar.G]) is not a split graph, then G is not probe 2-clique. Otherwise, find each maximal complete subgraph C of T([bar.G]) and verify if [bar.G] - E(C) is bipartite. Since a split graph has a linear number of maximal complete subgraphs, all these steps can be clearly performed in O([n.sup.3]) time.

3 Partitioned probe diamond-free graphs

Let G = (P [union] N, E) and H = (P' [union] N', E') be two partitioned graphs with stable sets N and N'. The graph H is defined to be a partitioned subgraph (a partitioned induced subgraph) of G, if H is a subgraph (an induced subgraph) of G, N' [subset or equal to] N and P' [subset or equal to] P. When the context is clear, we just say that H is (an induced subgraph) a subgraph of G. We say that G is isomorphic to H if and only if there exists a one-to-one function f : P [union] N [right arrow] P' [union] N' preserving adjacency and such that f (v) [member of] N' for all v [member of] N, and f (v) [member of] P' for all v [member of] P. We say that the partitioned graph G does not contain H as induced subgraph or does not contain an induced H if no partitioned induced subgraph of G is isomorphic to H. Given a set of partitioned graphs H, G is defined to be H-free if G does not contain an induced H belonging to H. If H is a set with a single element H, we use H-free for short. We call tips of a diamond the vertices of degree two of a diamond.

In this section we study the structure of probe diamond-free graphs. As a first step towards proving the main theorem of this section, partitioned probe diamond-free graphs are characterized by forbidden partitioned induced subgraphs, through the following theorem. In addition, it gives a strategy to construct a diamond-free graph from a partitioned graph G = (P [union] N, E) by adding those edges whose endpoints are tips of a diamond and belong to N. Notice that the partitioned diamonds [H.sub.1], [H.sub.2], [H.sub.3] of Figure 1 are all the possible partitions of a diamond with at least one of its tips in P. This guarantees that, if G = (P [union] N, E) is a partitioned {[H.sub.1], [H.sub.2], [H.sub.3]}-free graph, every diamond in G can be eliminated by adding the missing edge (because both tips are in N). The more difficult part of the proof is that of proving that no new diamond is created during this procedure.

Theorem 4 Let G = (P [union] N,E) be a partitioned graph. Then, G is a partitioned probe diamond-free graph if and only if G does not contain any partitioned graph depicted in Figure 1 as induced subgraph. Moreover, a probe completion is given by adding the edge set F of non-edges of G whose endpoints belong to N and they both are tips of the same induced diamond of G.

Proof: It is easy to see that none of the partitioned graphs in Figure 1 is a partitioned probe diamond-free graph. Conversely, let G be a partitioned graph not containing any partitioned induced graph depicted in Fig. 1. Let F be the set of non-edges of G whose endpoints belong to N and they both are tips of the same induced diamond of G. It suffices to prove that the completion [G.sup.*] = (N [union] P,E [union] F) of G is diamond-free. The proof follows by contradiction and it is split into three cases. Suppose, by the way of contradiction, that [G.sup.*] is not diamond-free; i.e, there exists a vertex set {u,v,x,y} of [G.sup.*] inducing a diamond H = [G.sup.*] [{u, v, x, y}]. Notice that, since G does not contain [H.sub.1], [H.sub.2] and [H.sub.3] as partitioned induced subgraph, [G.sup.*] does not contain any induced diamond with at most one nonprobe vertex and thus F is well defined.

Case 1: Exactly two vertices of {u, v, x, y} are nonprobe vertices. Suppose, without loss of generality, that u, v [member of] N and x, y [member of] P. By definition of [G.sup.*], the tips of H cannot be u and v, so uv [member of] F. By symmetry, we only need to consider two cases: either u and x are the tips of H, or x and y are. First, suppose that u and x are the tips of H. Since uv [member of] F, there exist vertices [w.sub.1], [w.sub.2] [member of] P such that u and v are the tips of a diamond induced by {u, v, [w.sub.1], [w.sub.2]}. In particular, both [w.sub.1] and [w.sub.2] are different from x. Suppose without loss of generality that [w.sub.1] is different from y. If y were adjacent to [w.sub.1], then either {[w.sub.1], v, x, y} would induce [H.sub.3] or {[w.sub.1], u, x, y} would induce [H.sub.2] in G, a contradiction. So, in particular, [w.sub.2] is different from y and, by symmetry, nonadjacent to it. Therefore, {u, v, [w.sub.1], [w.sub.2], y} induces [H.sub.4] in G, leading to a contradiction. Suppose now that x and y are the tips of H. Again, consider the vertices [w.sub.1], [w.sub.2] [member of] P such that u and v are the tips of a diamond induced by {u, v, [w.sub.1], [w.sub.2]}. Since x and y are nonadjacent, we can suppose without loss of generality that [w.sub.1] is different from x and y. Suppose that [w.sub.1] is adjacent to either x or y. If [w.sub.1] is adjacent to x and nonadjacent to y, then {[w.sub.1], x, y, u, v} induces [H.sub.4] in G, a contradiction. Analogously, if [w.sub.1] is adjacent to y and nonadjacent to x, then {[w.sub.1], x, y, u, v} induces [H.sub.4] in G, a contradiction. Consequently, if [w.sub.1] were adjacent to either x or y, then [w.sub.1] would be adjacent to x and y. So, {[w.sub.1], x, y, v} would induce H3 in G, a contradiction. So, in particular, [w.sub.2] is different from x and y and, by symmetry, nonadjacent to them. Consequently, {[w.sub.1], [w.sub.2], u, v, x} induces [H.sub.4] in G, a contradiction. In what follows we can assume that [G.sup.*] does not contain any induced diamond with at most two vertices in N.

Case 2: Exactly three vertices of {u, v, x, y} are nonprobe vertices.

Suppose first that u, v, w G N induce a triangle in [G.sup.*]. We are going to prove it implies that there exits an edge rs [member of] E(G) whose endpoints belong to P and are complete to {u, v, w} (recall that a vertex v is said to be complete (anticomplete) to a set of vertices A, if v is adjacent (nonadjacent) to all the vertices of A). Suppose, by the way of contradiction, that there is no edge in G whose endpoints belong to P and are complete to {u, v, w}. Since uv G F, there exist two vertices [x.sub.uv], [y.sub.uv] belonging to P such that {u, v, [x.sub.uv] ,[y.sub.uv] } induces a diamond in G. Consequently, w is neither adjacent to [x.sub.uv] nor to [y.sub.uv], because otherwise, since there is no edge whose both endpoints are adjacent to u, v and w, {[x.sub.uv],[y.sub.uv],v,w} would induce a diamond in [G.sup.*] with exactly two nonprobe vertices, a contradiction. Thus, there exist two vertices [x.sub.vw] and [y.sub.vw], different from [x.sub.uv] and [y.sub.uv], such that they both are adjacent to v and w and nonadjacent to u. If [x.sub.vw] (resp. [y.sub.vw]) were adjacent to exactly one of {[x.sub.uv], [y.sub.uv]}, then {[x.sub.uv], [y.sub.uv], [x.sub.vw], v} (resp. {[x.sub.uv], [y.sub.uv],[y.sub.vw], v}) would induce H3 in G, a contradiction. Consequently, if [x.sub.vw] (resp. [y.sub.vw]) is adjacent to either [x.sub.uv] or [y.sub.uv], then it is adjacent to both of them and thus {[x.sub.uv], [y.sub.uv], [x.sub.vw], u} (resp. {[x.sub.uv], [y.sub.uv], [y.sub.vw], v}) induces H2 in G, a contradiction. So, [x.sub.vw] and [y.sub.vw] are nonadjacent to [x.sub.uv] and [y.sub.uv]. Analogously, there exist two vertices [x.sub.uw] and [y.sub.uw], both of them adjacent to u and v and different from [x.sub.uv], [x.sub.vw], [y.sub.uv] and [y.sub.vw]. Besides, [x.sub.uw] (resp. [y.sub.uw]) is nonadjacent to [x.sub.uv], [x.sub.vw], [y.sub.uv] and [y.sub.vw]. Consequently {[x.sub.uv], [x.sub.vw], [x.sub.uw], [y.sub.uv], [y.sub.vw], [y.sub.uw]} [union] {u, v, w} induces H5 in G, a contradiction. The contradiction arose from supposing that there is no edge in G whose endpoints are complete to {u, v, w}. So, there exists an edge rs [member of] E(G) whose endpoints belong to P and are complete to {u, v, w}. We will prove now that there is no probe vertex z adjacent to u and v and nonadjacent to w. Suppose, by way of contradiction, that there exists a vertex z g P such that z is adjacent to u and v and nonadjacent to w. If z were nonadjacent to either r or s, then either {r,u,v,z} or {s,u,v,z} would induce a diamond in [G.sup.*] with two nonprobe vertices, a contradiction. Therefore, z is adjacent to r and s. So, since z is nonadjacent to w, {r,s,w,z} induces [H.sub.2] in G, a contradiction. We have already proved that there is no induced diamond in [G.sup.*] with exactly three nonprobe vertices inducing a triangle. Now, suppose, by the way of contradiction, that {u, v, x, y} induces a diamond in [G.sup.*] with tips y and u, where u, v and y are nonprobe vertices and x is a probe vertex. Since u is adjacent to v in [G.sup.*] and v is adjacent to y in [G.sup.*], then there exists a probe vertex w such that w is adjacent to either u and v, or v and y. Notice that, since [G.sup.*] does not contain a diamond with at most two nonprobe vertices, w is adjacent to x. Consequently, w is adjacent to y and u, otherwise [G.sup.*] would contain a diamond with exactly two nonprobe vertices. Since u is nonadjacent to y in [G.sup.*], {u,w,x,y} induces a diamond with exactly two nonprobe vertices in [G.sup.*], a contradiction.

In what follows we can assume that there is no induced diamond in [G.sup.*] with at most three nonprobe vertices.

Case 3: [G.sup.*] contains a diamond with four nonprobe vertices. Finally, we will prove that there is no diamond in [G.sup.*] with all its edges belonging to F. Suppose, by way of contradiction, that there exist four vertices u, v, w and z belonging to N and inducing a diamond in [G.sup.*] with tips w and z. Since {u, v, w} and {u, v, z} induce triangles in [G.sup.*], we know that there exist two adjacent vertices x and y belonging to P such that {u, v, w} is complete to {x, y} and two probe adjacent vertices r and s complete to {u, v, z}.

Let e = xy and e' = rs. Notice that e and e' do not have a common endpoint, because otherwise there would be a vertex in [G.sup.*], say x, such that it is adjacent to every vertex in {u,v,w,z}. Consequently, {x,u,w,z} would induce a diamond in [G.sup.*] with exactly three nonprobe vertices, a contradiction. Besides, the vertices x and y (resp., r and s) are nonadjacent to z (resp., w). Therefore, {x,y} and {r,s} are anticomplete. Indeed, suppose, by the way of contradiction, they are not anticomplete; and also suppose, without loss of generality, that x is adjacent to r. So, since r is nonadjacent to w, {u,r,x,w} induces a diamond in [G.sup.*] with two nonprobe vertices, contradiction. Consequently, {u,v,x,y,r} induces the H4 in [G.sup.*], a contradiction.

4 Nonpartitioned probe diamond-free graphs

Let G and F be graphs. We will say that F is a subgraph of G with induced diamonds if F is isomorphic to a subgraph of G (not necessarily induced) in such a way that all the induced diamonds of F induce also diamonds in G, i.e., the tips of a diamond in F are also not adjacent in G.

Before presenting the characterization by forbidden induced subgraphs for probe diamond-free graphs, we will present the following technical lemma whose proof will be postponed up to [section] 4.1.

Lemma 5 Let G be a {[F.sub.1], [F.sub.2], [F.sub.3], [F.sub.4], [F.sub.6]}-free graph. If G contains either S or Ti as a subgraph with induced diamonds, then G contains one of the graphs depicted in Figure 3 as induced subgraph.

Theorem 6 Let G be a graph. G is probe diamond-free if and only if G does not contain any graph depicted in Figures 2 and 3 as induced subgraph. Moreover, a suitable probe partition is obtained by defining N as the set of vertices of G that are tips of an induced diamond in G and P as V \ N and a probe completion is given by adding the edge set F of non-edges of G whose endpoints are tips of the same induced diamond.

Proof: First notice that in the graphs [F.sub.1], [F.sub.2], [F.sub.4], [F.sub.6], S, [T.sub.1], ..., [T.sub.10] the set of tips of induced diamonds is not a stable set. In F3 and F5 the set of tips of induced diamonds forms a maximal stable set, and thus any probe partition of G having the tips of induced diamonds as nonprobe vertices would contain a partitioned induced subgraph isomorphic to H4 and H5, respectively.

Conversely, let G be a graph not containing any graph depicted in Figures 2 and 3 as induced subgraph. Let N be the set of vertices of G that are tips of an induced diamond in G and P = V \ N. Let F be a set of non-edges of G whose endpoints are tips of the same induced diamond.

First, we are going to prove that N is a stable set of G. Suppose, by the way of contradiction, that there exist two adjacent vertices u and a belonging to N. Suppose that u belongs to a diamond [D.sub.1] induced by the vertices {u, v,w,x} whose other tip is x, and a belongs to another diamond [D.sub.2] induced by {a, b, c, d} whose other tip is d. If V ([D.sub.1]) does not intersect V ([D.sub.2]), then [D.sub.1] [union] [D.sub.2] would induce a subgraph in G that contains [T.sub.1] as subgraph with induced diamonds [D.sub.1] and [D.sub.2]. By Lemma 5, since G does not contain [F.sub.i] for i = 1,..., 4,6 as induced subgraph, G contains one of the graphs depicted in Figure 3 as induced subgraph, a contradiction. Hence, we can assume that the diamonds [D.sub.1] and [D.sub.2] have at least one vertex in common.

If they have exactly one vertex in common, it should have the same number of neighbors in both diamonds, because otherwise [D.sub.1] [union] [D.sub.2] would induce a subgraph in G that contains S as subgraph with induced diamonds [D.sub.1] and [D.sub.2]. So we are left with two possibilities up to symmetries and considering the fact that u and a are different and adjacent: either d = x or b = w.

First, suppose that d = x and {u, v, w} [intersection] {a, b, c} = 0. Since G is [F.sub.6]-free, there exists at least one edge different from au such that one of its endpoints belongs to {u, v, w, x} and the other one belongs to {a, b, c, d}. By symmetry, we can assume that it is either wa or wb. Suppose that w is adjacent to a. Since G is [F.sub.2]-free, v is adjacent to a. Consequently, {a, d, u, v, w} induces [F.sub.1], a contradiction. Therefore, we can assume that a is nonadjacent to w. By symmetry, we can also assume that v is nonadjacent to a and u is nonadjacent to b and c. Suppose now that w is adjacent to b. Since G is [F.sub.2]-free and w is nonadjacent to a, w is adjacent to c. So, {a, b, c, d, w} induces [F.sub.1], a contradiction. Therefore, w is nonadjacent to b. Symmetrically, w is nonadjacent to c and v is nonadjacent to b and nonadjacent to c. This leads to a contradiction because G is F6-free.

Suppose now that b = w and {u, v, x} [intersection] {a, c, d} = [empty set]. Since G is [F.sub.2]-free, a is adjacent to either v or x. If a were adjacent to v, since G is [F.sub.1] -free, a is would be adjacent to x. On the other hand, if a were adjacent to x, since G is F4-free, then a would be adjacent to v. Consequently, a is adjacent to v and x. By symmetry, u is adjacent to c and d. Since the vertex set {a, b, c, d, x} does not induce [F.sub.2], [F.sub.4] nor [F.sub.1], x is adjacent to d and c. Consequently, {a, b, u, x, d} induces [F.sub.4], a contradiction. Hence, we can assume that [D.sub.1] and [D.sub.2] have at least two vertices in common.

These two vertices cannot be nonadjacent because a and u are different and adjacent. So at most one vertex on each diamond is a tip. Suppose that none of them is a tip, and with no loss of generality b = w and c = v. Since G is [F.sub.1]-free, a is adjacent to x and u is adjacent to d. But then {a, b, u, x, d} induces either [F.sub.2] or [F.sub.4], a contradiction.

Suppose now that exactly one common vertex is a tip in one of the diamonds. Up to symmetries, we have to consider the cases: a = v, b = w and d = v, b = w. In the first case, since the vertex set {a, b, c, d, x} does not induce [F.sub.2], [F.sub.4] nor [F.sub.1], x is adjacent to d and c. Analogously, u is adjacent to d and c. Consequently, {a, b, u, x, d} induces [F.sub.4], a contradiction. In the second case, {a, b, u, x, d} induces either [F.sub.2] or [F.sub.4], a contradiction.

Finally, suppose that there is one tip of each diamond in the set of common vertices. Up to symmetries, we have to consider the cases: a = w, b = u; a = w, b = x; d = w, b = x and d = x, b = w.

Suppose first that a = w and b = u. Since {a, b, c, d, v} does not induce [F.sub.2], [F.sub.4] nor [F.sub.1], v is adjacent to d and c. But then {a, b, v, x, d} induces either [F.sub.2] or [F.sub.4], a contradiction. Suppose next that a = w and b = x. Again, since {a, b, c, d, v} does not induce F2, F4 nor [F.sub.1], v is adjacent to d and c, and now {a, b, u, d, v} induces either F2 or F4, a contradiction. Suppose now that d = w and b = x. Once more, since {a, b, c, d, v} does not induce F2, F4 nor [F.sub.1], v is adjacent to a and c, and so {a, b, u, d, v} induces [F.sub.4], a contradiction. Finally, suppose that d = x and b = w. Since {a, b, c, d, v} does not induce [F.sub.1], [F.sub.2] nor [F.sub.4], v is adjacent to a and c. By symmetry, c is adjacent to u. But then {a, u, v, c, d} induces [F.sub.1], a contradiction.

Hence, we can assume that [D.sub.1] and [D.sub.2] have exactly three vertices in common. These vertices cannot induce a 2-edge path, because in that case either u = a or u = d, a contradiction with the assumption that a and u are different and adjacent. So, [D.sub.1] and [D.sub.2] share a triangle, and we have to consider two cases, up to symmetries: either u = b or u G V([D.sub.2]) \ V([D.sub.1]). In the first case, x should be in V([D.sub.2]) \ V([D.sub.1]), so it is nonadjacent to b and, without loss of generality, it is adjacent to c and d. Therefore, {a, b, c, d, x} induces either [F.sub.2] or [F.sub.4], depending on the existence of the edge ax, which contradicts our assumptions. In the second case, without loss of generality, either x = b or x = d, so u is adjacent to c and to at most one of {b, d}. In that case, {a, b, c, d, u} induces either [F.sub.1], [F.sub.2] or [F.sub.4], depending on the existence of one ore none of the edges {ub, ud}, a contradiction again.

Finally, it remains to prove that the completion [G.sup.*] = (V, E [union] F) is diamond-free. By Theorem 4, it suffices to prove that the partitioned graph G = (N [union] P, E) with probe partition (N, P) does not contain any of the partitioned graphs depicted in Figure 3. By the construction of the partition (N, P), G = (NU P, E) does not contain [H.sub.1], [H.sub.2] and [H.sub.3]. Finally, since G is {[F.sub.3], [F.sub.5]}-free, the partitioned graph G = (N [union] P, E) does not contain the partitioned subgraphs [H.sub.4] and [H.sub.5].

4.1 Proof of Lemma 5

Proof of Lemma 5: In what follows, we mean by "S (resp. Ti) is a subgraph of G", S (resp. [T.sub.1]) is a subgraph of G with induced diamonds. Let G be a {[F.sub.1], [F.sub.2], [F.sub.3], [F.sub.4], [F.sub.6]}-free graph. We will prove the lemma by contradiction. Suppose that G does not contain any graph depicted in Fig. 3 as induced subgraph. We are going to split the proof into two cases.

Case 1: G contains a subgraph H isomorphic to S where the diamonds of S are induced in G. By our assumption, H is not an induced subgraph. Suppose that the vertex set of the subgraph H is labeled by the set {a, b, c, d, f, g}, where the set {a, b, c, d} induces a diamond whose tips are a and d, and {b, e, f, g} induces a diamond whose tips are b and g. Since H is not induced, there is at least one edge in E(G) \ E(H) whose endpoints belong to {a, b, c, d, e, f, g}. Since the diamonds are induced in G, the edge is neither ad nor bg.

By the symmetry of the graph, we may assume that at least one of ae, ag, ce and cg does exist. First, suppose that a is adjacent to e. So, a is either adjacent to f or adjacent to g because, otherwise, {a, b, e, f, g} would induce [F.sub.2]. On the one hand, if a were adjacent to g and nonadjacent to f, {a, b, e, f, g} would induce [F.sub.4]. On the other hand, if a were adjacent to f and nonadjacent to g, {a, b, e, f, g} would induce [F.sub.1]. Consequently, since G is {[F.sub.1], [F.sub.4]}-free, a is adjacent to f and g. By symmetry, where {a, b, c, d} plays the role of {b, e, f, g} and e (resp. f) plays the role of a, we conclude that both e and f are adjacent to c and d. Now, by symmetry, where {b, e, f, g} is the diamond and d plays the role of a, it follows that d is adjacent to g. If c were nonadjacent to g, {b, c, e, f, g} would induce [F.sub.1]. Therefore, c is adjacent to g. Consequently, {a, b, c, d, g} induces F4, a contradiction. This contradiction arose from supposing that a is adjacent to e. So, in what follows, we can assume that a is nonadjacent to e. Symmetrically, we can also assume that a is nonadjacent to f and d is nonadjacent to f and e.

Suppose now that a is adjacent to g. Then, since a is nonadjacent to e and f, {a, b, e, f, g} induces [F.sub.3], a contradiction. This contradiction arose from supposing that a is adjacent to g. Therefore, we can assume that a is nonadjacent to g. By symmetry, we can also assume that d is nonadjacent to g.

Now, suppose that c is adjacent to e. Since b is nonadjacent to g, c is adjacent to either f or g. On the one hand, if c were adjacent to g and nonadjacent to f, {c, b, e, f, g} would induce F4. On the other hand, if c were adjacent to f and nonadjacent to g, {c, b, e, f, g} would induce [F.sub.1]. Consequently, c is adjacent to f and g. Since b is nonadjacent to g and a is neither adjacent to g nor to f, {a, b, c, f, g} induces [F.sub.2]. So, we can assume that c is nonadjacent to e. By symmetry, c can be also assumed not to be adjacent to f.

Finally, suppose that c is adjacent to g. Since c is neither adjacent to e nor to f, {b, c, e, f, g} induces [F.sub.3], a contradiction.

In what follows, we can assume that G contains no subgraph isomorphic to S with induced diamonds.

Case 2: G contains a subgraph H isomorphic to [T.sub.1] where the diamonds of [T.sub.1] are induced in G.

By our assumptions, H is not an induced subgraph. Suppose that the vertex set of the subgraph H is labeled by the set {a, b, c, d, r, s, t, u}, where {a, b, c, d} induces a diamond whose tips are a and d, {r, s, t, u} induces a diamond whose tips are r and u, and a is adjacent to r. Since H is not induced, there is at least one edge in E(G) \ E(H) whose endpoints belong to {a, b, c, d, r, s, t, u}. Since the diamonds are induced in G, the edge is neither ad nor ru.

By the symmetry of the graph, we may assume that at least one of as, bs, au, bu and du does exist. First, suppose that a is adjacent to s. Since G is [F.sub.2]-free and r is nonadjacent to u, a is adjacent to either u or t. On the one hand, if a were adjacent to u and nonadjacent to t, {a, r, s, t, u} would induce [F.sub.4]. On the other hand, if a were adjacent to t and nonadjacent to u, {a, r, s, t, u} would induce [F.sub.1]. Therefore, a is adjacent to t and u. Consequently, G contains the graph S as a subgraph with induced diamonds, a contradiction. The contradiction arose from supposing that a is adjacent to s and thus a is nonadjacent to s and symmetrically a is nonadjacent to t. Besides, by symmetry, r is nonadjacent to b and c. Consequently, a is nonadjacent to u, because otherwise {a, r, s, t, u} would induce [F.sub.3]. Symmetrically, r is nonadjacent to d.

Suppose now that b is adjacent to s. Notice that, if b were adjacent to t, {a, b, r, s, t} would induce [F.sub.3]. So, b is nonadjacent to t and, by symmetry, s is nonadjacent to c. Therefore, if b were adjacent to u, since b is nonadjacent to t and r, then {b, r, s, t, u} would induce [F.sub.2], a contradiction. Consequently, b is nonadjacent to u and, by symmetry, s is nonadjacent to d. Analogously, if c is adjacent to t, then ct is the only edge in E(G) \ E(H) having an endpoint in {c, t}. Thus G contains either an induced [T.sub.5] or and induced [T.sub.6], depending on the existence of the edge du. So, we can assume that c is nonadjacent to t. Besides, c is nonadjacent to s because otherwise {a, b, c, r, s} would induce [F.sub.3]. Suppose now that c is adjacent to u. Since G is {[F.sub.2], [T.sub.8]}-free, d is nonadjacent to t and u. So, {a, b, c, d, r, s, t, u} induces [T.sub.4], a contradiction. Hence, we can assume that c is nonadjacent to u. Symmetrically, t is nonadjacent to d. Finally, if d were adjacent to u, {a, b, c, d, r, s, t, u} would induce [T.sub.10], a contradiction. Therefore, since G is [T.sub.2]-free, from now on, we can assume that b is nonadjacent to s. Symmetrically, we can also assume that b is nonadjacent to t, and c is nonadjacent to s and t.

Suppose that b is adjacent to u. If d were adjacent to u, then u would be adjacent to c. Because, otherwise {a, b, c, d, u} would induce [F.sub.2]. Consequently, {a, b, c, d, u} induces [F.sub.1] a contradiction. So, if b is adjacent to u, then u is nonadjacent to d. Symmetrically, if c is adjacent to u, then d is nonadjacent to u. In addition, by symmetry, if s (resp. t) is adjacent to d, then d is nonadjacent to u. Suppose now that c is adjacent to u. Since G is [F.sub.6]-free, either s is adjacent to d or t is adjacent to d. If s (resp. t) were adjacent to d, then {b, c, d, u, s} (resp. {b, c, d, u, t}) would induce [F.sub.3], a contradiction. The contradiction arose from supposing that c is adjacent to u. Therefore, we can assume that if b is adjacent to u, then c is nonadjacent to u. Symmetrically, if s is adjacent to d, then t is nonadjacent to d. Consequently, either exactly one of {s, t} is adjacent to d and thus {a, b, c, d, r, s, t, u} induces [T.sub.9], or none of them are and thus {a, b, c, d, r, s, t, u} induces [T.sub.7], reaching in both cases a contradiction. Therefore, we can assume that b and c are nonadjacent to u, and s and t are nonadjacent to d.

Finally, since G is Ti-free, d must be adjacent to u. Consequently, {a, b, c, d, r, s, t, u} induces [T.sub.3], a contradiction. This finishes the proof.

Next, the characterization for probe diamond-free graphs is used to characterize probe block graphs. Partitioned and nonpartitioned probe block graphs were characterized by forbidden induced subgraphs in [15]. Earlier and independently, probe block graphs were characterized by forbidden induced subgraphs in [11]. We will present a new characterization for this class, which establishes that probe block graphs are exactly the chordal probe diamond-free graphs. Specifically speaking, Theorem 4 and Theorem 6 are generalizations of those characterizations by forbidden induced subgraphs for probe block graphs presented in [15].

Lemma 7 Let G be a probe block graph. Then, G is chordal.

Proof: Let G = (V, E) be a probe block graph. Suppose, by the way of contradiction, that G contains an induced cycle H of length at least four. Since the graph induced by V(H) in any probe block completion [G.sup.*] of G will be connected and will not have a cut-vertex, it should be complete. Since in G every vertex of H has a non-neighbor in H, all the vertices of H have to be nonprobe vertices, a contradiction because they do not form a stable set.

Clearly a probe block graph is probe diamond-free and we have already proved that it is also chordal. The following lemma proves that the graph obtained by adding all the edges to a chordal probe diamond-free graph whose endpoints are tips of a diamond remains chordal. Consequently, by Theorem 6, every graph which is chordal and probe diamond-free is probe block.

Lemma 8 Let G = (V, E) be a connected chordal probe diamond-free graph and F be the set of nonedges of G whose endpoints are tips of some diamond in G. Then, [G.sup.*] = (V, E [union] F) is chordal.

Proof: Throughout the proof, index sums should be considered modulo k. Let F be the subset of edges of [G.sup.*] defined as in the lemma. Suppose, by way of contradiction, that [G.sup.*] = (V, E [union] F) contains an induced cycle H = [v.sub.1], ..., [v.sub.k], [v.sub.1] for k [greater than or equal to] 4 as induced subgraph. Since G is chordal, [v.sub.i][v.sub.i+1] [member of] F for some i = 1,..., k. Assume that the cycle H contains the minimum number of nonprobe vertices among all the induced cycles contained in [G.sup.*]. By construction, there exists a vertex [w.sub.1] [member of] P adjacent to [v.sub.i] and [v.sub.i+1]. By minimality on the number of nonprobe vertices of H and since [G.sup.*] is diamond-free, [w.sub.1] is anticomplete to V(H) - {[v.sub.i], [v.sub.i+1]} in [G.sup.*]. If E(H) n F = {[v.sub.i][v.sub.i+1]}, then V(H) [union] {[w.sub.1]} would induce a cycle in G, a contradiction. Thus, we can assume that there exists an edge [v.sub.j] [v.sub.j+1] [member of] F with i = j such that [v.sub.j] [v.sub.j+1] [member of] F. Therefore, there exists a vertex [w.sub.2] = [w.sub.1] belonging to P and adjacent to [v.sub.j] and [v.sub.j+1] which is also anticomplete to E(H) - {vjvj+1}. In addition, by the minimality of the number of nonprobe vertices in H, it follows that [w.sub.1][w.sub.2] [member of] E(G). Again, if there were no other edges belonging to H in F, G would contain an induced cycle greater than 4, a contradiction. Repeating this procedure, if were necessary, for any edge of H belonging to F, we conclude that G is not chordal, a contradiction again.

By combining Theorem 6, Lemma 7 and Lemma 8, it follows the characterization for probe block graphs. This characterization points out the relationship between the class of probe block graphs and

Ptolemaic graphs. Indeed, the corollary below shows that probe block graphs are a subclass of Ptolemaic graphs, and they are exactly those probe diamond-free graph that are chordal.

Corollary 9 Let G be a connected graph. The following statements are equivalent:

1. G is a probe block graph.

2. G is chordal and probe diamond-free.

3. G is Ptolemaic and {[F.sub.1], S, [T.sub.1]}-free.

Proof: 1. [right arrow] 2. Since block graphs are chordal and diamond-free, the class of probe block graphs is contained in the class of probe diamond-free graphs. On the other hand, by Lemma 7, it follows that the class of probe block graphs is contained in the class of chordal graphs.

2. [right arrow] 1. It is a consequence of Theorem 6 and Lemma 8.

2. [right arrow] 3. Let G be a probe diamond-free and chordal graph. By Theorem 6, G is, in particular, {[F.sub.1], S, [T.sub.1]}-free and F2-free. Consequently, since G is chordal, G is {[F.sub.1], S, [T.sub.1]}-free and Ptolemaic.

3. [right arrow] 2. It is a consequence of Theorem 6, since the only chordal graphs in Figures 2 and 3 are [F.sub.1] [F.sub.2], S and [T.sub.1].

5 Further remarks

From Theorem 4, Lemma 7 and Lemma 8 it follows that partitioned probe block graphs are exactly the class of partitioned chordal {[H.sub.1], [H.sub.2], [H.sub.3]}-free graphs (see also [15]). Let G be a class of graphs. The G-width of a graph G is the minimum number k of independent sets [N.sub.1], ..., [N.sub.k] in G such that there exists an embedding of a graph H [member of] G on G such that for every edge e = (x, y) of H which is not an edge of G there exists an i with x, y [member of] N. In the case that k = 1, G is a probe G-graph. In [5], it is presented a polynomial-time algorithm to recognize whether a given graph has B-width at most k, being B the class of block graphs. An interesting open problem is to try to characterize, by forbidden induced subgraphs, those graphs with B-width at most k, for k [greater than or equal to] 2.

References

[1] D. Bayer, V. B. Le, and H. N. de Ridder. Probe threshold and probe trivially perfect graphs. Theoretical Computer Science, 410(47-49):4812-4822, 2009.

[2] A. Berry, M. C. Golumbic, and M. Lipshteyn. Recognizing chordal probe graphs and cycle bicolorable graphs. SIAM Journal on Discrete Mathematics, 21(3):573-591, 2007.

[3] D. E. Brown and L. J. Langley. Probe interval orders. In Brams, Gehrlein, and Roberts, editors, The Mathematics of Preference Choice and Order, Essays in Honor of P C. Fishburn, pages 313-322. Springer Berlin Heidelberg, 2009.

[4] D. B. Chandler, M.-S. Chang, T. Kloks, J. Liu, and S.-L. Peng. Recognition of probe cographs and partitioned probe distance hereditary graphs. In S.-W. Cheng and C. K. Poon, editors, Proceedings of the Second International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, Hong Kong, China, June 20-22, 2006, volume 4041 of Lecture Notes in Computer Science, pages 267-278. Springer, 2006.

[5] M.-S. Chang, L.-J. Hung, T. Kloks, and S.-L. Peng. Block-graph width. Theoretical Computer Science, 412(23):2496-2502, 2011.

[6] M.-S. Chang, L.-J. Hung, and P. Rossmanith. Recognition of probe distance-hereditary graphs. Discrete Applied Mathematics, 161(3):336-348, 2013.

[7] J. L. G. J. Chang, A. J. J. Kloks and S.-L. Peng. The pigs full monty - a floor show of minimal separators, in stacs 2005, proceedings. volume 3404 of Lecture Notes in Computer Science, pages 521-532. Springer, 2005.

[8] M. C. Golumbic. Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. Elsevier, Amsterdam, second edition, 2004.

[9] M. C. Golumbic and M. Lipshteyn. Chordal probe graphs. Discrete Applied Mathematics, 143(13):221-237, 2004.

[10] M. C. Golumbic, F. Maffray, and G. Morel. A characterization of chain probe graphs. Annals of Operations Research, 188:175-183, 2011.

[11] L. N. Grippo. Structural characterizations of intersection graphs. PhD thesis, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina, 2011.

[12] P. Hell and J. Huang. Interval bigraphs and circular arc graphs. Journal of Graph Theory, 46(4):313-327, 2004.

[13] J. L. Johnson and J. P. Spinrad, editors. A polynomial time recognition algorithm for probe interval graphs, In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001). SIAM, 2001.

[14] D. C. Kay and G. Chartrand. A characterization of certain Ptolemaic graphs. Canadian Journal of Mathematics, 17:342-346, 1965.

[15] V. Le and S.-L. Peng. Characterizing and recognizing probe block graphs. In R.-S. Chang, L. C. Jain, and S.-L. Peng, editors, Proceedings of the Workshop on Algorithms, Bioinformatics, and Computation Theory of the International Computer Symposium, ICS 2012, Hualien, Taiwan, December 12-14, 2012, volume 20 of Smart Innovation, Systems and Technologies, pages 7-13. Springer Berlin Heidelberg, 2013.

[16] R. M. McConnell and J. Spinrad. Construction of probe interval models. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA., pages 866-875, 2002.

[17] J. Spinrad. Circular-arc graphs with clique cover number two. J. Comb. Theory, Ser. B, 44(3):300-306, 1988.

[18] D. B. West. Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ, 1996.

[19] P. Zhang, E. Schon, S. Fischer, E. C. and J. Weiss, S. Kistler, and P. Bourne. An algorithm based on graph theory for ghe assembly of contigs in physical mapping of DNA. Computer Applications in the Biosciences, 10(3):309-317, 1994.

Flavia Bonomo (1,4) * Celina M. H. de Figueiredo (2)([dagger]) Guillermo Duran (1,5,6)([double dagger]) Luciano N. Grippo (7)([section]) Martin D. Safe (7)([paragraph]) Jayme L. Szwarcfiter (2,3)([parallel])

(1) CONICET, Argentina

(2) COPPE, Universidade Federal do Rio de Janeiro, Brazil

(3) NCE, Universidade Federal do Rio de Janeiro, Brazil

(4) Depto. de Computacion, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina

(5) Depto. de Matematica and Instituto de Calculo, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina

(6) Depto. de Ingenieria Industrial, FCFM, Universidad de Chile, Santiago, Chile

(7) Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina

* Email: fbonomo@dc.uba.ar. Partially supported by ANPCyT PICT 2012-1324, UBACyT Grant 20020130100808BA, and CONICET PIP 112-201201-00450C0 (Argentina).

([dagger]) Email: celina@cos.ufrj.br. Partially supported by the Brazilian research agencies FAPERJ and CNPq

([double dagger]) Email: gduran@dm.uba.ar. Partially supported by FONDECyT Grant 1140787 and Millennium Science Institute "Complex Engineering Systems" (Chile), and ANPCyT PICT 2012-1324, UBACyT Grant 20020130100808BA, and CONICET PIP 112-201201-00450C0 (Argentina)

([section]) Email: lgrippo@ungs.edu.ar. Partially supported by ANPCyT PICT 2012-1324, UBACyT Grant 20020130100808BA, and CONICET PIP 112-201201-00450C0 (Argentina)

([paragraph]) Email: msafe@ungs.edu.ar. Partially supported by ANPCyT PICT 2012-1324, UBACyT Grant 20020130100808BA, and CONICET PIP 112-201201-00450CO (Argentina)

([parallel]) Email: jayme@nce.ufrj.br. Partially supported by the Brazilian research agencies CAPES and CNPq.

received 6th Jan. 2014, accepted 14th Mar. 2015.
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Bonomo, Flavia; de Figueiredo, Celina M.H.; Duran, Guillermo; Grippo, Luciano N.; Safe, Martin D.; S
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Jan 1, 2015
Words:9121
Previous Article:p-box: a new graph model.
Next Article:A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters