Closed-Neighborhood Anti-Sperner Graphs

John P. McSorley,

Alison Marr, Thomas D. Porter, Walter D. Wallis,

Department of Mathematics,

Mailcode 4408, Southern Illinois University, Carbondale. IL 62901-4408. mcsorley60@hotmail.com

amarr@math.siu.edu tporter@math.siu.edu wdwallis@math.siu.edu

Abstract

For a simple graph G let N_{G}[u] denote the closed-neighborhood of vertex u ∈ V (G). Then G is closed-neighborhood anti-Sperner (CNAS) if for every u there is a v ∈ V (G)\{u} with N_{G}[u] ⊆ N_{G}[v]; and a graph H is closed-neighborhood distinct (CND) if every closedneighborhood is distinct, i.e., if N_{H}[u] ≠ N_{H}[v] when u ≠ v, for all u and v ∈ V (H).

In this paper we are mainly concerned with constructing CNAS graphs. We construct a family of connected CNAS graphs with n vertices for each fixed n ≥ 2. We list all connected CNAS graphs with ≤ 6 vertices, and find the smallest connected CNAS graph that lies outside these families. We indicate how some CNAS graphs can be constructed from a related type of graph, called a NAS graph. Finally, we present an algorithm to construct all CNAS graphs on a fixed number of vertices from labelled CND graphs on fewer vertices.

1 Closed-Neighborhood anti-Sperner Graphs

Let F = {N_{1}, N_{2}, …} be a family of sets. Then F is Sperner if no member of F is a subset of another member; and F is anti-Sperner if every member of F is a subset of another member.

Let G be a simple graph with a finite number of vertices. For each u ∈ V (G) let N_{G}[u] denote the closed-neighborhood of u, i.e., vertex u together with the set of vertices to which u is adjacent.

Let F(G) = {N_{G}[u] | u ∈ V (G)} be the family of closed-neighborhoods of G. Then if F(G) is anti-Sperner we say that G is a closed-neighborhood anti-Sperner (CNAS) graph, i.e., for every u ∈ V (G) there is a u^{p} ∈ V (G)\{u} with N_{G}[u] ⊆ N_{G}[u^{p}]. Vertex u^{p} is a closed-parent of vertex u; so a CNAS graph is a graph in which every vertex has a closed-parent. We note that u and u^{p} are adjacent.

A graph H is closed-neighborhood distinct (CND) if every closed-neighborhood is distinct, i.e., if N_{H}[u] ≠ N_{H}[v] when u ≠ v, for all u and v ∈ V (H).

If we replace the word ‘closed’ by ‘open’ in the first definition above then we have an open-neighborhood anti-Sperner graph, which we call a NAS graph. These graphs were introduced by Porter in [5], and studied further in Porter and Yucas [6], and in McSorley [4]. Our CNAS graphs are a natural variation of these graphs.

In this paper we are mainly concerned with constructing CNAS graphs:

In Section 2 we construct a family of connected CNAS graphs with n vertices for each fixed n ≥ 2. We list all connected CNAS graphs with ≤ 6 vertices, and find the smallest connected CNAS graph that lies outside these families.

In Section 3 we return to NAS graphs and indicate how some, but not all, CNAS graphs on a fixed number of n ≥ 2 vertices can be constructed from a suitable NAS graph also on n vertices; thus establishing a link between the two different types of graphs.

Section 4 contains preparatory material for Section 5, in which we present an algorithm to construct all CNAS graphs on a fixed number of n ≥ 2 vertices from labelled CND graphs on ≤ n − 1 vertices. This is similar to an algorithm that constructs NAS graphs from labelled ND (neighborhood distinct) graphs in McSorley [4]

Standard definitions of graph theory are from West [10].

2 Families of CNAS graphs, small CNAS graphs

For n ≥ 1 let K_{n} denote the complete graph on n vertices. For m ≥ 2 let S_{m} be a connected or disconnected graph on m vertices, with no isolates. For n ≥ 2 and 2 ≤ m ≤ n let K_{n}\S_{m} = K_{n} − E(S_{m}) denote the complete graph K_{n} with the edges of S_{m} removed. Finally, in any graph on n ≥ 2 vertices, call a vertex full if it has degree n − 1.

We are primarily interested in connected CNAS graphs, since each component in a disconnected CNAS graph must itself be CNAS.

Theorem 2.1 Let G be an arbitrary graph on n ≥ 2 vertices with at least two full vertices. Then G is a connected CNAS graph.

