Graph Operations on Clique-Width Bounded Graphs Frank Gurski∗ February 1, 2008 7 0 0 Abstract 2 Inthis paperwe surveythe behaviorofvariousgraphoperationsonthe graphparam- n eters clique-width and NLC-width. We give upper and lower bounds for the clique-width a and NLC-width of the modified graphs in terms of the clique-width and NLC-width of J the involved graphs. Therefor we consider the binary graph operations join, co-join, 9 sum, difference, products, corona, substitution, and 1-sum, and the unary graph opera- 2 tions quotient, subgraph, edge complement, bipartite edge complement, power of graphs, ] switching, local complementation, edge addition, edge subdivision, vertex identification, S and vertex addition. D s. Keywords: clique-width, NLC-width, graph operations c [ 1 Introduction 1 v 5 The clique-width of a graph is defined by a composition mechanism for vertex-labeled graphs 8 [CO00]. The operations are the vertex disjoint union, the addition of edges between vertices 1 1 controlled by a label pair, and the relabeling of vertices. The clique-width of a graph G is the 0 minimum number of labels needed to define it. The NLC-width of a graph is defined by a 7 composition mechanismsimilar tothatforclique-width[Wan94]. Every graphof clique-width 0 / at most k has NLC-width at most k and every graph of NLC-width at most k has clique- s c width at most 2k [Joh98]. The only essential difference between the composition mechanisms : v of clique-width bounded graphs and NLC-width bounded graphs is the addition of edges. In i an NLC-width composition the addition of edges is combined with the union operation. This X union operation applied to two graphs G and J is controlled by a set S of label pairs such r a that for every pair (a,b) ∈ S all vertices of G labeled by a will be connected with all vertices of J labeled by b. Both concepts are useful, because it is sometimes much more comfortable to useNLC-widthexpressions instead of clique-width expressionsand vice versa, respectively. Clique-width and NLC-width bounded graphs are particularly interesting from an algo- rithmicpointof view. Alot of NP-complete graph problemscan besolved in polynomialtime forgraphsofboundedclique-width. Forexample, allgraphpropertieswhichareexpressiblein monadicsecondorderlogicwithquantificationsover vertices andvertexsets(MSO -logic) are 1 decidableinlineartimeonclique-widthboundedgraphs[CMR00]. Furthermore,therearealso alotofNP-completegraphproblemswhicharenotexpressibleinMSO -logiclikeHamiltonic- 1 ity, partition problems, and bounded degree subgraph problems but which can also be solved in polynomial time on clique-width bounded graphs [Wan94, EGW01, KR03, Tod03, GW06]. ∗ Heinrich-Heine Universit¨at Du¨sseldorf, Institute of Computer Science, D-40225 Du¨sseldorf, Germany E- Mail: [email protected] 1 Distance hereditary graphs have clique-width at most 3 [GR00]. The set of all graphs of clique-width at most 2 or NLC-width 1 is the set of all labeled co-graphs. Brandst¨adt et al. have analyzed the clique-width of graphs defined by forbidden one-vertex extensions of P 4 [BDLM02]. The clique-width and NLC-width of permutation graphs, interval graphs, grids andplanargraphsisnotbounded[GR00]. Anarbitrarygraphwithnverticeshasclique-width at most n−r, if 2r < n−r, and NLC-width at most ⌈n⌉ [Joh98]. Every graph of tree-width1 2 at most k has clique-width at most 3·2k−1 [CR01]. In [GW00], it is shown that every graph of clique-width or NLC-width k which does not contain the complete bipartite graph K for n,n some n > 1 as a subgraph has tree-width at most 3k(n−1)−1. The recognition problem for graphs of clique-width or NLC-width at most k is still open for k ≥ 4 and k ≥ 3, respectively. Clique-width of at most 3 is decidable in polynomial time [CHL+00]. NLC-width of at most 2 is decidable in polynomial time [Joh00]. Clique-width of at most 2 and NLC-width 1 is decidable in linear time [CPS85]. Minimizing NLC-width andminimizing clique-width is NP- complete [GW05,GW07,FRRS05,FRRS06]. Theclique-width oftree-width boundedgraphs is computable in linear time [EGW03]. Graph operation can be used to characterize sets of graphs by forbidden graphs. Graphs of bounded tree-width, which are less powerful than graphs of bounded clique-width, are closed undertaking minors and characterized by a finiteset of forbiddenminors[RS85]. Oum and Seymour introduced in [OS06] the rank-width of graphs, which is defined independently of vertex labels, but which is shown to be as powerful as clique-width. In [Oum05] is is shown that rank-width boundedgraphs are closed under taking local complementation which leads to a characterization of graphs of rank-width at most k by forbidden vertex-minors (i.e. taking induced subgraphs and local complementations). It is still open if there exists a graph operation that does not increase the NLC-with or clique-width and which can be used to characterize graphs of NLC-with at most k or clique-width at most k by a set of forbidden subgraphs. Thus we want to study the behavior of graph operations on the NLC-width and clique-width of graphs more precisely. Further we know from [OS06] that we can compute a clique-width f(k)-expression for every given graph in polynomial time. Since f(k) can be exponential in the clique-width of the given graph and nearly all algorithms for hard graph problems on clique-width bounded graphs have a running time exponential in the number of used labels, it is important to find expressions using few labels. In order to deal with this problem, our survey shows for various graph operations f how to construct an expression for graph f(G) from an expression for some graph G. This paper is organized as follows. In Section 2, we recall the definitions of clique-width and NLC-width. In Section 3, we give an overview on the behavior of the binary operations join, co-join, sum, difference, products, corona, substitution, and 1-sum on the clique-width and NLC-width of a given graph. In Section 4, we consider the latter problem for the unary graph operations quotient, subgraph, edge complement, bipartite edge complement, power of graphs, switching, local complementation, edge addition, edge subdivision, vertex identi- fication, and vertex addition. In Section 5, we show how theses results can be used to give upperboundson theclique-width andNLC-widthof graphclasses andwecomparetheshown bounds within a table. 1See [Bod98]for definition and an overview on tree-width. 2 2 Preliminaries Let[k] := {1,...,k}bethesetofallintegers between 1andk. Weworkwithfiniteundirected labeledgraphsG = (V ,E ,lab ),whereV isafinitesetofverticeslabeledbysomemapping G G G G lab : V → [k] and E ⊆ {{u,v} | u,v ∈ V , u 6= v} is a finite set of edges. A labeled G G G G graph J = (V ,E ,lab ) is a subgraph of G if V ⊆ V , E ⊆ E and lab (u) = lab (u) for J J J J G J G J G all u ∈ V . J is an induced subgraph of G if additionally E = {{u,v} ∈ E | u,v ∈ V }. J J G J The labeled graph consisting of a single vertex labeled by a ∈ [k] is denoted by • . For a a vertex v ∈ V we denote by N (v) the set of all vertices which are adjacent to v in G, i.e. G G N (v) = {w ∈ V | {v,w} ∈ E }. N (v) is called the set of all neighbors of v in G or G G G G neighborhood of v in G. The degree of a vertex v ∈ V , denoted by deg (x), is the number of G G neighbors of vertex v in G, i.e. deg (v) = |N (v)|. G G Thenotionofclique-widthforlabeledgraphsisdefinedbyCourcelleandOlariuin[CO00]. Definition 2.1 (CW , clique-width, [CO00]) Let k be some positive integer. The class k CW of labeled graphs is recursively defined as follows. k 1. The single vertex graph • for some a∈ [k] is in CW . a k 2. Let G = (V ,E ,lab ) ∈ CW and J = (V ,E ,lab ) ∈ CW be two vertex disjoint G G G k J J J k labeled graphs, then G⊕J := (V′,E′,lab′) defined by V′ := V ∪V , E′ := E ∪E , G J G J and lab (u) if u ∈V lab′(u) := G G , ∀u∈ V′ (cid:26) labJ(u) if u ∈VJ is in CW . k 3. Let a,b ∈ [k] be two distinct integers and G = (V ,E ,lab ) ∈CW be a labeled graph, G G G k then (a) ρ (G) := (V ,E ,lab′) defined by a→b G G lab (u) if lab (u) 6=a lab′(u) := G G , ∀u∈ V G (cid:26) b if labG(u) =a is in CW and k (b) η (G) := (V ,E′,lab ) defined by a,b G G E′ := E ∪{{u,v} |u,v ∈ V , u6= v, lab(u) = a, lab(v) = b} G G is in CW . k The clique-width of a labeled graph G is the least integer k such that G∈ CW . k The notion of NLC-width2 of labeled graphs is defined by Wanke in [Wan94]. Definition 2.2 (NLC , NLC-width, [Wan94]) Let k be some positive integer. The class k NLC of labeled graphs is recursively defined as follows. k 2The abbreviation NLC results from the node label controlled embedding mechanism originally defined for graph grammars. 3 1. The single vertex graph • for some a∈ [k] is in NLC . a k 2. Let G = (V ,E ,lab ) ∈ NLC and J = (V ,E ,lab ) ∈ NLC be two vertex disjoint G G G k J J J k labeled graphs and S ⊆ [k]2 be a relation, then G × J := (V′,E′,lab′) defined by S V′ := V ∪V , G J E′ := E ∪E ∪{{u,v} | u∈ V , v ∈ V , (lab (u),lab (v)) ∈ S}, G J G J G J and lab (u) if u ∈V lab′(u) := G G , ∀u∈ V′ (cid:26) labJ(u) if u ∈VJ is in NLC . k 3. Let G = (V ,E ,lab ) ∈ NLC and R :[k] → [k] be a function, then ◦ (G) := (V ,E , G G G k R G G lab′) defined by lab′(u) := R(lab (u)), ∀u∈ V is in NLC . G G k The NLC-width of a labeled graph G is the least integer k such that G∈ NLC . k An expression X builtwith the operations • ,⊕,ρ ,η for integers a,b ∈[k] according a a→b a,b to Definition 2.1 is called a clique-width k-expression. An expression X built with the oper- ations • ,× ,◦ for a ∈ [k], S ⊆ [k]2, and R : [k] → [k] according to Definition 2.2 is called a S R an NLC-width k-expression. The graph defined by expression X is denoted by val(X). Every clique-width k-expression can be transformed into an equivalent NLC-width k- expression and every NLC-width k-expression can be transformed into an equivalent clique- width 2k-expression [Joh98]. Example 2.3 1. The following two clique-width expressions X and X define the labeled graphs G and 1 2 1 G in Figure 1. 2 X = η ((ρ (η (• ⊕• )))⊕• ) 1 1,2 2→1 1,2 1 2 2 X = ρ (η (((η (• ⊕• ))⊕(η (• ⊕• )))⊕• )) 2 1→2 2,3 1,2 1 2 1,2 1 2 3 2. The following two NLC-width expressions X and X also define the labeled graphs G 3 4 1 and G in Figure 1. 2 X = (• × • )× • 3 1 {(1,1)} 1 {(1,2)} 2 X = ◦ (((• × • )× (• × • ))× • ) 4 {(1,2),(2,2),(3,3)} 1 {(1,2)} 2 ∅ 1 {(1,2)} 2 {(2,3)} 3 Every NLC-width k-expression X has by its recursive definition a tree structure that is called the NLC-width k-expression-tree T for X. T is an ordered rooted tree whose leaves correspond to the vertices of graph val(X) and the inner nodes3 correspond to the operations 3To distinguish between the vertices of (non-tree) graphs and trees, we simply call the vertices of trees nodes. 4 2 G G 1 2 3 1 1 2 2 2 2 Figure1: TwolabeledgraphsG andG definedbyexpressionsX andX andbyexpressions 1 2 1 3 X and X , respectively. 2 4 of X, see [GW00]. In the same way we define the clique-width k-expression-tree for every clique-width k-expression, see [EGW03]. If integer k is known from the context or irrelevant for the discussion, then we sometimes use the simplified notion expression-tree for the notion k-expression-tree. For some node u of expression-tree T, let T(u) be the subtree of T rooted at u. Note that tree T(u) is always an expression-tree. The expression X(u) defined by T(u) can simply be determined by traversing the tree T(u) starting from the root, where the left children are visited first. X(u) defines a (possibly) relabeled induced subgraph G(u) of G. Foraninnernodevofsomeexpression-treeT andaleafuofT(v)wedefinebylab(u,G(v)) the label of that vertex of graph G(v) that corresponds to u. A node u of T is called a predecessor of a node u′ of T if u′ is on a path from u to a leaf. A node u of T is called the least common predecessor of two nodes u and u if u is a 1 2 predecessor of both nodes u ,u , and no child of u is a predecessor of u ,u . 1 2 1 2 3 Binary Operations Let G = (V ,E ) and G = (V ,E ) be two vertex disjoint graphs and let f be some binary 1 1 1 2 2 2 graph operation which creates a new graph f(G ,G ) from G and G . We next consider the 1 2 1 2 NLC-width and clique-width of graph f(G ,G ) with respect to the NLC-width or clique- 1 2 width of G and G . See [BM76, Har69] for an overview on graph operations. 1 2 We start with preliminary results whose proofs are very easy. 3.1 Disjoint Union, Co-Join The disjoint union or co-join G = G ∪G of G and G is the graph with vertex set V ∪V 1 2 1 2 1 2 and edge set E ∪E . SinceNLC-width and clique-width operations both contain the disjoint 1 2 union it is easy to see that NLC-width(G ∪G ) = max(NLC-width(G ),NLC-width(G )) 1 2 1 2 and clique-width(G ∪G ) = max(clique-width(G ),clique-width(G )). 1 2 1 2 This obviously implies that the NLC-width and clique-width of a graph can be computed by the maximum NLC-width or clique-width of its connected components. 5 3.2 Join The join G = G × G of G and G is the graph with vertex set V ∪ V and edge set 1 2 1 2 1 2 E ∪E ∪{{u ,u } | u ∈ V ,u ∈ V }. It is obviously that 1 2 1 2 1 1 2 2 NLC-width(G ×G ) = max(NLC-width(G ),NLC-width(G )) 1 2 1 2 and clique-width(G ×G ) = max(clique-width(G ),clique-width(G ),2). 1 2 1 2 By the bounds of Section 4.3 this obviously implies that the NLC-width of a graph also can be computed by the maximum NLC-width of its co-connected components. 3.3 Sum The sum G = G +G of G and G with |V | = |V | is the graph defined by the adjacency 1 2 1 2 1 2 matrix given by thesum of adjacency matrices of G and G , that is two vertices are adjacent 1 2 in G +G if and only if they are adjacent in G or they are adjacent in G . Note that the 1 2 1 2 representation of a graph by an adjacency matrix is not unique. Let G be the disjoint union of m paths P , each represented by a row in the adjacency 1 n matrix for G , and G be the disjoint union of n paths P , each represented by a column 1 2 m in the adjacency matrix for G then graph G + G is a n × m grid and is of unbounded 2 1 2 clique-width, even if G and G are of bounded tree-width. 1 2 3.4 Difference The difference G = G − G of G and G with |V | = |V | is the graph defined by the 1 2 1 2 1 2 adjacency matrix given by the difference of adjacency matrices of G and G , that is two 1 2 vertices are adjacent in G −G if and only if they are adjacent in G and not adjacent in 1 2 1 G . 2 If G has bounded tree-width, then since graphs of bounded tree-width are closed under 1 taking subgraphs, G has bounded tree-width and thus G has bounded clique-width [CR01]. If G is the K then G is the edge complement graph of G and has bounded NLC-width 1 n 2 and bounded clique-width. If G is the K then we obtain by G bipartite edge complement 1 n,n graphofG . Thusthedifferencegeneralizesedgecomplementandbipartiteedgecomplement. 2 3.5 Product A graph product of G and G is a new graph whose vertex set is V × V and for two 1 2 1 2 vertices (u ,u ) and (v ,v ) the adjacency in the product is defined by the adjacency (or 1 2 1 2 equality, or non-adjacency) of u ,v in G and u ,v in G . We consider some of the most 1 1 1 2 2 2 famous possibilities to define graph products. Results on graph products, independently of clique-width, can be found in [Har69, IK00, JT94]. The cartesian graph product G = G 2G of G and G is the graph with vertex set 1 2 1 2 V ×V and (u ,u ) and (v ,v ) are adjacent in G if and only if (u = v and {u ,v }∈ E ) 1 2 1 2 1 2 1 1 2 2 2 or (u = v and {u ,v } ∈ E ). If we take the cartesian product of two paths P and P we 2 2 1 1 1 n m obtain an n×m-grid which does not have bounded clique-width [GR00]. 6 Thecategorical graph productG = G ∗G ofG andG isthegraphwithvertexsetV ×V 1 2 1 2 1 2 and (u ,u ) and (v ,v ) are adjacent in G if and only if {u ,v } ∈ E and {u ,v } ∈ E . If 1 2 1 2 1 1 1 2 2 2 we take the categorical product of two paths P and P we obtain the disjoint union of two n m grids which does not have bounded clique-width [GR00]. The categorical graph product is also called edge product. The normal graph product G = G ·G of G and G is the graph with vertex set V ×V 1 2 1 2 1 2 and (u ,u ) and (v ,v ) are adjacent in G if and only if (u = v and {u ,v } ∈ E ) or 1 2 1 2 1 1 2 2 2 ({u ,v } ∈ E and u = v ) or ({u ,v } ∈ E and {u ,v } ∈ E ). If we take the normal 1 1 1 2 2 1 1 1 2 2 2 product of two paths P and P we obtain a graph of unbounded clique-width. n m The normal graph product is also called strong graph product or AND product. Theco-normal graph productG = G ◦G ofG andG isthegraphwithvertexsetV ×V 1 2 1 2 1 2 and (u ,u ) and (v ,v ) are adjacent in G if and only if {u ,v } ∈ E or {u ,v } ∈ E . If we 1 2 1 2 1 1 1 2 2 2 take the co-normal product of two paths P and P we obtain an n×m-grid which does not n m have bounded clique-width [GR00]. The co-normal graph product is also called disjunctive graph product or OR product. The lexicographic graph product G = G [G ] of G and G is the graph with vertex set 1 2 1 2 V ×V and (u ,u ) and (v ,v ) are adjacent in G if and only if ({u ,v } ∈ E ) or (u = v 1 2 1 2 1 2 1 1 1 1 1 and {u ,v }∈ E ). The lexicographic graph product is also called graph composition. 2 2 2 Next we show that the composition of two graphs of bounded NLC-width or bounded clique-width has bounded NLC-width and bounded clique-width. Theorem 3.1 For two graphs G and G 1 2 NLC-width(G [G ]) = max(NLC-width(G ),NLC-width(G )) 1 2 1 2 and clique-width(G [G ]) = max(clique-width(G ),clique-width(G )). 1 2 1 2 Proof Let G be a graph of NLC-width k and G be a graph of NLC-width k . Let T be 1 1 2 2 1 an NLC-width k -expression-tree for G and T be an NLC-width k -expression-tree for G . 1 1 2 2 2 We now construct from T and T an expression-tree T for G [G ]. We start with a copy T 1 2 1 2 of T . We relabel every leaf of T from • into ◦ , R(b)= a for b ∈ [k ]. For each leaf of T we 1 a R 2 insert a copy of T in T. Then we make the root of each of the copies of T adjacent to one of 2 2 each relabeled leaf of T. The resulting tree is an expression-tree for G [G ] using max(k ,k ) 1 2 1 2 labels. In the same way we can show the clique-width result. 2 3.6 Corona The corona G ∧G of G and G consists of the disjoint union of one copy of G and |V | 1 2 1 2 1 G1 copies of G and each vertex of the copy of G is connected to all vertices of one copy of G 2 1 2 (i.e. |V |·|V | edges are inserted in the disjoint union of the |V |+1 graphs). G1 G2 G1 The corona of graphs was introduced by Frucht and Harary in [FH70]. We show that we can bound the NLC-width and clique-width of G ∧G in the NLC-width or clique-width of 1 2 its combined graphs. 7 Theorem 3.2 Let m = max(NLC-width(G ),NLC-width(G )), then it holds 1 1 2 m ≤ NLC-width(G ∧G ) ≤ m +1 1 1 2 1 and for m = max(clique-width(G ),clique-width(G )) 2 1 2 m ≤ clique-width(G ∧G ) ≤ m +1 2 1 2 2 Proof First we prove the upper bound. Let G be a graph of NLC-width k and G be 1 1 2 a graph of NLC-width k . Let T be an NLC-width k -expression-tree for G and T be an 2 1 1 1 2 NLC-width k -expression-tree for G . We now construct from T and T an expression-tree 2 2 1 2 T for graph G ∧G . We start with a copy T of T . 1 2 1 For every i = 1,...,|V |, we first relabel leaf u of T originally labeled by • into G1 i li × . Then for i = 1,...,|V | we insert one new leaf v labeled by • into T. Further {(li,k+1)} G1 i li we insert one copy T of T and one node w labeled by ◦ , R(l) = k+1, l = 1,...,k into 2,i 2 i R 2 T. Last we insert two edges between u and v and u and w such that v is the left child of i i i i i u and w is the right child of u and one edge between the root of T and w into T. i i i 2,i i The resulting tree is an expression-tree for graph G ∧G using max(k ,k )+1 labels. 1 2 1 2 Since G and G are induced subgraphs of G ∧G the NLC-width of G ∧G is at least 1 2 1 2 1 2 the maximum of NLC-width(G ) and NLC-width(G ). 2 1 2 3.7 Substitution Let G and G be two graphs and let v ∈ V be a vertex of G . We define a new graph 1 2 G1 1 G [v/G ] which has vertex set V ∪ V − {v} and edge set E ∪ E − {{v,w} | w ∈ 1 2 G1 G2 G1 G2 N (v)}∪{{u,w} | u ∈ V ,w ∈ N (v)}. That is by G [v/G ] we denote the graph which G1 G2 G1 1 2 we obtain by substituting vertex v in G by graph G . By a proof similar to that of Theorem 1 2 3.1 we obviously can show the following bounds. Theorem 3.3 For two graphs G and G and v ∈ V 1 2 G1 NLC-width(G [v/G ])= max(NLC-width(G ),NLC-width(G )) 1 2 1 2 and clique-width(G [v/G ]) = max(clique-width(G ),clique-width(G )). 1 2 1 2 Vertex set V is also called a module of graph G [v/G ], since all vertices of V have the G2 1 2 G2 same neighbors in graph G [v/G ]. 1 2 3.8 1-Sum LetG andG betwographsandletv ∈ V andw ∈ V . WedefineanewgraphG ⊕ G 1 2 G1 G2 1 v,w 2 which has vertex set V ∪V −{v,w}∪{z} and edge set E ∪E −{{v,v }∈ E | v ∈ G1 G2 G1 G2 1 G1 1 V }−{{w,w } ∈ E |w ∈ V }∪{{z,z }| z ∈ N (v)∪N (w)}. Thatis byG ⊕ G G1 1 G2 1 G2 1 1 G1 G2 1 v,w 2 we denote the graph which we obtain by the disjoint union of G and G in which vertices v 1 2 and w are identified. By a proof similar to that of Theorem 3.1 we can show the following bounds. 8 Theorem 3.4 For two graphs G and G and v ∈ V and w ∈ V 1 2 G1 G2 NLC-width(G ⊕ G ) ≤ max(NLC-width(G ),NLC-width(G ))+2 1 v,w 2 1 2 and clique-width(G ⊕ G ) ≤ (clique-width(G ),clique-width(G ))+2. 1 v,w 2 1 2 Vertex z is alsocalled an articulation vertexof graphG ⊕ G , sinceG ⊕ G without 1 v,w 2 1 v,w 2 z has more connected components than G ⊕ G . The maximal connected components of 1 v,w 2 some graph G without any articulation vertex are called blocks of G. The bounds of Theorem 3.4 obviously imply that the NLC-width and clique-width of a graph can be estimated by the maximum NLC-width or clique-width of its blocks and its number of blocks. 4 Unary Operations In the following we consider unary graph operations f which create a new graph f(G) from a graph G= (V,E). 4.1 Quotient If we substitute a module V′ ⊆ V of a graph G by a single vertex, e.g. by removing all but one vertices of V′ from G, we call the resulting graph G[V′/v] the quotient of graph G. Since G[V′/v] is an induced subgraph of G we conclude the following bounds. Theorem 4.1 For every graph G and every module V′ ⊆ V G NLC-width(G[V′/v]) ≤ NLC-width(G) and clique-width(G[V′/v]) ≤ clique-width(G). The substitution and quotient operation is used in [Joh98, CMR00] to show that the NLC-width and clique-width of a graph can be obtained by the maximum NLC-width or clique-widthofitsprimesubgraphsappearingasquotientgraphsinamodulardecomposition. 4.2 Induced subgraph For every induced subgraph H of a graph G we know that NLC-width(H) ≤ NLC-width(G) and clique-width(H) ≤ clique-width(G). An expression for graph H can easily be obtained by an expression from graph G by omitting thevertices of V −V . Although taking inducedsubgraphsdoesnotincreasetheNLC-width G H and clique-width of a graph it is still open if there is a characterization for NLC for k ≥ 2 k or CW for k ≥ 3 by sets of forbidden subgraphs. k For arbitrary subgraphs of graphs of bounded clique-width, and thus also not for minors the clique-width and NLC-width can not be bounded. This can easily be shown by the example of a complete graph (NLC-width 1, clique-width 2) and the subgraphs and minors have arbritrary large NLC-width and clique-width. 9 4.3 Edge Complement The edge complement graph G of a graph G has the same vertex set as G and two vertices in G are adjacent if and only if they are not adjacent in G, i.e. G = (V,{{u,v} | u,v ∈ V,u 6= v,{u,v} 6∈ E}). The following bounds are known from [Wan94, CO00]. NLC-width(G)= NLC-width(G) 1 ·clique-width(G) ≤ clique-width(G)≤ 2·clique-width(G) 2 4.4 Bipartite complement If G = (V,E) is a bipartite graph with vertex partition V = V ∪V , such that there are no 1 2 edges between two vertices of V and no edges between two vertices of V , then the bipartite 1 2 bip complement G of G is the graph with vertex set V and edge set {{u,v} | {u,v} 6∈ E,u ∈ V ,v ∈ V }. In [LR04] is is shown that for bipartite graphs G is holds 1 2 1 bip ·clique-width(G) ≤ clique-width(G ) ≤ 4·clique-width(G). 4 In the same way one can show that 1 bip ·NLC-width(G) ≤ NLC-width(G )≤ 2·NLC-width(G). 2 4.5 Power of a graph The d-th power Gd of a graph G is a graph with the same set of vertices as G and an edge between two vertices if and only if there is a path of length at most d between them. Todinca [Tod03] has shown the following bound. clique-width(Gd)≤ 2·clique-width(G)·dclique-width(G) Now we show bounds for the NLC-width and clique-width of graphs when applying local graph operations which are our main results. 4.6 Switching Next we consider the switching operation defined by Seidel [Sei92]. Let G be a graph and x be a vertex of G. S(G,x) defines the graph whose vertex set is the same as of G and whose edge set is the edge set of G but the vertices adjacent to x become exactly to those vertices which are not adjacent to x. That is, V = V and S(G,x) G E = E −{{x,y} | y ∈ V ,{x,y} ∈ E }∪{{x,y} | y ∈ V ,x 6= y,{x,y} 6∈ E }. S(G,x) G G G G G Two graphs are called switching equivalent if one of them can be transformed into a graph isomorphic to the other by a sequence of switching operations. It is shown in [CC80] that deciding if two graphs are switching equivalent is an isomorphism complete problem. Next we will show that one switching operation in a graph increases or decreases its NLC-width at most by one. 10