{'fraction_non_alphanumeric': 0.05919898473367922, 'fraction_numerical': 0.017319249001530364, 'mean_word_length': 3.4960563852995468, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number

Nordhaus and Gaddum proved, for any graph G, that the chromatic number of G plus the chromatic number of G complement is less than or equal to the number of vertices in G plus 1. Finck characterized the class of graphs that satisfy equality in this bound. In this paper, we provide a new characterization of this class of graphs, based on vertex degrees, which yields a new polynomial-time recognition algorithm and efficient computation of the chromatic number of graphs in this class. Our motivation comes from our theorem that generalizes the Nordhaus-Gaddum theorem to the distinguishing chromatic number: for any graph G, the distinguishing chromatic number of G plus the distinguishing chromatic number of G complement is less than or equal to the number of vertices of G plus the distinguishing number of G. Finally, we characterize those graphs that achieve equality in the sum upper bounds simultaneously for both the chromatic number and for our distinguishing chromatic number analog of the Nordhaus-Gaddum inequality.


Introduction
We provide a generalization of the classic Nordhaus and Gaddum Theorem for the chromatic number to the distinguishing chromatic number. First, we recall their theorem, which gives bounds on the sum and the product of the chromatic number of a graph with that of its complement. We write χ(G) for the chromatic number of graph G, and for the complement of graph G we write G. The upper bound in (2) below was proved by Zykov [22] and the remaining three inequalities were proved by Nordhaus and Gaddum [16]. Theorem 1.1. If G is a graph with |V (G)| = n and χ(G) is the chromatic number of G, then 2 √ n ≤ χ(G) + χ(G) ≤ n + 1. (1) n ≤ χ(G)χ(G) ≤ n + 1 2 2 . (2) Finck [11] characterized the graphs that achieve equality for each of the four bounds in Equations (1.1) and (1.2). A labeling (or coloring) of the vertices of a graph G, h : V (G) → {1, . . . , r}, is said to be r-distinguishing (or just distinguishing) if the only automorphism of the graph that preserves all of the vertex labels is the identity. The distinguishing number of G, denoted by D(G), is defined as the minimum number r so that G has an r-distinguishing labeling. Albertson and Collins study the distinguishing number in [2] and subsequently other authors have studied the distinguishing number of graphs and of other structures, see for example [1,3,4,10,12,13,14,19,21], and many others.
The automorphism group of a graph is the same as the automorphism group of its complement, hence we get the following remark. In [9] we introduce the distinguishing chromatic number of a graph G, denoted by χ D (G), that requires the coloring to be proper as well as distinguishing. Together with Hovey we explored the distinguishing chromatic number from the perspective of group theory in [8]. The subject has received considerable attention from others, who considered the distinguishing chromatic number in [7], and others both the distinguishing number and the distinguishing chromatic number [6,15,18,20]. In this paper we ask whether there is a version of Theorem 1.1 for the distinguishing chromatic number. Definition 1.3. A labeling (or coloring) of the vertices of a graph G, h : V (G) → {1, . . . , r}, is said to be proper r-distinguishing (or just proper distinguishing) if it is a proper labeling (i.e., coloring) of the graph and the only automorphism of the graph that preserves all of the vertex labels is the identity. The distinguishing chromatic number of a graph G, denoted by χ D (G), is the minimum r such that G has a proper r-distinguishing labeling.
We note that the two lower bounds from Theorem 1.1 are still valid for the distinguishing chromatic number since χ(G) ≤ χ D (G) for all graphs G. Thus for any graph G with n = |V (G)| we have: For any graph G with D(G) = 1, we have χ(G) = χ D (G), and so any graph G with D(G) = 1 that satisfies equality in one of the lower bounds of Equations (1.1) and (1.2) the electronic journal of combinatorics 16 (2009), #R00 will be an example of a graph for which the corresponding bound in Equations (1.3) and (1.4) is tight. Finck's constructions [11] of such graphs include examples with D(G) = 1. Cavers and Seyffarth provide further examples in [5]. Before concluding this section, we present some background definitions and Brooks' Theorem. We use |S| to denote the size of set S and ∆(G) to denote the largest vertex degree in graph G. The independent set with s vertices is denoted by I s . For a vertex u ∈ V (G), we let N(u) be the set of neighbors of u in G. We will routinely use G − v in place of G − v and it is easy to see that these are equivalent. If S is a set of vertices in G, we write G[S] to denote the subgraph induced in G by S. We write Aut(G) for the group of all automorphisms of the graph G. We say that graph H is color-critical if χ(H − x) < χ(H) for every vertex x ∈ V (H). We will also need Brooks' Theorem: Brooks [1941]) If G is a connected graph other than a complete graph or an odd cycle, then χ(G) ≤ ∆(G).
In this paper we revisit the Nordhaus-Gaddum inequalities (Theorem 1.1) and the classes of graphs for which the upper bound in Equation (1.1) is tight. In Section 2 we give analogues of the upper bounds in Equations (1.1) and (1.2) for the distinguishing chromatic number. In Section 3 we give a new characterization of those graphs that achieve equality for the upper bound in Equation (1.1), based on vertex degrees. Our characterization leads to a new polynomial-time recognition algorithm for this class and efficient computation of the chromatic number of graphs in this class. In Section 4 we characterize those graphs that achieve equality in the upper bound of Equation (1.1) and our distinguishing chromatic number analog of this Nordhaus-Gaddum inequality.
2 The Nordhaus Gaddum inequalities for χ and χ D Nordhaus and Gaddum [16] describe three classes of graphs to illustrate that their bounds are tight. The first class is the complete graphs, which are tight for the upper bound in Equation (1.1) and the lower bound in Equation (1.2); next is the complete multipartite graphs with q parts, each of size q, which are tight for the lower bounds in Equation (1.1) and Equation (1.2); and third, the disjoint union of a complete graph and an independent set with one fewer vertex, K n +I n−1 which are tight for the upper bounds in Equation (1.1) and Equation (1.2). They note that it is not possible to satisfy the lower bound in Equation (1.1) and the upper bound in Equation (1.2) simultaneously. In Table 1, we  record the values for the distinguishing number and the distinguishing chromatic number  for these examples. The examples in Table 1 make clear that we will need to increase the upper bounds in Equations (1.1) and (1.2) in order to prove analogues for the distinguishing chromatic number. Each of these examples in the table is a complete multipartite graph (K n and K q,q,...,q ) or the complement of a complete multipartite graph (K t + I t−1 ). Collins and Trenk [9] have shown that complete multipartite graphs are exactly the graphs G for which χ D (G) = |V (G)|, that is, the graphs with the largest possible distinguishing chromatic the electronic journal of combinatorics 16 (2009) number. Note that the distinguishing number of each graph in the table is equal to either its distinguishing chromatic number or the distinguishing chromatic number of its complement. This leads us to our first step in finding an appropriate generalization of the Nordhaus-Gaddam theorems, which is to consider the distinguishing chromatic number of the complements of complete multipartite graphs. Proof. By the definition of χ D and D, the inequality χ D (G) ≥ D(G) holds for all graphs G. Since G is a complete multipartite graph, we know that G is a collection of disjoint complete graphs.
Thus we may recolor the graph G i and separately recolor the graph G i using |V i | + 1 new colors so that both new colorings are proper. We do this for each i ∈ C using a new set of |V i | + 1 colors for each i. The result is a coloring of G and a coloring of G using a total of D(G) i=1 (|V i | + 1) = |V (G)| + D(G) = n + D(G) colors. By construction, these colorings of G and G are proper. Moreover, we show they are distinguishing. Suppose there were a non-trivial automorphism σ of G that preserved colors. Since a new set of colors is used for each i, we know that σ must preserve membership in V i for each i. However, the original coloring was distinguishing, so the only automorphism of G that preserves membership in V i for each i must be the identity.
Proof. We follow the proof given in [16]. For all real numbers x, y we know 0 ≤ (x − y) 2 and thus 4xy ≤ (x + y) 2 and xy ≤ ( x+y 2 ) 2 . Substitute x = χ D (G) and y = χ D (G) into this last inequality and then apply Theorem 2.2 to finish the proof. Theorem 2.2 is robust, and in Proposition 2.6 we extend it to any group action on our graph G.
Definition 2.4. Let G be a graph and let Γ be a subgroup of Aut(G). The distinguishing number of G with respect to Γ, denoted by D Γ (G), is the minimum number of colors needed to color the vertices of G so that no non-identity element of Γ preserves the colors.
Definition 2.5. Let G be a graph and let Γ be a subgroup of Aut(G). The distinguishing chromatic number of G with respect to Γ, denoted by χ Γ D (G), is the minimum number of colors needed to color the vertices of G so that the coloring is proper, and no non-identity element of Γ preserves the colors. Proposition 2.6. If G be a graph with n = |V (G)| and Γ is a subgroup of Aut(G), then Proof. The proof is similar to the proof of Theorem 2.2.
We now turn to the question of characterizing those graphs that achieve equality in the upper bounds of identity of Theorem 1.1 and the related question of characterizing the analogous graphs for Theorem 2.2.
Proposition 2.1 shows that all complete multipartite graphs, including K n and K t + I t−1 , are NGD-graphs. However, they are not all NG-graphs, see Table 2 at the beginning of Section 4. the electronic journal of combinatorics 16 (2009), #R00 Corollary 2.8. If G is an NGD-graph with a fixed distinguishing coloring using D(G) colors, then each color class induces an NG-graph.
Proof. Let G be an NGD-graph and fix a distinguishing coloring of G using D(G) colors: 1, 2, 3, . . . , D(G). Let V i be the vertices of color i and let for any i, then following the proof of Theorem 2.2, we would have a distinguishing coloring of G and G using fewer than n + D(G) colors. This contradicts the assumption that G is an NGD-graph.

Characterizing NG-graphs
In this section we focus on the ordinary chromatic number χ and the inequality χ(G) + χ(G) ≤ n + 1 of Theorem 1.1. Our main result of this section is a characterization of NG-graphs, that is, the graphs that satisfy this with equality. Our characterization leads to a polynomial-time recognition algorithm for NG-graphs and an efficient computation of the chromatic number of NG-graphs.
Finck [11] characterizes the graphs that achieve equality for each of the four inequalities in Theorem 1.1. His characterizations involve arrays and in the case of NG-graphs, he gives an induction proof based on χ(H) for certain induced subgraphs H of G. This proof is not constructive, nor does it lead to a polynomial-time algorithm for recognizing whether a given graph is an NG-graph. Starr and Turner [17] give a characterization of NG-graphs that is simpler to state but relies explicitly on χ(G) and thus also can not be used to recognize NG-graphs in polynomial-time. Our characterization depends on partitioning vertices accordinng to their degree and leads to a polynomial-time algorithm to determine whether a graph is an NG-graph and if so to find its chromatic number.
Definition 3.1. If G is an NG-graph, then the ABC-partition of V (G) is as follows: The following theorem characterizes NG-graphs and Figure 1 illustrates the three possible forms.

Theorem 3.2. A graph G is an NG-graph if and only if when its vertex set is partitioned
We observe that χ(G) = a + b since we need a + b colors for A ∪ B and we may reuse a color from A for all vertices in C. In addition, χ(G) = c + 1 since we need c colors for C and one new color for A ∪ B. We have and c are integers. Then χ(G) = b + 3 (reuse a color from A for all vertices of C), χ(G) = c + 3 (reuse a color from A for all vertices of B), and n = 5 + b + c, so G is an NG-graph.
We prove the converse of Theorem 3.2 after a series of lemmas.
Proof. Using the assumption that H is an NG-graph and the given degree condition we have x is color-critical in H. This completes the proof of all the assertions of Lemma 3.3.
Lemma 3.4. Suppose G is an NG-graph and define A G , B G and C G as in Definition 3.1.
For any y ∈ B G and any x ∈ A G ∪ B G we have xy ∈ E(G).
Proof. For a contradiction, assume xy ∈ E(G). By the definition of B G and Lemma 3.3 we know y is color-critical in G and thus χ(G − y) = χ(G) − 1. Then the electronic journal of combinatorics 16 (2009), #R00 Now we can properly color G using χ(G) − 1 colors by taking a proper coloring of G − x − y using χ(G) − 2 colors and using one additional color for x and y, a contradiction. Proof. Given that G is an NG-graph, Definition 2.7 implies that G is also an NG-graph.
is an independent set. For x ∈ A ′ and y ∈ B ′ the same lemma tells us that xy ∈ E(G) and thus for x ∈ A and y ∈ C we know xy ∈ E(G).  If H is connected we conclude that H is an odd cycle or a complete graph. First consider the case H = C 2k+1 . If k ≥ 3 we have χ(H) = 3 and χ(H) = k + 1 so χ(H) + χ(H) = k + 4 ≤ k + (k + 1) = 2k + 1 = n which contradicts Lemma 3.6. If k = 1 then H is the complete graph C 3 , hence we conclude that either H is a 5-cycle (k = 2) or H is a complete graph.
Next we consider the case that H is not connected. Let We next present an algorithm for determining whether a graph is an NG-graph and in the affirmative case, computing its chromatic number. The proof of correctness and an analysis of the complexity are given in Theorem 3.8. Algorithm: NG Input: A graph G with n = |V (G)|. Output: A determination of whether G is an NG-graph and if so, its chromatic number. Initialize k = 1.
Loop: Partition V (G) according to vertex degrees as follows: . If the answer to any of the questions is 'no', continue to step ( * ). Otherwise (if all answers are yes), go to step (vi). (v) Is ac ∈ E(G) for all a ∈ A and all c ∈ C?
If the answers to (i) -(v) are 'yes', then check if χ(G) = k as follows: (vi) For G[A] a complete graph, check that |A| + |B| = k. For G[A] an independent set, check that |B| + 1 = k. For G[A] a 5-cycle, check that |B| + 3 = k.
If (vi) is affirmative, then graph G is an NG-graph and χ(G) = k and the algorithm ends. If not, continue to ( * ). ( * ) If k < n, increment k := k + 1 and return to the beginning of the loop. If k = n + 1, then graph G is not an NG-graph.
Theorem 3.8. Algorithm NG determines whether graph G is an NG-graph in polynomial time.
Proof. We first establish correctness. We know χ(G) is between 1 and n, so start with k = 1, thinking of k as a potential value of χ.
If the answers to (i) -(vi) are all 'yes', then Theorem 3.2 ensures that G is a an NG-graph, where (vi) verifies that χ(G) = k. If any of the answers to (i) -(vi) are no, we try the next possible value of k. If we reach k = n + 1, then we have tried all possible values of χ(G), and V (G) can not be partitioned so that G has the necessary form. Thus the algorithm correctly determines whether G is an NG-graph, and if so, computes the chromatic number.
Each of the questions can be answered in time O(n 2 ), and we potentially have to increment k from 1 to n so the running time of the algorithm is O(n 3 ).

Characterizing those NG-graphs that are NGDgraphs
In Section 3, we characterized NG-graphs and according to Theorem 3.2, there are three possibilities for A G . We name them for convenience in the next definition.

Definition 4.1. An NG-graph G is of Type 1 if G[A G ] is a clique, Type 2 if G[A G ] is an independent set and Type 3 if G[A G ] is a 5-cycle.
Note that an NG-graph with |A G | = 1 is both Type 1 and Type 2. Analogously we would like to characterize NGD-graphs. The set of NG-graphs and the set of NGD-graphs intersect, but neither is contained in the other, as demonstrated in Table 2.
In this section we make progress toward this goal by characterizing the NG-graphs that are also NGD-graphs. We show in Theorem 4.4 that none of the Type 3 NG-graphs are NGD-graphs and in Theorem 4.12 and Corollary 4.13, we characterize those Type 1 and Type 2 NG-graphs that are NGD-graphs. The next result shows that the complement of a Type 1 NG-graph is a Type 2 NG-graph.

Proposition 4.2.
If G is an NG-graph, then G is an NG-graph. Moreover, an NG-graph G is of Type 1 iff G is of Type 2, and G is of Type 3 iff G is of Type 3. G NG-graph NGD-graph K 3,1,1 yes yes K 3,2 no yes C 5 yes no C 7 no no Table 2: Examples of graphs that separate the classes of NG-graphs and NGD-graphs Proof. The first sentence follows immediately from Definition 2.7, so we focus on the statements in the second sentence. Since G is an NG-graph, χ(G) + χ(G) = n + 1 and A G is the set of vertices whose degree is χ(G) − 1. Therefore A G is the set of vertices whose is a clique if and only if G[A G ] is an independent set. So G is a Type 1 NG-graph if and only if G is a Type 2 NG-graph. The complement of a 5-cycle is a 5-cycle, so G is a Type 3 NG-graph if and only if G is a Type 3 NG-graph.
In proving that a Type 3 NG-graph G is not an NGD-graph, it will be helpful to have an optimal coloring of G in which one color appears on only one vertex. This is possible by our next lemma. Proof. We start by proving (i). Let G be a Type 1 NG-graph and fix a proper coloring of G using χ(G) colors. Since the vertices in A G ∪ B G induce a clique in G, they are all colored distinctly. If there are other vertices with x's color, they must be in C G . First consider the case in which x ∈ B G . Since A G = ∅, there exists y ∈ A G , and all vertices of C G may be recolored to have y's color. This leaves x as the only vertex in its color class.
Next consider the case in which x ∈ A G and |A G | = 1. By the definition of Type 1 NG-graphs, we know N(x) = B G and for each c ∈ C G we know deg(c) = deg(x) = |B G |. Thus each c ∈ C G has a non-neighbor in B G . We can recolor each c ∈ C G to be the color of any of its non-neighbors in B G . This leaves x as the only vertex in its color class.
Finally, consider the case in which x ∈ A G and |A G | > 1. Let a ∈ A G where a = x. Since ax ∈ E(G) we know a's color is different from x's color. Then each vertex in C G can be colored with a's color and this leaves x as the only vertex in its color class.
The proof of (ii) is similar to the first paragraph of the proof of (i).
Proof. Let G be a Type 3 NG-graph, and for a contradiction, assume G is also an NGDgraph. Fix a distinguishing coloring of G using colors 1, 2, 3, . . . , D(G). By definition the electronic journal of combinatorics 16 (2009), #R00 of a Type 3 NG-graph, the vertices in A G induce a 5-cycle in G, which we represent by By the structure of Type 3 NGD-graphs, we know that any particular v ∈ B G ∪ C G has the same relationship to each vertex in A G . Furthermore, any automorphism of G preserves the sets A G , B G , C G because these sets are defined in terms of vertex degrees. Thus a coloring of G is distinguishing if and only if it is distinguishing on both G[A G ] and G[B G ∪ C G ]. Since D(C 5 ) = 3, we may recolor the vertices in A G so that they use three colors and without loss of generality, vertices v 1 , v 3 get color 1, vertices v 2 , v 4 get color 2, and vertex v 5 gets color 3. Let V i be the vertices of color i and let G i = G[V i ] be the graph induced by the vertices of color i.
For simplicity of notation in what follows, let H = G 1 and F = G 2 . By Corollary 2.8, graphs H and F are NG-graphs. Furthermore, H (and likewise F ) is not of Type 3, since there is no C 5 induced in H (or in F ). Thus H and F are Type 1 or Type 2 NG-graphs and by Proposition 4.2, so are their complements H and F . Since v 1 and v 3 have the same degree in H, they are in the same part of the Lemma 4.3 to H (and F ), we conclude that there exists a proper coloring of H using χ(H) colors in which v 1 is uniquely colored. Similarly, there exists a proper coloring of F using χ(F ) colors in which v 2 is uniquely colored.
Following the proof of Theorem 2.2, for each i = 1, 2, 3, . . . , D(G), we create a new coloring of G i using χ(G i ) colors and of G i using χ(G i ) colors, so that χ(G i ) + χ(G i ) = |V i | + 1. Note that in this coloring we use a different palette of colors for each G i and for each G i . Furthermore, we choose colorings of H = G 1 and F = G 2 so that v 1 is uniquely colored (yellow) in H and v 2 is uniquely colored (purple) in F . Finally, we switch v 2 's color to yellow. Since v 1 and v 2 are not adjacent in G, the new coloring is proper. It is also distinguishing as follows: Recall that in G or G, any automorphism preserves the set of vertices {v 1 , v 2 , v 3 , v 4 , v 5 }. Note that v 1 , v 2 , v 3 , v 4 , v 5 were all given different colors in G before this final switch of v 2 's color, since they come from three different palettes, and v 1 , v 2 were uniquely colored. After the switching v 2 's color, each of v 3 , v 4 , v 5 is fixed by every automorphism that preserves the colors. There is no automorphism that switches v 1 and v 2 and preserves the colors after the final switch since v 1 is adjacent to v 3 and v 2 is not adjacent to v 3 in G. There are no vertices outside of A G that needed v 1 and v 2 to distinguish them, since all vertices outside of A have the same relationship to each vertex inside of A. Now we have given colorings of G and G that are distinguishing and proper using a total of n + D(G) − 1 colors, contradicting G being an NG-graph.
We will need a refinement on the vertex partition of a Type 1 NG-graph, where we further partition the set C G as L G ∪ M G . Let ⊕ be the external direct product of groups, and recall that S n is the group of permutations of the set {1, 2, 3, . . . , n}.  Proof. Recall the definition of the distinguishing number with respect to Γ from Definition 2.4. In any distinguishing coloring of G, the colors can be reused for each set in the ABLM-partition of G, and the number of colors needed for A is a and for L is ℓ, thus We now define some necessary parameters, x G and y G . The next lemma gives a bound on x + y, and following it are more two technical lemmas.   Note that for any two vertices in T u , there is an automorphism of G that interchanges them and fixes the rest of G. Thus, D(G) ≥ |T u | for every u ∈ M. In order to achieve a proper and distinguishing coloring, for each u ∈ M, each set T u must be colored distinctly and the colors used on the vertices in T u must be disjoint from S u . Conversely, if this is achieved, we have a proper and distinguishing coloring of G[B ∪ M]. Let u 1 , u 2 , . . . , u k be chosen so that T u 1 , T u 2 , . . . , T u k is a partition of M.
For 1 ≤ i ≤ k, we color the vertices in T u i distinctly, using as many colors in {1, 2, 3, . . . , b} − S u as possible. The smallest number of colors, in addition to our original b colors, that we need is max 1≤i≤k Lemma 4.11. Let G be a Type 1 NG-graph G, with an ABLM partition. If ℓ = 0, then y < D(G).
Proof. Given ℓ = 0, we know C = M. Since each vertex in B has degree greater than each vertex in A in G, each vertex in B has an edge to some vertex in M in G. That means that in G, every vertex in B is missing an edge to some vertex in M. For each v ∈ B, let W v = {w ∈ B : N G (w) = N G (v)}. Following the argument of Lemma 4.10, We are now ready to characterize those Type 1 NG-graphs that are also NGD-graphs. Note that the vertices in A G in a Type 1 NG-graph G form a complete subgraph, and all have the same neighborhood in the rest of the graph. So D(G) ≥ |A G |. Similarly, an independent set L of vertices in C G each of which is adjacent to every vertex in B G would all need to be distinctly colored in any distinguishing coloring of G, so D(G) ≥ |L|. In the theorem below, we show that for any Type 1 NG-graph G, D(G) is the maximum of these quantities if and only if G is NGD-graph.
Theorem 4.12. Let G be a Type 1 NG-graph G and a = |A G | and ℓ is the number of vertices in C G that are adjacent to every vertex in B G . Then G is an NGD-graph iff D(G) = max{a, ℓ}.
Proof. In any distinguishing and proper coloring of G, all vertices in B are colored distinctly, since B is complete, and there are no edges between the set A and the set L ∪ M, so colors used on vertices in A can be reused in L ∪ M. There are no edges between L and M, so colors used on L can be reused on M. Thus, χ D (G) = b + max{a, ℓ, x}. In a distinguishing and proper coloring of G, every vertex in A ∪ L ∪ M must be colored distinctly since L∪M is a complete graph, and all vertices in A are adjacent to all vertices in L ∪ M, and all vertices in A must be colored distinctly to eliminate the symmetries. Colors used on A and L can be re-used on B, since there are no edges in G between B and A ∪ L. Thus, χ D (G) = m + max{a + ℓ, y}. Hence χ D (G) + χ D (G) = b + max{a, ℓ, x} + m + max{a + ℓ, y}.
We analyze the cases, depending on max{a, ℓ, x} and max{a + ℓ, y}. Recall from Definition 2.7 that G is an NGD-graph iff χ D (G) + χ D (G) = a + b + ℓ + m + D(G). Our proof will also show that the graphs in Cases (2) -(5) are not NGD-graphs.
In this case G is an NGD-graph if and only if D(G) = max{a, ℓ}. By Corollary 4.7, D(G) ≥ max{a, ℓ}, so if D(G) = max{a, ℓ}, then G is an NGD-graph, and if D(G) > max{a, ℓ}, then G is not an NGD-graph.
the electronic journal of combinatorics 16 (2009), #R00 Corollary 4.13. A Type 2 NG-graph G is an NGD-graph iff D(G) = |A G | or D(G) equals the number of vertices in B G that have no adjacencies to vertices in C G .
In our next example, we describe a Type 1 NG-graph which falls into Case 1 of the proof of Theorem 4.12, but is not an NGD-graph.
Example 4.14. Let G be a Type 1 NG-graph with a = 1, b = 5, ℓ = 0, m = 5, and then define the edges between B G and M G so that each vertex in M G has degree 1 and is adjacent to a different vertex in B G . Then D(G) = 3, x = 0, y = 0, which fits in Case 1, except that G is not an NGD-graph, because D(G) > max{a, ℓ}.
We conclude with two questions and an acknowledgement. Question 4.2. In Theorem 4.12 and Corollary 4.13, we have characterized those NGgraphs which are NGD-graphs. Can this be extended to a characterization of the class of NGD-graphs?