Proof. Clearly G is connected. Let u and v ∈ V (G) be two full vertices then N_{G}[u] = N_{G}[v] = V (G), the whole vertex set of G. So vertex u is a closed-parent of all vertices in V (G)\{u}, and v is a closed-parent of u. Hence every vertex in V (G) has a closed-parent, and so G is CNAS.

In particular, for n ≥ 2, the complete graph K_{n} is CNAS. Furthermore, we may preserve the CNAS property by removing edges from K_{n} provided that we always leave at least two full vertices:

Corollary 2.2 For any n ≥ 2 and any m with 2 ≤ m ≤ n − 2 let S_{m} be a graph on m vertices with no isolates. Then K_{n}\S_{m} is a connected CNAS graph.

Indeed, we can classify incomplete connected CNAS graphs on n vertices with at least two full vertices:

Theorem 2.3 For n ≥ 2 let G ≠ K_{n} be a connected CNAS graph on n vertices with at least two full vertices. Then there is a graph S_{m} on m vertices with no isolates where 2 ≤ m ≤ n − 2 such that G = K_{n}\S_{m}.

Proof. Let {u_{1}, u_{2}, …, u_{m}} be the non-full vertices of G, since G ≠ K_{n} then m ≥ 2. And let {u_{m+1}, …, u_{n}} be the full vertices of G, the number of these is n − m ≥ 2, so m ≤ n − 2. Consider a copy of K_{m} with vertex set {u_{1}, u_{2}, …, u_{m}}, and the K_{n} with vertex set {u_{1}, u_{2}, …, u_{n}}. Let S_{m} = \overline{G[u_{1}, u_{2}, …, u_{m}]}, where the complement is taken in the above K_{m}.

Now if u_{i} is an isolate in S_{m} then in G[u_{1}, u_{2}, …, u_{m}] it has (full) degree m − 1 and so in G it is full, a contradiction. Hence S_{m} has no isolates. Then G = K_{n}\S_{m}, and 2 ≤ m ≤ n − 2.

So, for each n ≥ 2, we have a family K_{n}\S of connected CNAS graphs, each member of which has at least two full vertices:

K_{n}\S = {K_{n}}∪{K_{n}\S_{m} | S_{m} is a graph on m vertices with no isolates, 2 ≤ m ≤ n−2}.

For those G outside these families we have:

Theorem 2.4 Let G be a connected CNAS graph on n ≥ 2 vertices without at least two full vertices. Then G has no full vertices.

Proof. Clearly G cannot have exactly one full vertex, because this full vertex would not have a closed-parent; hence it has no full vertices.

The connected CNAS graphs G on 2 ≤ n ≤ 6 vertices are shown in Table 1. Here K_{a,b} denotes the complete bipartite graph with parts of size a and b, P_{a} denotes the path on a vertices, and e denotes an edge.

\begin{matrix}n & G \\ 2 & K_{2} \\ 3 & K_{3} \\ 4 & K_{4}, K_{4}\K_{2} \\ 5 & K_{5}, K_{5}\K_{2}, K_{5}\P_{3}, K_{5}\K_{3} \\ 6 & K_{6}, K_{6}\K_{2}, K_{6}\P_{3}, K_{6}\2K_{2}, K_{6}\K_{3}, K_{6}\P_{4} \\ 6 & K_{6}\K_{1,3}, K_{6}\(K_{1,3} + e), K_{6}\K_{2,2}, K_{6}\(K_{2,2} + e), K_{6}\K_{4}, F \end{matrix}

Table 1. Connected CNAS graphs G with n vertices, 2 ≤ n ≤ 6.

Example 1 Of the connected CNAS graphs on 2 ≤ n ≤ 6 vertices all except one, F, belongs to a family K_{n}\S for some n ≥ 2. The graph F is shown below. It is the smallest connected CNAS graph that lies outside these families, i.e., without at least two full vertices. So, from Theorem 2.4 it has no full vertices, indeed it has 6 vertices and maximum degree 4.

F  • • • • • •

3 CNAS graphs and Neighborhood anti-Sperner graphs

In this Section we show how to construct some CNAS graphs with a fixed number of n vertices from NAS graphs with n vertices, thus establishing a connection between the two different types of graph.

Let F_{o}(H) = {N_{H}(u) | u ∈ V (H)} be the family of open-neighborhoods of a graph H. We always drop the prefix ‘open’ in open-neighborhood, openparent, open-twin, etc.. Then if F_{o}(H) is anti-Sperner we say that H is a neighborhood anti-Sperner (NAS) graph. Hence, in a NAS graph H, for every u ∈ V (H) there is a parent u^{p_{o}} ∈ V (H)\{u} such that N_{H}(u) ⊆ N_{H}(u^{p_{o}}).

NAS graphs have been studied in [4], [5], and [6]. Because the definition of a CNAS graph is similar to that of a NAS graph, we might sensibly ask whether we can construct CNAS graphs from NAS graphs. However it doesn’t seem possible to construct all CNAS graphs of order n from NAS graphs of order n, but some CNAS graphs can be constructed:

For an arbitrary graph G, the set P ⊆ V (G) is a closed-parent-set if it is closed under taking closed-parents, i.e., if every u ∈ P has a closed-parent u^{p} ∈ P. And a closed-parent-set partition of V (G) is a partition of V (G) into closed-parent-sets. Similarly, for an arbitrary H, the set P_{o} ⊆ V (H) is a parent-set if it is closed under taking parents, i.e., if every u ∈ P_{o} has a parent u^{p_{o}} ∈ P_{o}. And a parent-set partition of V (H) is a partition of V (H) into parent-sets.

Theorem 3.1 Let H be a NAS graph with {P_{o,1}, P_{o,2}, …, P_{o,d}} a parentset partition of V (H). Let G = H^{+} be the graph obtained from H by making P_{o,i} into a clique for each 1 ≤ i ≤ d, i.e., by making G[P_{o,i}] = K_{|P_{o,i}|}. Then G is a CNAS graph and {P_{o,1}, P_{o,2}, …, P_{o,d}} is a closed-parent-set partition of V (G).

Proof. For an arbitrary vertex u ∈ V (G) = V (H) let u ∈ P_{o,i} for some fixed i, so N_{G}[u] = N_{H}(u) ∪ P_{o,i}. Now, in H, let u^{p_{o}} ∈ P_{o,i} be a parent of u ∈ P_{o,i}, so N_{G}[u^{p_{o}}] = N_{H}(u^{p_{o}}) ∪ P_{o,i}. Hence, since N_{H}(u) ⊆ N_{H}(u^{p_{o}}), then N_{G}[u] ⊆ N_{G}[u^{p_{o}}], i.e., u^{p_{o}} ∈ P_{o,i} is a closed-parent of u in G. Hence (in G) P_{o,i} is a closed-parent-set. Furthermore, since u ∈ V (G) is arbitrary then G is CNAS. Each P_{o,i} is a closed-parent-set of V (G), and so {P_{o,1}, P_{o,2}, …, P_{o,d}} is a closed-parent-set partition of V (G).

The null graph N_{n} is the graph with n ≥ 1 vertices and no edges.

Example 2 We can construct many non-isomorphic CNAS graphs from a single NAS graph. Consider the NAS graph H = N_{1}∪N_{1}∪K_{2,2} on 6 vertices. There are 5 different parent-set partitions of V (H), yielding 4 non-isomorphic CNAS graphs G = H^{+} on 6 vertices, 3 of which are connected:

See next page

The construction of Theorem 3.1 yields a CNAS graph G = H^{+} with a closed-parent-set partition of V (G) in which each closed-parent-set is a clique. However not all CNAS graphs have such a partition, and those that do not cannot be obtained via this construction no matter which NAS graph H and which parent-set partition of V (H) is used. The smallest CNAS graph without such a partition is K_{4}\K_{2}. Other constructions of CNAS graphs from NAS graphs do not seem to be available. But Theorem 3.1 is still useful for obtaining some CNAS graphs from NAS graphs, as illustrated in Example 2.

NAS H = N_{1} ∪ N_{1} ∪ K_{2,2} • • • • • • P_{o,1}  ^{CNAS G = H^{+} • • • • • •  K_{6}}

• • • • • • P_{o,1} P_{o,2}  ^{• • • • • •  K_{2} ∪ K_{4}}

• • • • • • P_{o,1} P_{o,2} P_{o,3}  ^{• • • • • •  K_{2} ∪ K_{4}}

• • • • • • P_{o,1} P_{o,2}  ^{• • • • • •  K_{6}\K_{2,2}}

• • •  • • • P_{o,1} P_{o,2}  ^{• • •  • • •  F}

4 Closed-Neighborhood distinct graphs, labelled graphs, miscellaneous

This Section contains preparatory material needed in Section 5.

The join X ∨ Y of two graphs X and Y with disjoint vertex sets is the graph with vertex set V (X) ∪ V (Y) and edge set E(X) ∪ E(Y) ∪ {xy | x ∈ V (X) and y ∈ V (Y)}, i.e., every vertex in V (X) is joined to every vertex in V (Y).

Recall that a graph H is closed-neighborhood distinct (CND) if every closed-neighborhood is distinct, i.e., if N_{H}[u] ≠ N_{H}[v] when u ≠ v, for all u and v ∈ V (H). Sumner [9] called such graphs point distinguishing and they are also known as supercompact, see Lim [3]. See also Entringer and Gassman [2] for further properties of these graphs.

Sumner proved the following Theorem for graphs in which every neighborhood is distinct, which he called point determining. But he stated that there is a dual Theorem for CND graphs. We state his Theorem using our notation, (see Theorem 2 of Sumner [9] and Theorem 2.1 of Chia and Lim [1]):

Let H be a CND graph with ≥ 2 vertices. Then there is a vertex w ∈ V (H) such that H − w is also CND.

The CND graphs with ≤ 3 vertices are: N_{1}, N_{2}, N_{3}, and P_{3}.

We use Sumner’s result in the following algorithm which constructs all CND graphs on t vertices from CND graphs on t − 1 vertices:

Algorithm CND Graphs Four step algorithm to construct all CND graphs H on a fixed number of t ≥ 2 vertices from all CND graphs on t − 1 vertices.

(1) List all non-isomorphic CND graphs H_{t−1} on t − 1 vertices.

(2) For each H_{t−1} list all subsets S ⊆ V (H_{t−1}) for which S ≠ N_{H_{t−1}}[u] for all u ∈ V (H_{t−1}), i.e., S is distinct from all closed-neighborhoods of H_{t−1}. Note that S = ∅ is to be considered.

(3) Let w ∉ V (H_{t−1}) be a new vertex. For each such H_{t−1} and S let H be the graph with vertices and edges as follows:

V (H) = V (H_{t−1}) ∪ {w}  and  E(H) = E(H_{t−1}) ∪ {ws | s ∈ S},

i.e., H is the graph obtained by joining w to S.

(4) Remove isomorphic copies from the graphs in (3).

We now have a complete list of CND graphs H with t vertices, with no repeated H.

Example 3 We find all CND graphs on 4 vertices from the two CND graphs N_{3} and P_{3} on 3 vertices. For each such graph there are 2^{3} − 3 = 5 subsets S, yielding 10 CND graphs on 4 vertices. Removing isomorphic copies leaves the 5 non-isomorphic CND graphs below:

[figure]

We can then use these CND graphs on 4 vertices to construct all CND graphs on 5 vertices ,....., and so on. Hence, for any t ≥ 1, we can construct all CND graphs on ≤ t vertices.

We will need labelled graphs H in which every vertex u ∈ V (H) has been labelled with a positive integer ℓ(u) ≥ 1. We also need the concept of label-isomorphism:

Let H and H′ be two arbitrary labelled graphs. Then H and H′ are label-isomorphic if there is a bijection between V (H) and V (H′) which is a graph isomorphism that preserves labels. So if in a label-isomorphism we have u ∈ V (H) ↔ u′ ∈ V (H′), then ℓ(u) = ℓ(u′).

Example 4 Consider the two labellings of the first graph from Example 3, H and H′, shown below. Next to vertex u is its label ℓ(u).

[figure: v; 3; u; 1; w; 2; x; 1; H; v′; 2; u′; 1; w′; 3; x′; 1; H′]

Clearly u ↔ u′, v ↔ v′, w ↔ w′, x ↔ x′ is an isomorphism but not a labelisomorphism since ℓ(v) ≠ ℓ(v′). However u ↔ x′, v ↔ w′, w ↔ v′, x ↔ u′ is a label-isomorphism. So H and H′ are label-isomorphic.

Finally, for an arbitrary graph G, if N_{G}[u] = N_{G}[v] for two different vertices u and v ∈ V (G) then u and v are closed-twins. We note that closed-twins are adjacent. We denote a closed-twin of u by u^{∗}. If u has no closed-twin then it is closed-twinless. If H is CND then every vertex in V (H) is closed-twinless.

5 Constructing CNAS Graphs from labelled CND Graphs

In this final Section we show how to construct all CNAS graphs G on a fixed number of n ≥ 2 vertices from labelled CND graphs H on ≤ n − 1 vertices.

Let G be an arbitrary graph. Consider the following equivalence relation ≡ on V (G): u ≡ u′ if and only if N_{G}[u] = N_{G}[u′]. The equivalence class containing u is U = {u′ ∈ V (G) | N_{G}[u] = N_{G}[u′]} ≠ ∅. Here every vertex u′ is a closed-twin of u, which we normally write as u^{∗}, provided that it is distinct from u. We let t denote the number of equivalence classes under ≡ of V (G) (or of G); and denote the classes themselves by U_{1}, U_{2}, …, U_{t}, where |U_{i}| = ℓ_{i} for each i = 1, 2, …, t.

Theorem 5.1 Let G be an arbitrary graph with equivalence relation ≡. Let U and V be two distinct equivalence classes with u ∈ U and v ∈ V arbitrary. Then

(i) the induced subgraph G[U] = K_{|U|},

(ii) uv ∈ E(G) if and only if G[U ∪ V] = G[U] ∨ G[V] = K_{|U|} ∨ K_{|V |},

(iii) uv ∉ E(G) if and only if G[U ∪ V] = K_{|U|} ∪ K_{|V |}.

Proof. (i) If |U| = 1 then clearly G[U] = K_{|U|}. So assume that |U| ≥ 2 and let u and u^{∗} be two arbitrary distinct vertices in U. Then u ∈ N_{G}[u] = N_{G}[u^{∗}], i.e., uu^{∗} ∈ E(G). Since u and u^{∗} are arbitrary, then G[U] = K_{|U|}. (ii) Now u ∈ U and v ∈ V are arbitrary, let u′ ∈ U and v′ ∈ V also be arbitrary, (so u = u′ and/or v = v′ is allowed). Since uv ∈ E(G), so v ∈ N_{G}[u] = N_{G}[u′], so u′ ∈ N_{G}[v] = N_{G}[v′], and then u′v′ ∈ E(G). Hence G[U ∪ V] = G[U] ∨ G[V] = K_{|U|} ∨ K_{|V |}, using (i). The converse is clear. (iii) Similar to (ii), using (i) again.

So, in any graph G and for any two distinct equivalence classes U and V, either G[U ∪ V] = K_{|U|} ∨ K_{|V |} or G[U ∪ V] = K_{|U|} ∪ K_{|V |}. This suggests the following two constructions:

Construction G_{≡} Let G be an arbitrary graph, with equivalence relation ≡ and equivalence classes U_{1}, U_{2}, …, U_{t}, where |U_{i}| = ℓ_{i} for each i = 1, 2, …, t. Construct a labelled graph G_{≡} with t vertices, and edges as follows:

V (G_{≡}) = {U_{1}, U_{2}, …, U_{t}} and E(G_{≡}) = {U_{i}U_{j} | G[U_{i}∪U_{j}] = K_{|U_{i}|}∨K_{|U_{j}|}},

where vertex U_{i} has been labelled with ℓ_{i} for each i. We call G_{≡} the closedreduced graph of G. See [3] where an unlabelled version of this graph is called S(G). An unlabelled version is also known as the Roberts reduct, see Roberts [8], and Section 10.6 of Prisner [7]. Note that |V (G)| = ∑_{i=1}^{t} ℓ_{i}.

Construction H^{↑} Let H be an arbitrary labelled graph, so every u ∈ V (H) has been labelled with a positive integer ℓ(u) ≥ 1. Construct a new graph H^{↑} from H by replacing each vertex u with the ℓ(u) vertices from exp(u) = {x_{1}, x_{2}, …, x_{ℓ(u)}}, the expansion set of u, where H^{↑}[exp(u)] = K_{ℓ(u)} is a clique. Similarly, replace v by exp(v) = {y_{1}, y_{2}, …, y_{ℓ(v)}}, etc.. If uv ∈ E(H) then let H^{↑}[exp(u), exp(v)] = K_{ℓ(u)} ∨ K_{ℓ(v)}, and if uv ∉ E(H) then let H^{↑}[exp(u), exp(v)] = K_{ℓ(u)} ∪ K_{ℓ(v)}.

We illustrate these constructions with F below. The equivalence classes of F under ≡ are: U_{1} = {x_{1}}, U_{2} = {y_{1}, y_{2}}, U_{3} = {z_{1}, z_{2}}, and U_{4} = {t_{1}}.

F  x_{1} • • y_{1}  •y_{2} • z_{1}  •z_{2} • t_{1}  • • • • 1 U_{1} 2 U_{2} 2 U_{3} 1 U_{4}  F_{≡}

From the above two constructions we have:

Theorem 5.2 Let G be an arbitrary graph. Then G = (G_{≡})^{↑}.

Given an arbitrary graph G, as we closed-reduce to G_{≡} we identity vertices with the same closed-neighborhood, so G_{≡} should be CND (Theorem 3.1 of [3]):

Theorem 5.3 Let G be an arbitrary graph. Then G_{≡} is CND.

Proof. Let U and V be two distinct vertices in V (G_{≡}). Suppose that G_{≡} is not CND and N_{G_{≡}}[U] = N_{G_{≡}}[V] = {U, V, U_{1}, U_{2}, …, U_{d}} for some d ≥ 1, or N_{G_{≡}}[U] = N_{G_{≡}}[V] = {U, V }.

In the first case let u ∈ V (G) lie in equivalence class U, then, since N_{G_{≡}}[U] is a clique, we have N_{G}[u] = U ∪ V ∪ (⋃_{k=1}^{d} U_{k}). Similarly, if v ∈ V then N_{G}[v] = V ∪ U ∪ (⋃_{k=1}^{d} U_{k}). Hence N_{G}[u] = N_{G}[v] so u ≡ v, a contradiction since u ∈ U and v ∈ V and U ≠ V. Thus G_{≡} is CND. The proof is similar when N_{G_{≡}}[U] = N_{G_{≡}}[V] = {U, V }.

The following two technical Lemmas are required before our main results:

Lemma 5.4 Let H be an arbitrary labelled CND graph with t ≥ 1 vertices. Then H^{↑} has t equivalence classes under ≡.

Proof. Let H^{↑} have s equivalence classes under ≡, we will show that s = t.

Let each vertex u ∈ V (H) be labelled with ℓ(u) ≥ 1. The Lemma is clearly true if t = 1. So assume that t ≥ 2 and let u and v be distinct vertices in V (H). In the construction of H^{↑} from H we replace u by the ℓ(u) vertices from exp(u) = {x_{1}, x_{2}, …, x_{ℓ(u)}}, and we replace v by the ℓ(v) vertices from exp(v) = {y_{1}, y_{2}, …, y_{ℓ(v)}}. Let x_{i} ∈ exp(u) and y_{j} ∈ exp(v) be arbitrary. Now, since H is CND, we have N_{H}[u] ≠ N_{H}[v]. Without loss of generality let w ∈ N_{H}[u]\N_{H}[v] and let exp(w) = {z_{1}, z_{2}, …, z_{ℓ(w)}}, (w = u is allowed). If w ≠ u then, in H^{↑}, we have x_{i} ∈ N_{H^{↑}}[z_{1}] but y_{j} ∉ N_{H^{↑}}[z_{1}]. So N_{H^{↑}}[x_{i}] ≠ N_{H^{↑}}[y_{j}], and so x_{i} ≢ y_{j} in H^{↑}. So x_{i} and y_{j} are in distinct equivalence classes of H^{↑}. Now let V (H) = {u_{1}, u_{2}, …, u_{t}}. We can apply the above argument to every distinct pair u_{a} and u_{b} ∈ V (H), showing that exp(u_{a}) and exp(u_{b}) are contained in distinct equivalence classes of H^{↑}. Hence t ≤ s. A slight modification of this argument is required if w = u.

Suppose s > t. Let e_{1}, e_{2}, …, e_{s} be representatives of the s equivalence classes under ≡ in H^{↑}, one from each class. Then, by the pigeon hole principle, there must be some vertex u ∈ V (H) whose expansion set exp(u) contains two of e_{1}, e_{2}, …, e_{s}. Suppose that e_{a} and e_{b} ∈ exp(u) where 1 ≤ a < b ≤ s, then N_{H^{↑}}[e_{a}] = N_{H^{↑}}[e_{b}], i.e., e_{a} ≡ e_{b} in H^{↑}, a contradiction. Hence s ≤ t. And so s = t.

In an arbitrary graph G we say that vertex u ∈ V (G) is closed-parentless if u does not have a closed-parent. And if u does have a closed-parent u^{p} with N_{G}[u] ⊂ N_{G}[u^{p}] then we call u^{p} a proper closed-parent of u.

In the following Lemma, as usual, we denote the equivalence class under ≡ containing u by U, and the equivalence class containing u^{p} by U^{p}.

Lemma 5.5

(i) In an arbitrary graph G let u^{p} be a proper closed-parent of u. Then, in G_{≡}, U^{p} is a proper closed-parent of U.

(ii) For a CNAS graph G let W ∈ V (G_{≡}) be closed-parentless. Then ℓ(W) ≥ 2.

Proof. (i) In G since u^{p} is a proper closed-parent of u then N_{G}[u^{p}] ≠ N_{G}[u], and so U^{p} ≠ U, i.e., in G_{≡} the vertices U^{p} and U are distinct, and U^{p}U ∈ E(G_{≡}).

We first show that U^{p} is a closed-parent of U. If not, then there exists a vertex V with V ∈ N_{G_{≡}}[U] but V ∉ N_{G_{≡}}[U^{p}]. Now V ≠ U since U^{p}U ∈ E(G_{≡}) and so U ∈ N_{G_{≡}}[U^{p}], and V ≠ U^{p} since U^{p} ∈ N_{G_{≡}}[U^{p}]. Let v ∈ V (G) be in equivalence class V. Then v ∈ N_{G}[u] but v ∉ N_{G}[u^{p}], a contradiction since u^{p} is a (proper) closed-parent of u. So, in G_{≡}, U^{p} is a closed-parent of U. Now G_{≡} is CND so U^{p} cannot be a closed-twin of U, but it is a closed-parent of U, so it must be a proper closed-parent of U. (ii) Let W ∈ V (G_{≡}) be closed-parentless, then W has no proper closedparents in G_{≡}. Let w ∈ V (G) lie in equivalence class W, so, by (i), w has no proper closed-parents in G. But G is CNAS so w must have a closed-parent which must be a closed-twin w^{∗}, so |W | ≥ 2, i.e., ℓ(W) ≥ 2.

The following main result deals with both connected and disconnected CNAS graphs.

Theorem 5.6 Let G be an arbitrary graph. Then G is a CNAS graph with t equivalence classes under ≡ if and only if G_{≡} is a labelled t vertex CND graph in which all closed-parentless vertices have label ≥ 2.

Proof. First let G be a CNAS graph with t equivalence classes under ≡ given by U_{1}, U_{2}, …, U_{t}, where |U_{i}| = ℓ_{i} for each i = 1, 2, …, t. Then the construction of G_{≡} from G and Theorem 5.3 shows that G_{≡} is a labelled t vertex CND graph. From Lemma 5.5(ii) all closed-parentless vertices in G_{≡} have label ≥ 2.

Conversely suppose that G_{≡} is a labelled t vertex CND graph in which all closed-parentless vertices have label ≥ 2. From Theorem 5.2 we have G = (G_{≡})^{↑}. Now any vertex u ∈ V (G) is a u_{j} ∈ exp(U) = {u_{1}, u_{2}, …, u_{ℓ(U)}} for some U ∈ V (G_{≡}), and the closed-neighborhoods N_{G}[u_{j}] for j = 1, 2, …, ℓ(U) are all equal. Either ℓ(U) = 1 or ℓ(U) ≥ 2. If ℓ(U) = 1 then U is not closedparentless and so U has a closed-parent U^{p}, and then u_{1} has a closed-parent in exp(U^{p}). If ℓ(U) ≥ 2, then each u_{j} has a closed-twin, which is a closedparent. Hence, in either case, u = u_{j} has a closed-parent, and so G is CNAS. Furthermore, since G_{≡} is a t vertex CND graph then, from Lemma 5.4, the graph G = (G_{≡})^{↑} has t equivalence classes under ≡.

For connected graphs we have:

Lemma 5.7 Let G be an arbitrary graph. Then G is connected if and only if G_{≡} is connected.

Proof. Let G be connected. To see that G_{≡} is connected, let U and V be two different vertices of G_{≡}, and let u ∈ U and v ∈ V in G. Then, since G is connected, there is a path u = w_{1}w_{2} ⋯ w_{d} = v between u and v in G, but then U = W_{1}W_{2} ⋯ W_{d} = V is a walk between U and V in G_{≡}, and so G_{≡} is connected. The converse is proved similarly.

Using Lemma 5.7 we have the following ‘connected’ version of Theorem 5.6:

Theorem 5.8 Let G be an arbitrary graph. Then G is a connected CNAS graph with t equivalence classes under ≡ if and only if G_{≡} is a connected labelled t vertex CND graph in which all closed-parentless vertices have label ≥ 2.

We need another definition: Let n ≥ 2 be a positive integer. A partition of n is a set P = {ℓ_{1}, ℓ_{2}, …, ℓ_{t}} of t ≥ 1 integers that satisfy 1 ≤ ℓ_{1} ≤ ℓ_{2} ⋯ ≤ ℓ_{t} and ∑_{i=1}^{t} ℓ_{i} = n. Partition P has t parts.

We now present an algorithm to construct (connected) CNAS graphs G from (connected) labelled CND graphs H. It uses Theorems 5.6 and 5.8 where we denote G_{≡} by H, and consider all possible (connected) labelled CND graphs H, and then construct all possible (connected) CNAS graphs G by using G = H^{↑}.

Let the labels on the t vertices of H = G_{≡} be {ℓ_{1}, ℓ_{2}, …, ℓ_{t}}, where each ℓ_{i} ≥ 1. If G is CNAS with n ≥ 2 vertices then a vertex u ∈ V (G) of maximum degree must have a closed-twin, so |U| ≥ 2. So some ℓ_{i} ≥ 2, and since n = ∑_{i=1}^{t} ℓ_{i}, then t ≤ n − 1.

Algorithm (Connected) CNAS Graphs Four step algorithm to construct all (connected) CNAS graphs G on a fixed number of n ≥ 2 vertices from all (connected) labelled CND graphs H on 1 ≤ t ≤ n − 1 vertices.

For each fixed t = 1, 2, …, n − 1:

(1) By repeated use of Algorithm CND Graphs, (suitably modified to generate connected CND graphs if required), list all non-isomorphic (connected) CND graphs H_{t} on t vertices.

(2) List all partitions P_{t} of n with t parts.

(3) For each (connected) graph H_{t} and partition P_{t} = {ℓ_{1}, ℓ_{2}, …, ℓ_{t}} label its t vertices with {ℓ_{1}, ℓ_{2}, …, ℓ_{t}} in all possible non-label isomorphic ways, ensuring that all closed-parentless vertices have label ≥ 2.

(4) For each (connected) labelled graph H_{t} construct G = H_{t}^{↑}.

Because of Theorems 5.6 and 5.8 we have a complete list of (connected) CNAS graphs G with n vertices, with no repeated G.

Example 5 We illustrate Algorithm Connected CNAS Graphs for n = 5 by constructing the 4 connected CNAS graphs G on 5 vertices, see Table 1. From the Algorithm we need to consider all connected CND graphs H_{t} on 1 ≤ t ≤ 4 vertices. These graphs H_{t} are shown below, suitably labelled. Two such H_{t} cannot be labelled since closed-parentless vertices, indicated by \overline{cp}, require a label of ≥ 2, thus forcing the sum of all labels to be > 5.

CND H H_{1}  5•  ^{•  • •  • •  CNAS G K_{5}}

H_{3}  • • • 1 2 2  •  • •  • •  K_{5}\P_{3}

H′_{3}  • • • 1 3 1  • • •  • •  K_{5}\K_{2}

H_{4}  • • • • ≥ 1 \overline{cp}  \overline{cp} ≥ 1  Cannot be expanded

H′_{4}  • • • • 1 2 1  1  ^{•  • •  • •  K_{5}\K_{3}}

H′′_{4}  • • • • \overline{cp} \overline{cp}  \overline{cp} \overline{cp}  Cannot be expanded

References

[1] G-L.Chia, C-K.Lim. On Supercompact Graphs I: The Nucleus, Ars Combinatoria, 20, 101–110, (1985).

[2] R.C.Entringer, L.D.Gassman. Line-Critical Point Determining and Point Distinguishing Graphs, Discrete Mathematics, 10, 43–55, (1974).

[3] C-K.Lim. On Supercompact Graphs, Journal of Graph Theory, 2, 349– 355, (1978).

[4] J.P.McSorley. Constructing and Classifying Neighborhood Anti-Sperner Graphs, Submitted.

[5] T.D.Porter. Graphs with the Anti-Neighborhood Sperner Property, Journal of Combinatorial Mathematics and Combinatorial Computing, 50, 123–127, (2004).

[6] T.D.Porter, J.L.Yucas. Graphs whose Vertex-Neighborhoods are Anti-Sperner, Bulletin of the Institute of Combinatorics and its Applications, 44, 69–77, (2005).

[7] E.Prisner. Graph Dynamics, Pitman Research Notes in Mathematics Series 338. Longman, (1995).

[8] F.S.Roberts. Indifference Graphs, in: Proof Techniques in Graph Theory, (F.Harary ed.) Academic Press, 139–146, (1969).

[9] D.P.Sumner. Point Determination in Graphs, Discrete Mathematics, 5, 179–187, (1973).

[10] D.B.West. Introduction to Graph Theory, Prentice-Hall, (1996).