Constructing and Classifying Neighborhood Anti-Sperner Graphs

John P. McSorley, Department of Mathematics, Mailcode 4408, Southern Illinois University, Carbondale. IL 62901-4408. mcsorley60@hotmail.com

October 1, 2007

Abstract

For a simple graph G let N_{G}(u) be the (open) neighborhood of vertex u ∈ V (G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v ∈ V (G)\{u} with N_{G}(u) ⊆ N_{G}(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_{H}(u) ≠ N_{H}(v) when u ≠ v, for all u and v ∈ V (H).

In Porter and Yucas [3] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r = 0, 1, …, 6.

Keywords: Graph, Neighborhood, Distinct, Sperner, anti-Sperner, Classify.

1 Introduction and Main Results

We first give some definitions from Porter [2], Porter and Yucas [3], and Sumner [5]. Standard definitions of graph theory are from West [6].

Let F = {S_{1}, S_{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 open neighborhood of u, i.e., the set of vertices that u is adjacent to. Here we use ‘neighborhood’ for ‘open neighborhood’.

Let F(G) = {N_{G}(u) | u ∈ V (G)} be the family of neighborhoods of G. Then G is neighborhood anti-Sperner (NAS) if F(G) is anti-Sperner. Hence, in a NAS graph G, for every u ∈ V (G) there is a u^{p} ∈ V (G)\{u} such that N_{G}(u) ⊆ N_{G}(u^{p}). We say that u^{p} is a parent of u and note that u is not adjacent to u^{p}. Neighborhood anti-Sperner graphs were introduced by Porter in [2] where they were called ANS graphs, and studied further in Porter and Yucas [3].

A graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_{H}(u) ≠ N_{H}(v) when u ≠ v, for all u, v ∈ V (H).

Let H be an arbitrary graph with t vertices and let T_{1}, T_{2}, …, T_{t} be t arbitrary graphs. Using the notation of [3], the graph G = I(T_{1}, T_{2}, …, T_{t} : H) is the graph obtained from H by replacing vertex i with a copy of T_{i} for each i = 1, 2, …, t, and then if ij ∈ E(H) joining T_{i} to T_{j}. In Equation (1) Section 3 of [3] a characterization of regular NAS graphs is given which we reproduce here with a mix of their and our notations, where N_{ℓ} is the null graph with ℓ ≥ 1 vertices and no edges:

Let G be a regular NAS graph with reduced graph G_{≡} on t vertices with labels ℓ_{1}, ℓ_{2}, …, ℓ_{t}. Then G = I(N_{ℓ_{1}}, N_{ℓ_{2}}, …, N_{ℓ_{t}} : G_{≡}).

A direct result of our Theorem 3.2 is an extension of this result from regular NAS graphs to arbitrary NAS graphs. We comment on this after Theorem 3.2, and write this up formally below and in our Extensions and Conclusions (Section 5), as Theorem 5.1.

Theorem 5.1 Let G be a NAS graph with reduced graph G_{≡} on t vertices with labels ℓ_{1}, ℓ_{2}, …, ℓ_{t}. Then G = I(N_{ℓ_{1}}, N_{ℓ_{2}}, …, N_{ℓ_{t}} : G_{≡}).

Using this extension we give an Algorithm to construct all NAS graphs on a fixed number of n ≥ 2 vertices from labelled ND graphs on ≤ n − 1 vertices, and then an Algorithm to construct all connected NAS graphs on a fixed number of n ≥ 4 vertices from connected labelled ND graphs on ≤ n−2 vertices.

In [3] all connected r-regular NAS graphs were found and classified for r = 2, 3, and 4. In Section 4 we simplify this classification and extend it to r = 5 and 6. We also extend Theorem 2.11 of [3], see Theorem 5.2 in Section 5. Section 2 next contains preparatory material.

Some results of [3] concern infinite NAS graphs, however in this paper we only consider finite NAS graphs.

2 Neighborhood distinct graphs, labelled graphs, miscellaneous,

This Section contains preparatory and miscellaneous material required in later Sections.

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 neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_{H}(u) ≠ N_{H}(v) when u ≠ v, for all u, v ∈ V (H). Sumner [5] called such graphs point determining and proved the following Theorem that we write using our notation, (see Theorem 2 of [5]):

Let H be a ND graph with ≥ 2 vertices. Then there is a vertex w ∈ V (H) for which H − w is also ND.

The ND graphs with ≤ 3 vertices are: N_{1}, K_{2}, N_{1} ∪ K_{2}, and K_{3}.

Sumner’s result gives us:

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

 (1) List all non-isomorphic ND 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 neighborhoods
     of H_{t−1}.  We allow S = ∅.
 (3) Let w ∉ V (H_{t−1}) be a new vertex.  For each such H_{t−1} and S
     let H be the graph obtained by joining w to S:

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

 (4) Remove non ND graphs and then isomorphic copies of the remaining
     ND graphs from the list in (3).

We now have a complete list of ND graphs H on t vertices.

Example 1 We find all ND graphs with 4 vertices from the 2 ND graphs N_{1} ∪ K_{2} and K_{3} with 3 vertices. For each such graph there are 2^{3} − 3 = 5 subsets S, yielding 10 graphs at step (3). Removing non ND graphs and isomorphic copies of the remaining ND graphs leaves the 5 non-isomorphic ND graphs with 4 vertices:

[figure]

Fig. 1. All ND graphs with 4 vertices

We can then use these ND graphs on 4 vertices to construct all ND graphs on 5 vertices, ..... , and so on. Hence, for any t ≥ 1, we can construct all ND 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 labelisomorphic if there is a graph isomorphism between H and H′ that preserves vertex labels. So if in a label-isomorphism we have u ∈ V (H) ↔ u′ ∈ V (H′), then ℓ(u) = ℓ(u′).

If N_{G}(u) = N_{G}(v) for two different vertices u and v ∈ V (G) then we call u and v twins. We note that twins are non-adjacent. We denote a twin of u by u^{∗}. If u doesn’t have a twin then it is twinless. If H is ND then every vertex of H is twinless. Graphs that we call ND have also been considered in Kotlov and Lovász [1] under the name ‘twin-free’. In a NAS graph a vertex of maximum degree must have a twin. The smallest NAS graph is N_{2} with 2 vertices, and the smallest connected NAS graph is K_{2,2} with 4 vertices.

3 Constructing NAS Graphs from labelled ND Graphs

In this Section we show how to construct all NAS graphs G on n ≥ 2 vertices from labelled ND graphs H on ≤ n − 1 vertices, and all connected NAS graphs G on n ≥ 4 vertices from connected labelled ND graphs H on ≤ n−2 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 twin of u, we normally write a twin as u^{∗} provided that it is distinct from u. We let t denote the number of equivalence classes of V (G) or of G under ≡; and denote the classes themselves by U_{1}, U_{2}, …, U_{t}, where |U_{i}| = ℓ_{i} for each i = 1, 2, …, t.

Theorem 3.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] = N_{|U|},

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

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

Proof. (i) If |U| = 1 then clearly G[U] = N_{|U|}. So assume that |U| ≥ 2 and let u and u^{∗} be two arbitrary distinct vertices in U. If uu^{∗} ∈ E(G) then u ∈ N_{G}(u^{∗}) = N_{G}(u), a contradiction since G is simple. Hence uu^{∗} ∉ E(G), and so G[U] = N_{|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). Now 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] = N_{|U|} ∨ N_{|V |}. The converse is clear. (iii) Straightforward.

So, in any graph G, and for any two distinct equivalence classes U and V either G[U ∪ V] = N_{|U|} ∨ N_{|V |} or G[U ∪ V] = N_{|U|} ∪ N_{|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}] = N_{|U_{i}|}∨N_{|U_{j}|}},

where vertex U_{i} has been labelled with ℓ_{i} for each i. Note that |V (G)| = ∑_{i=1}^{t} ℓ_{i}.

We call G_{≡} the reduced graph of G. An unlabelled version of G_{≡} is the host graph from Section 3 of [3], although here G was assumed to be a regular NAS graph.

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 expanding each vertex u as follows: replace u with the ℓ(u) vertices from exp(u) = {x_{1}, x_{2}, …, x_{ℓ(u)}}, the expansion set of u, where H^{↑}[exp(u)] = N_{ℓ(u)}. If uv ∈ E(H) then let H^{↑}[exp(u)∪exp(v)] = N_{ℓ(u)}∨N_{ℓ(v)}, and if uv ∉ E(H) then let H^{↑}[exp(u) ∪ exp(v)] = N_{ℓ(u)} ∪ N_{ℓ(v)}. (The graph H^{↑} is sometimes referred to as the blow-up of H.)

From the above two constructions we have:

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

We obtain our first result by applying Theorem 3.2 to arbitrary NAS graphs. This is an extension of the result of Equation (1) Section 3 of [3] from regular NAS graphs to arbitrary NAS graphs. We write this up formally in our Extensions and Conclusions (Section 5), see Theorem 5.1.

Now we proceed with the main topic of this Section.

Given an arbitrary graph G, as we reduce to G_{≡} we identity vertices with the same neighborhood, so G_{≡} should be ND:

Theorem 3.3 Let G be an arbitrary graph. Then G_{≡} is ND.

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

In the first case let u ∈ U then N_{G}(u) = ⋃_{k=1}^{d} U_{k}. Similarly, if v ∈ V then N_{G}(v) = ⋃_{k=1}^{d} U_{k}. Hence N_{G}(u) = N_{G}(v) so u ≡ v, a contradiction. The proof is similar when N_{G_{≡}}(U) = N_{G_{≡}}(V) = ∅.

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

Lemma 3.4 Let H be a labelled ND graph with t ≥ 1 vertices. Then H^{↑} has t equivalence classes under ≡.

Proof. Let H^{↑} have s equivalence classes under ≡, we 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 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 ND, 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 = v is allowed). 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^{↑}. (A slight modification of this argument is required if w = v.) Hence t ≤ s.

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) for some a ≠ b, 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 parentless if u does not have a parent. And if u does have a parent u^{p} with N_{G}(u) ⊂ N_{G}(u^{p}) then we call u^{p} a proper parent of u.

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

Lemma 3.5

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

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

Proof. (i) In G since u^{p} is a proper 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. Furthermore if U^{p}U ∈ E(G_{≡}) then u^{p}u ∈ E(G), a contradiction, hence U^{p}U ∉ E(G_{≡}), i.e., U^{p} ∉ N_{G_{≡}}(U).

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

The following result deals with both connected and disconnected NAS graphs.

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

Proof. First let G be a NAS 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 3.3 shows that G_{≡} is a labelled t vertex ND graph. From Lemma 3.5(ii) all parentless vertices in G_{≡} have label ≥ 2.

Conversely suppose that G_{≡} is a labelled t vertex ND graph in which all parentless vertices have label ≥ 2. From Theorem 3.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 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 parentless and so U has a parent U^{p}, and then u_{j} has a parent in exp(U^{p}). If ℓ(U) ≥ 2, then each u_{j} has a twin, which is a parent. Hence, in either case, u = u_{j} has a parent, and so G is NAS. Furthermore, since G_{≡} is a t vertex ND graph then, from Lemma 3.4, the graph G = (G_{≡})^{↑} has t equivalence classes under ≡.

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 NAS graphs G from labelled ND graphs H. It relies on Theorem 3.6: we denote G_{≡} by H, and consider all possible labelled ND graphs H, and then construct all possible NAS 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 NAS with n ≥ 2 vertices then a vertex u ∈ V (G) of maximum degree must have a twin, so |U| ≥ 2. So some ℓ_{i} ≥ 2, and since n = ∑_{i=1}^{t} ℓ_{i}, then t ≤ n − 1.

Algorithm NAS Graphs Four step algorithm to construct all NAS graphs G on a fixed number of n ≥ 2 vertices from all labelled ND graphs H on t ≤ n − 1 vertices.

For each fixed t = 1, 2, . . . , n − 1:
 (1) By repeated use of Algorithm ND Graphs list all non-isomorphic
     ND graphs H_{t} on t vertices.
 (2) List all partitions P_{t} of n with t parts.
 (3) For each 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 parentless vertices have label ≥ 2.
 (4) For each labelled graph H_{t} construct G = H_{t}^{↑}.

Because of Theorem 3.6 we have a complete list of NAS graphs G with n vertices, with no repeated G.

We are primarily interested in connected NAS graphs and so we now modify Algorithm NAS Graphs to generate connected NAS graphs; we require three more results.

Lemma 3.7 Let G be an arbitrary graph. Then G is connected with ≥ 2 vertices if and only if G_{≡} is connected with ≥ 2 vertices.

Proof. Let G be connected with ≥ 2 vertices, and let uv ∈ E(G). Then, since u ∉ N_{G}(u) and u ∈ N_{G}(v), so N_{G}(u) ≠ N_{G}(v), and so G_{≡} has ≥ 2 vertices. 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.

Now any NAS graph G has ≥ 2 vertices, so using Lemma 3.7 we have the following ‘connected’ version of Theorem 3.6:

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

The smallest connected NAS graph is K_{2,2} which has t = 2 equivalence classes under ≡, each of size 2. In fact we have:

Lemma 3.9 Let G be a connected NAS graph with t equivalence classes under ≡. Then t ≥ 2, and G has at least two equivalence classes each of size ≥ 2.

Proof. Let G be a connected NAS graph and let u ∈ V (G) be a vertex of maximum degree Δ, then u has a twin. So |U| ≥ 2, and U is the first equivalence class of size ≥ 2.

Since G is connected and NAS then |V (G)| ≥ 4, and so Δ ≠ 0, i.e., N_{G}(u) ≠ ∅. So let v ∈ N_{G}(u) have the maximum degree amongst all vertices in N_{G}(u). Let v^{p} be a parent of v, clearly v^{p} ∈ N_{G}(u). Now deg(v) ≤ deg(v^{p}), but v has maximum degree amongst all vertices in N_{G}(u), so deg(v) = deg(v^{p}) and v^{p} is a twin of v. Hence |V | ≥ 2, and clearly V ≠ U, so V is another equivalence class of size ≥ 2. And also t ≥ 2.

So if G is a connected NAS graph with n ≥ 4 vertices then t = |V (G_{≡})| ≥

2. Also t ≤ n − 2 because there are at least two labels on V (G_{≡}) that are each ≥ 2.

Now, using Theorem 3.8, we have Algorithm Connected NAS Graphs below; it constructs all connected NAS graphs G on a fixed number n ≥ 4 of vertices, with no repeated G.

Algorithm Connected NAS Graphs Four step algorithm to construct all connected NAS graphs G on a fixed number of n ≥ 4 vertices from all connected labelled ND graphs H on 2 ≤ t ≤ n − 2 vertices.

For each fixed t = 2, 3, . . . , n − 2:
 (1) By repeated use of Algorithm ND Graphs, modified to generate
     connected ND graphs, list all non-isomorphic connected ND graphs
     H_{t} on t vertices.
 (2) List all partitions P_{t} of n with t parts.
 (3) For each 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 parentless vertices have label ≥ 2.
 (4) For each labelled graph H_{t} construct G = H_{t}^{↑}.

Example 2 As an illustration of Algorithm Connected NAS Graphs we construct all connected NAS graphs G on n = 6 vertices. We need only consider all connected ND graphs H_{t} on t = 2, 3, or 4 vertices. These H_{t} are shown in the left column of Fig. 2, suitably labelled. The last 2 such graphs have ≥ 3 parentless vertices, indicated by \overline{p}, each of which require a label of ≥ 2, this is not possible since the sum of all labels must equal 6.

\begin{matrix}H & G & ND & NAS & H_{2} & • & • & 2 & 4 \\ • & • & • & • & • & • & K_{2,4} \end{matrix}

H′_{2}  •  • 3  3  ^{• • •  • • •  K_{3,3}}

H_{3}  • • • 2 2 2  ^{• • • • • •  K_{2,2,2}}

H_{4}  • • • • 12  21  ^{• • • • • •  K_{3,3} − e}

H′_{4}  ≥ 1 • • • • p̄ p̄  p̄  cannot be expanded

H′′_{4}  • • • • p̄ p̄ p̄ p̄  cannot be expanded Fig. 2. All connected NAS graphs G on 6 vertices, illustrating Algorithm Connected NAS Graphs for n = 6

4 Classifying r-regular NAS Graphs

In [3] all connected r-regular NAS graphs were found and classified for r = 2, 3, and 4, (Theorems 2.5, 2.7, and 3.5, respectively). Here we simplify the proofs of these Theorems, and extend the classification to r = 5 and 6.

We first require the following Lemma:

Lemma 4.1 Let G be an arbitrary graph with equivalence relation ≡. Then, for every u ∈ V (G), the neighborhood N_{G}(u) is a union of equivalence classes of ≡.

Proof. For any v ∈ V (G) denote 2 arbitrary members of the equivalence class [v] by v′ and v′′. If v′ ∈ N_{G}(u) then u ∈ N_{G}(v′) = N_{G}(v′′), and so v′′ ∈ N_{G}(u) and then [v] ⊆ N_{G}(u) since v′′ is arbitrary. Hence, if N_{G}(u) contains a part of an equivalence class then it contains the whole class, and so it is a union of whole equivalence classes, as required.

Let H be an arbitrary labelled graph with label ℓ(u) ≥ 1 on each vertex u ∈ V (H), and with no isolated vertices. If distinct vertices u and v ∈ V (H) are adjacent we write u ∼ v. Define the weight of u as wt(u) = ∑_{v∼u} ℓ(v). For r ≥ 1 we say that H is r-weight-regular if wt(u) = r for all u ∈ V (H).

Note that |V (H)| ≥ 2. In the remainder of this Section, when H is replaced by G_{≡}, we will always assume that |V (G_{≡})| ≥ 2, even though this may not be explicitly mentioned.

Theorem 4.2 Let G be an arbitrary graph and let r ≥ 1. Then G is r-regular if and only if G_{≡} is r-weight-regular.

Proof. As usual let G have t equivalence classes under ≡ given by U_{1}, U_{2}, …, U_{t}.

First let G be r-regular. Fix i with 1 ≤ i ≤ t and let u ∈ U_{i} and N_{G}(u) = {v_{1}, v_{2}, …, v_{r}}. From Lemma 4.1 above N_{G}(u) is a union of s equivalence classes, say N_{G}(u) = ⋃_{k=1}^{s} V_{k}. So deg(u) = r = ∑_{k=1}^{s} |V_{k}|. Now, in G, vertex u ∼ v for (every) v ∈ V_{k}, for all k = 1, 2, …, s. So, in G_{≡}, vertex U_{i} ∼ V_{k}, for all k = 1, 2, …, s. Now the labels on vertices V_{k} are ℓ(V_{k}) = |V_{k}|. Hence, in G_{≡}, we have wt(U_{i}) = ∑_{k=1}^{s} ℓ(V_{k}) = ∑_{k=1}^{s} |V_{k}| = r. So, since i is arbitrary, then G_{≡} is r-weight-regular.

Conversely suppose that G_{≡} is r-weight-regular, let the arbitrary vertex U ∈ V (G_{≡}) have label ℓ(U) = |U| ≥ 1. When constructing G = (G_{≡})^{↑} from G_{≡} we replace vertex U with the ℓ(U) vertices from exp(U) = {u_{1}, u_{2}, …, u_{ℓ(U)}}. Then, in G, for any u_{j} with j = 1, 2, …, ℓ(U), we have deg(u_{j}) = ∑_{V ∼U} |V | = ∑_{V ∼U} ℓ(V) = wt(U) = r. Since U ∈ V (G_{≡}) is arbitrary and u_{j} ∈ U is also arbitrary, then G is r-regular.

Theorem 4.3 Let G be an arbitrary graph. Then G is a connected rregular NAS graph if and only if G_{≡} is a connected ND r-weight-regular graph, in which each label ℓ(U) satisfies 2 ≤ ℓ(U) ≤ r.

Proof. If G is a connected r-regular NAS graph then every vertex u is a vertex of maximum degree and so has a twin, and so each |U| ≥ 2, thus each ℓ(U) ≥ 2 in G_{≡}. Furthermore by Lemma 3.7 and Theorem 4.2 the graph G_{≡} is a connected ND r-weight-regular graph. Noting that in a r-weight-regular graph each label must be ≤ r, then, in G_{≡}, each label ℓ(U) satisfies 2 ≤ ℓ(U) ≤ r. The proof of the converse uses the same results.

Corollary 4.4 Let G be a connected r-regular NAS graph. Then r ≥ 2.

Proof. From Theorem 4.3 each label on G_{≡} is ≥ 2. Hence r ≥ 2.

From Theorem 4.3, if G is a connected r-regular NAS graph then the labels on G_{≡} must come from L = {2, 3, …, r}. In the following G_{≡} is a connected ND r-weight-regular graph. Before we start the classification of connected r-regular NAS graphs for r = 0, 1, …, 6 we have two Observations:

(1) If label r is used on G_{≡} then G_{≡} must be [figure: r; r; .] So G = [figure: r; r; ↑; = K_{r,r},] is the unique connected r-regular NAS graph in which G_{≡} has a label r.

(2) Label r − 1 cannot be used on G_{≡} since, in order to make G_{≡} r-weight-regular, we would then require label 1, but 1 ∉ L.

In the following we classify all connected r-regular NAS graphs G for a fixed r = 0, 1, …, 6 by first finding all connected labelled ND r-weight-regular graphs G_{≡}, in which each label ℓ(U) satisfies 2 ≤ ℓ(U) ≤ r, and then using Theorem 4.3.

r = 0 or 1 From Corollary 4.4 there are no connected r-regular NAS graphs for r = 0 or 1. r = 2 L = {2} = {r}. So all labels on G_{≡} must be r = 2. Hence, from Observation (1), G = K_{2,2} is the unique connected 2-regular NAS graph.

r = 3 L = {2, 3} = {r−1, r}. From from Observations (1) and (2) G = K_{3,3} is the unique connected 3-regular (cubic) NAS graph.

r = 4 L = {2, 3, 4} = {2, r − 1, r}. If label r = 4 is used then G = K_{4,4}. Clearly if only label 2 is used on G_{≡}, a connected ND 4 = \underbrace{2 + 2}_{2}-weight-

regular graph, then G_{≡} must be 2-regular. So G_{≡} is the a-cycle, C_{a}, where a ≥ 3 and a ≠ 4 since C_{4} is not ND, with each vertex having label 2. But note that if we label each vertex of C_{4} with 2 we get C_{4}^{↑} = K_{4,4}. Hence the only connected 4-regular NAS graphs are G = C_{a}^{↑} where each vertex in C_{a} has label 2, for all a ≥ 3.

Also note that G has 2a vertices so there are no connected 4-regular NAS graphs with an odd number of vertices, see Corollary 3.6 of [3].

r = 5 L = {2, 3, 4, 5} = {2, 3, r −1, r}. If label r = 5 is used then G = K_{5,5}. Otherwise G_{≡} is a connected ND 5 = \underbrace{2 + 3}_{2}-weight-regular graph, hence,

again, G_{≡} is 2-regular. Indeed G_{≡} is the 4a-cycle, C_{4a}, for a ≥ 2. The labelling on each ‘block’ of 4 clockwise-consecutive vertices in C_{4a} is {2, 2, 3, 3} repeated a times until all 4a vertices are labelled. The case a = 1 gives C_{4} which is not ND, however C_{4} labelled with {2, 2, 3, 3} gives C_{4}^{↑} = K_{5,5}. So the only connected 5-regular NAS graphs are G = C_{4a}^{↑} with the above labelling, for all a ≥ 1. The example below shows a = 1.

•  • •  • 3  3C_{4}  2 2  • • •  • • • K_{5,5} • •  • •

r = 6 L = {2, 3, 4, 5, 6} = {2, 3, 4, r − 1, r}. If label r = 6 is used then we get K_{6,6}.

Since label 5 cannot be used on G_{≡} we can only use labels from L′ = {2, 3, 4}. So let G_{≡} be a connected ND 6-weight-regular graph with labels from L′ = {2, 3, 4}. Let U ∈ V (G_{≡}). Then U has label ℓ(U) ∈ L′, and since wt(U) = 6 there are only three possibilities for labelling U and its neighbors:

•

•

•

ℓ(U)

2

4

(a)

•

•

•

ℓ(U)

3

3

(b)

Fig. 3. Three possibilities for labelling U and its neighbors

•

•

•

ℓ(U) •

2

2

2

(c)

Let a [2, 3]-regular graph be a graph in which every vertex has degree 2 or 3, and with at least one vertex of degree 2 and at least one of degree 3. Then from Figs. 3(a), (b), and (c) any G_{≡} must be 2-regular, or cubic, or [2, 3]-regular.

In the following when we say that G_{≡} is labelled with set L′′, then every label in L′′ must be used at least once. We consider L′′ where ∅ ≠ L′′ ⊆ L′.

The use of label 3 ∈ L′′ is restricted by the following Lemma. Let d(U, V) be the length of a shortest path between vertices U and V in G_{≡}.

Lemma 4.5 Let G_{≡} be labelled with the set L′′ where 3 ∈ L′′, and let U and V be distinct vertices of G_{≡} with UV ∈ E(G_{≡}).

(i) Then either ℓ(U) = 3 or ℓ(V) = 3 (or both).

(ii) If both ℓ(U) = ℓ(V) = 3. Then L′′ = {3}.

Proof. Recall that G_{≡} is connected.

(i) Since 3 ∈ L′′ then 3 must be used as a label in G_{≡}, so let W ∈ V (G_{≡}) have ℓ(W) = 3. If W = U or V then we are finished. Otherwise every second vertex on any path starting at W must have label 3, see Fig. 3(b). So, if d(W, U) is even, then ℓ(U) = 3. Or if d(W, U) is odd then there is a path of even length d(W, U) ± 1 from W to V, hence ℓ(V) = 3. (ii) Let X be any vertex in V (G_{≡}). Then either there is a path of even length from U to X or from V to X. Hence ℓ(X) = 3. So every vertex has label 3, i.e., L′′ = {3}.

Now we are ready to consider the seven cases for L′′ where ∅ ≠ L′′ ⊆ {2, 3, 4}. We will determine all possible G_{≡}, connected ND 6-weight-regular graphs. Then all G, connected 6-regular NAS graphs, are given by G = (G_{≡})^{↑}. L′′ = {2} G_{≡} is any connected ND cubic graph, with label 2 on every vertex.

L′′ = {3} G_{≡} is a connected ND 2-regular graph. So G_{≡} = C_{a}, where a ≥ 3, and a ≠ 4, with each vertex having label 3. (As usual note that a labelled C_{4}^{↑} = K_{6,6}.) L′′ = {4} or {3, 4} No G_{≡} are possible since a label of 2 is needed with the label of 4 to create a vertex with weight 6. L′′ = {2, 3} For this case we show that there is a one-to-one correspondence between the set of G_{≡} and the set of simple connected cubic graphs S.

Here G_{≡} is a [2, 3]-regular connected ND 6-weight-regular graph labelled with L′′ = {2, 3}. Let U ∈ V (G_{≡}). Suppose that ℓ(U) = 2 but that U has degree 3. Then this contradicts Fig. 3(c) and Lemma 4.5(i), hence U has degree 2. Conversely, let vertex U have degree 2, so, from Fig. 3(b) and Lemma 4.5(ii), we have ℓ(U) = 2. So a vertex in G_{≡} has label 2 if and only if it has degree 2, and has label 3 if and only if it has degree 3.

Let UV ∈ E(G_{≡}) be arbitrary. Then, from Lemma 4.5(i) and (ii), without loss of generality let ℓ(U) = 2 and ℓ(V) = 3. So, for any edge in G_{≡}, one end-vertex has label 2 and the other has label 3. Hence G_{≡} is a bipartite graph with all vertices U with ℓ(U) = 2 in the first part, call this set of vertices U; and all vertices V with ℓ(V) = 3 in the second part, call this set V.

From above each vertex in U has degree 2 and each vertex in V has degree 3. Counting edges gives 2|U| = 3|V|. So |V| is even, set |V| = 2a, then |U| = 3a, where a ≥ 2. (If a = 1 then G_{≡} = K_{3,2} which is not ND; but, as usual, a labelled K_{3,2}^{↑} = K_{6,6}.)

Let U = {U_{1}, U_{2}, …, U_{3a}} and V = {V_{1}, V_{2}, …, V_{2a}}. Now construct a graph S with vertex-set V (S) = V, and with edge V_{j}V_{j′} (j ≠ j′) whenever there is a vertex U_{i} ∈ U with N_{G_{≡}}(U_{i}) = {V_{j}, V_{j′}}. So S has 2a vertices and 3a edges. Now S has no loops, and also no multi-edges because G_{≡} is ND, so S is simple. And S is cubic because the degree of any V_{j} in G_{≡} is 3. Finally S is connected because G_{≡} is connected. Thus S is a simple connected cubic graph on 2a vertices.

Conversely, let S be a simple connected cubic graph on the 2a vertices V = {V_{1}, V_{2}, …, V_{2a}}, where a ≥ 2. Then S has 3a edges E(S) = {e_{1}, e_{2}, …, e_{3a}}. Put a new vertex U_{i} on edge e_{i} for each i = 1, 2, …, 3a. Let B be the bipartite graph with vertex sets U = {U_{1}, U_{2}, …, U_{3a}} as its first part and V as its second part. Then B is [2, 3]-regular, and, because S is connected, then B is connected. And clearly B is ND. Now label each vertex U_{i} with 2, and each vertex V_{j} with 3. Then B is a 6-weight-regular graph. Thus B is a [2, 3]-regular connected ND 6-weight-regular graph, i.e., B is an example of a G_{≡}. We denote B by Bis(S), because we have ‘bisected’ each edge in S to form B.

Thus there is a one-to-one correspondence between the set of G_{≡} and the set of simple connected cubic graphs S. L′′ = {2, 3, 4} Here we show that the structure of G_{≡} is quite restricted, but show that infinitely many such G_{≡} exist.

By a similar argument in the above L′′ = {2, 3} case, G_{≡} is a bipartite graph. Its first part consists of all vertices of degree 2 and labels 2 or 4; let there be a ≥ 1 vertices U with label 2 and b ≥ 1 vertices U′ with label 4. Its the second part consists of vertices with label 3; let there be c ≥ 0 vertices V with degree 3 and d ≥ 0 vertices V′ with degree 2, where c + d ≥ 1. See Fig. 4.

a U 2

2 .. .

•

• 3

3 .. .

•

•

c = 2/3(a − b) V

b U^′ 4

4 .. .

•

• 3

3 .. .

•

•

d = 2b V^′

Fig. 4. The graph G_{≡}(a, b)

We show that d = 2b and c = \frac{2}{3}(a − b). Consider the 2b edges incident to the b vertices in U′. From Fig. 3 each of these 2b edges is incident to a vertex in V′. Now a vertex in V′ cannot be adjacent to two vertices in U′ since such a vertex would then have weight 8. So these 2b edges must be incident to 2b distinct vertices in V′, hence 2b ≤ d. If d > 2b then V′ contains a vertex that is not adjacent to any vertex in U′, so it must be adjacent to two vertices in U and so have weight 4, a contradiction. Hence d ≤ 2b, and so d = 2b. Then counting edges in two different ways gives c = \frac{2}{3}(a − b), so a ≥ b ≥ 1 and a ≡ b (mod 3).

To summarize: G_{≡} is a connected ND bipartite graph. The first part consists of a ≥ 1 vertices with degree 2 and label 2 (U), and b ≥ 1 vertices with degree 2 and label 4 (U′). The second part consists of \frac{2}{3}(a − b) ≥ 0 vertices with degree 3 and label 3 (V), and 2b ≥ 2 vertices with degree 2 and label 3 (V′), where a ≥ b ≥ 1 and a ≡ b (mod 3). Furthermore, the 2b edges incident to the b vertices in U′ are incident to the 2b vertices in V′, in a one-to-one fashion. We denote such a graph by G_{≡}(a, b).

If a = b then G_{≡}(a, a) is 2-regular. So G_{≡}(a, a) = C_{4a} for a ≥ 2 with labelling {2, 3, 4, 3} repeated a times around the cycle.

If a > b then G_{≡}(a, b) is [2, 3]-regular. It doesn’t seem possible to explicitly describe all G_{≡}(a, b); we can, however, show that a G_{≡}(a, b) exists for all ordered pairs (a, b) with a > b ≥ 1 and a ≡ b (mod 3), except for (a, b) = (4, 1); see Theorem 4.9.

First we deal with the pairs (a, b) = (4, 1), (7, 1), and (5, 2). We omit the proof of the following Lemma, it involves straightforward exhaustive checking.

Lemma 4.6

(i) There does not exist a G_{≡}(4, 1).

(ii) There exists a unique G_{≡}(7, 1) up to label-isomorphism.

(iii) There exist two non-label-isomorphic G_{≡}(5, 2)’s, one with girth 6 and one with girth 8.

4 •  • 3 2 •  • 3 2 • 2 • 2 •  • 3 2 •  • 3 2 •  • 3 2 •  • 3 G_{≡}(7, 1) unique

4 • • 3 4 • • 3 2 • • 3 2 • • 3

2 •

2 • • 3 2 • • 3

G_{≡}(5, 2) girth 6

Fig. 5. Three small G_{≡}(a, b)

4 •  • 3 4 •  • 3 2 •  • 3 2 •  • 3 2 • 2 •  • 3 2 •  • 3 G_{≡}(5, 2) girth 8

Lemma 4.7 Suppose that there exists a G_{≡}(a, b) with a > b ≥ 1. Then

(i) there exists a G_{≡}(a + 1, b + 1),

(ii) there exists a G_{≡}(a + 3, b).

Proof. (i) Clearly any G_{≡}(a, b) must contain an edge [figure: 2; 3; .] Delete this edge and replace it with:

4 •  • 3 2 •  • 3 2 •  • 3

We now have a G_{≡}(a + 1, b + 1). (ii) In G_{≡}(a, b), as usual, let U = {U_{1}, U_{2}, …, U_{a}} where, from Lemma 4.6, we have a ≥ 5. And let V ∪V′ = \{V_{1}, V_{2}, …, V_{\frac{2}{3} (a+2b)}\}, where the \frac{2}{3}(a−b) ≥ 2 vertices from V are listed first; we have \frac{2}{3}(a + 2b) ≥ 6.

We first show that we can find two edges U′ V′ and U′′ V′′ where U′, U′′ ∈ U are distinct and V′, V′′ ∈ V ∪ V′ are distinct, such that U′ V′′ and U′′ V′ are non-edges.

Without loss of generality let U_{1}V_{1} be an edge of G_{≡}(a, b), and choose U_{1}V_{1} as the first edge U′ V′, i.e., let U′ = U_{1} and V′ = V_{1}. Now deg(U′) = 2, let N_{G_{≡}(a,b)}(U′) = {V′, V (1)} for some V (1) ∈ V ∪V′\{V′}. Also deg(V′) = 3 so, without loss of generality, let N_{G_{≡}(a,b)}(V′) = {U′, U_{2}, U_{3}}. Now consider U_{4} and let U′′ = U_{4}. Let N_{G_{≡}(a,b)}(U′′) = {V (2), V (3)}. At least one of V (2) or V (3) is distinct from V (1), say V (2) ≠ V (1), (and both are distinct from V′). So let V′′ = V (2). Then U′′ V′′ is an edge of G_{≡}(a, b), and U′ V′′ and U′′ V′ are non-edges. And ℓ(U′) = ℓ(U′′) = 2 and ℓ(V′) = ℓ(V′′) = 3.

Now let K be a copy of K_{3,2} with vertices {X_{1}, X_{2}, X_{3}} in the first part, each with label 2; and vertices {Y_{1}, Y_{2}} in the second part, each with label 3. In K ∪ G_{≡}(a, b) remove the 2 edges {X_{1}Y_{1}, U′ V′} and add the 2 edges {X_{1}V′, Y_{1}U′}, then remove the 2 edges {X_{2}Y_{2}, U′′ V′′} and add the 2 edges {X_{2}V′′, Y_{2}U′′}. See below where the removed edges are indicated by dashed lines.

U′′ 2 •  •V′′ 3 From G_{≡}(a, b) U′ 2 •  •V′ 3  G_{≡}(a + 3, b) } { X_{3} 2 • X_{2} 2 K_{3,2} = K { •  •Y_{2} 3 X_{1} 2 •  •Y_{1} 3

Then careful checking shows that this new graph is a G_{≡}(a + 3, b).

Lemmas 4.6(ii) and 4.7(ii) give:

Lemma 4.8 There exists a G_{≡}(a, 1) for all a ≥ 7 with a ≡ 1 (mod 3).

Theorem 4.9 There exists a G_{≡}(a, b) for all pairs (a, b) with a > b ≥ 1 and a ≡ b (mod 3), except for (a, b) = (4, 1).

Proof. First suppose that a − b = 3. Since a G_{≡}(4, 1) does not exist then a ≥ 5. Now start with a G_{≡}(5, 2) and apply Lemma 4.7(i) a total of a − 5 times to reach a G_{≡}(5 + (a − 5), 2 + (a − 5)) = G_{≡}(a, a − 3) = G_{≡}(a, b).

If a − b = 6, 9, 12, . . .. Then start with a G_{≡}(a − b + 1, 1) which exists by Lemma 4.8 and apply Lemma 4.7(i) a total of b−1 times to reach a G_{≡}(a, b).

Remark In the four cases L′′ = {2}, {3}, {2, 3} or {2, 3, 4} that yield a G_{≡} the labelling on G_{≡} is unique. That is, for any (unlabelled) G_{≡} constructed by the method shown for each case, there is a unique way, up to label-isomorphism, to label its vertices with L′′ to produce a 6-weight-regular graph, (see step (3) of Algorithm Connected NAS Graphs).

L′′ = {2, 4} In this final case we call a vertex with degree 3 a cubic vertex.

If G_{≡} is 2-regular then G_{≡} = C_{4a} for a ≥ 2 with labelling {2, 2, 4, 4} repeated a times around the cycle.

So let G_{≡} be a [2, 3]-regular connected ND 6-weight-regular graph with a ≥ 1 vertices of degree 2 and b ≥ 2 cubic vertices – so b is even – that has been labelled with L′′ = {2, 4}; denote such a graph by G_{≡}{a, b}. Similar to the previous case with L′′ = {2, 3, 4} an exact classification of G_{≡}{a, b} doesn’t seem possible. We can, however, determine all pairs {a, b} for which there exists a G_{≡}{a, b}; see Theorem 4.15.

First we need the following three results.

Lemma 4.10 In a G_{≡}{a, b} the number of vertices of degree 2 equals the sum of the degrees of all vertices with label 4, i.e.,

a = ∑_{ℓ(U)=4} deg(U).  (1)

Proof. If a vertex has degree 2 then it must have a neighbor with label 4, see Fig. 3(a). Conversely if a vertex has label 4 then all of its neighbors must have degree 2. Hence the result.

Now the following Corollary is immediate. Corollary 4.11 In a G_{≡}{a, b}

(i) if a is even then there are an even number of cubic vertices with label 4, (ii) if a is odd then there are an odd number of cubic vertices with label 4.

The next result concerns vertices in G_{≡}{a, b} with degree 2 and label 4. Lemma 4.12 In a G_{≡}{a, b}

(i) a vertex with degree 2 and label 4 is adjacent to exactly one other vertex with degree 2 and label 4,

(ii) vertices with degree 2 and label 4 occur in adjacent pairs, (iii) there are an even number of vertices with degree 2 and label 4. Proof. (i) Let U have degree 2 and label 4 and let U_{1} and U_{2} be the 2 neighbors of U, with ℓ(U_{1}) = 4 and ℓ(U_{2}) = 2. Then deg(U_{1}) = 2, and U_{1} is the required vertex which is adjacent to U with degree 2 and label 4. (ii) Now the other neighbor of U_{1} has label 2. So adjacent vertices U and U_{1} have as neighbors, excepting each other, a vertex with label 2. Thus U and U_{1} form an adjacent pair of vertices each with degree 2 and label 4. (iii) This now follows from (ii).

These three results are now used in the following non-existence proofs, given in order of increasing a. Theorem 4.13 Graphs G_{≡}{a, b} do not exist as indicated below:

(i) a = 1: there does not exist a G_{≡}{1, b} for all even b ≥ 2, (ii) a = 2: there does not exist a G_{≡}{2, b} for all even b ≥ 2, (iii) a = 3: there does not exist a G_{≡}{3, 2}, (iv) a = 4: there does not exist a G_{≡}{4, 2},

(v) a = 5: there does not exist a G_{≡}{5, b} for all even b ≥ 2, (vi) a = 4s + 1, for all s ≥ 2: there does not exist a G_{≡}{a, 2}.

Proof. (i) In a G_{≡}{a, b} we have a = ∑_{ℓ(U)=4} deg(U) from Equation (1). So in a G_{≡}{1, b} we have 1 = ∑_{ℓ(U)=4} deg(U) ≥ 2 since there is at least one vertex with degree 2 or 3 with label 4, a contradiction. (ii) Similarly, in a G_{≡}{2, b} we have 2 = ∑_{ℓ(U)=4} deg(U) so there is exactly 1 vertex with degree 2 and label 4, a contradiction to Lemma 4.12(iii). (iii) A G_{≡}{3, 2} has degree sequence 2^{3}3^{2}. There are only two such graphs with this degree sequence, G43 and G44 on p. 8 of [4]. But graph G43 cannot be labelled with L′′ to be 6-weight-regular, and G44 is not ND. (iv) Similar to (iii) using p. 10 of [4], see the graphs G127, G128, G129, and G130.

(v) From Equation (1) a G_{≡}{5, b} has exactly 1 cubic vertex with label 4, and so 1 vertex with degree 2 and label 4, again a contradiction to Lemma 4.12(iii). (vi) Since a = 4s + 1 is odd then, by Equation (1) and Corollary 4.11(ii), a G_{≡}{a, 2} has exactly 1 cubic vertex with label 4. Then Equation (1) becomes 4s + 1 = 3 + ∑_{{ℓ(U)=4 \atop deg(U)=2}} deg(U), and so G_{≡}\{a, 2\} has 2s − 1, an odd number,

of vertices with degree 2 and label 4, again a contradiction.

Now we show the existence of every G_{≡}{a, b} not mentioned in Theorem 4.13. We need:

Lemma 4.14 Suppose that there exists a G_{≡}{a, b} with a ≥ 3 and even b ≥ 2. Then

(i) there exists a G_{≡}{a + 4, b},

(ii) there exists a G_{≡}{a, b + 2}.

Proof. We first show that every G_{≡}{a, b} has, as a subgraph, at least one of the two following edge configurations: [figure: 2; 2; 2; 2; or; 2; 2; 2; ,] the degrees of the vertices involved are immaterial. Let U be a cubic vertex in G_{≡}{a, b} with neighbors {U_{1}, U_{2}, U_{3}}, so ℓ(U_{1}) = ℓ(U_{2}) = ℓ(U_{3}) = 2. If ℓ(U) = 2 then we have [figure: U_{1}; 2; U; 2; U_{2}; 2; .] If ℓ(U) = 4 then each U_{i} has degree 2 and label 2. So each U_{i} is adjacent to one vertex with label 2. If there are no edges in the induced graph G_{≡}{a, b}[U_{1}, U_{2}, U_{3}], then each U_{i} must be adjacent to some new vertex V_{i}. If V_{1} = V_{2} then we have [figure: U_{1}; 2; V_{1}; 2; U_{2}; 2; ;] or else we have [figure: U_{1}; 2; V_{1}; 2; U_{2}; 2; V_{2}; 2; .] Or with 1 edge in G_{≡}{a, b}[U_{1}, U_{2}, U_{3}], say edge U_{1}U_{2}, we must have [figure: U_{1}; 2; U_{2}; 2; U_{3}; 2; V_{3}; 2; .] Now 2 or 3 edges in G_{≡}{a, b}[U_{1}, U_{2}, U_{3}] are not possible. So, in every case, we have one of the two required edge configurations.

(i) In any G_{≡}{a, b} replace any edge [figure: 2; 2] with the path on 6 vertices, as shown below

•  • 2  2  ^{•  •  •  •  •  • 2 W_{1} W_{2} W_{3} W_{4} 2  4  4  2  2}

to produce a G_{≡}{a + 4, b}. The vertices {W_{1}, W_{2}, W_{3}, W_{4}} are the 4 new vertices with degree 2. (ii) In our G_{≡}{a, b} amend the edge configuration [figure: 2; 2; 2; 2] as shown below

• •  • • 22  2 2  ^{• •  • • •  • 22  22 W_{1} 2  W_{2} , 2}

or the edge configuration [figure: 2; 2; 2] as shown below

• • • 2 2 2  ^{• • • • • 2 2  2 W_{1} 2  W_{2} 2}

to produce a G_{≡}{a, b + 2}. The vertices {W_{1}, W_{2}} are the 2 new cubic vertices.

Now we give the main existence result:

Theorem 4.15 Graphs G_{≡}{a, b} exist as indicated below:

(i) a ≡ 0 (mod 4),

1. a = 4: there exists a G_{≡}{4, b} for all even b ≥ 4,

2. a ≥ 8: there exists a G_{≡}{a, b} for all even b ≥ 2;

(ii) a ≡ 1 (mod 4), a ≥ 9: there exists a G_{≡}{a, b} for all even b ≥ 4;

(iii) a ≡ 2 (mod 4), a ≥ 6: there exists a G_{≡}{a, b} for all even b ≥ 2;

(iv) a ≡ 3 (mod 4),

1. a = 3: there exists a G_{≡}{3, b} for all even b ≥ 4,

2. a ≥ 7: there exists a G_{≡}{a, b} for all even b ≥ 2.

Proof. (i) 1. a ≡ 0 (mod 4), a = 4: By Theorem 4.13(iv) a G_{≡}{4, 2} does not exist. A G_{≡}{4, 4} is shown on the left below:

•  • • • •  • • • 4  4 2 2 2  2 2 2 G_{≡}{4, 4} unique  ^{• • •  • • • • • • • 2  2 2  2 4  4 2 4  4 2 G_{≡}{8, 2}}

Then using this G_{≡}{4, 4} as a starter we can construct a G_{≡}{4, b} for all even b ≥ 4 by applying Lemma 4.14(ii) a total of (b − 4)/2 times.

2. a ≡ 0 (mod 4), a ≥ 8: A G_{≡}{8, 2} is shown on the right above, and using this as a starter we can construct a G_{≡}{a, b} for all a ≥ 8 and even b ≥ 2 by applying Lemma 4.14(i) (a−8)/4 times, followed by Lemma 4.14(ii) (b − 2)/2 times. (ii) a ≡ 1 (mod 4), a ≥ 9: By Theorem 4.13(i) and (v) graphs G_{≡}{1, b} and G_{≡}{5, b} for all even b ≥ 2 do not exist; and by (vi) a G_{≡}{9, 2} does not exist. A G_{≡}{9, 4} is:

•

•

•

•

•

•

•

•

• • • • •

2 2

G_{≡}{9, 4}  4  4

2 2

2 2 4 2 2

2

And using this G_{≡}{9, 4} as a starter we can construct a G_{≡}{a, b} for all a ≥ 9 and even b ≥ 4 by using Lemma 4.14(i) (a − 9)/4 times, followed by Lemma 4.14(ii) (b − 4)/2 times. (iii) a ≡ 2 (mod 4), a ≥ 6: By Theorem 4.13(ii) graphs G_{≡}{2, b} for all even b ≥ 2 do not exist; a G_{≡}{6, 2} is:

•

• •

• • •

• •

G_{≡}{6, 2} 4

2 2 4 2 2

2 2

And using this G_{≡}{6, 2} as a starter we can construct a G_{≡}{a, b} for all a ≥ 6 and even b ≥ 2 from (a − 6)/4 iterations of Lemma 4.14(i), followed by (b − 2)/2 iterations of Lemma 4.14(ii). (iv) 1. a ≡ 3 (mod 4), a = 3: By Theorem 4.13(iii) a G_{≡}{3, 2} does not exist. A G_{≡}{3, 4} is shown on the left below:

•  • • •  • •  • 2  4  2 2 2  2 2 G_{≡}{3, 4} unique  ^{• • •  •  • • • • • 2  4 422 2  2 4  2 G_{≡}{7, 2}}

Then using this G_{≡}{3, 4} as a starter we can construct a G_{≡}{3, b} for all even b ≥ 4 by applying Lemma 4.14(ii) (b − 4)/2 times.

2. a ≡ 3 (mod 4), a ≥ 7: A G_{≡}{7, 2} is shown on the right above, and using this we can construct a G_{≡}{a, b} for all a ≥ 7 and even b ≥ 2 by applying Lemma 4.14(i) (a−7)/4 times, followed by Lemma 4.14(ii) (b−2)/2 times.

Finally, we summarize the r = 6 case:

Theorem 4.16 Let G be a NAS graph. Then G = (G_{≡})^{↑} is connected and 6-regular if and only if G_{≡} is

(i) any connected ND cubic graph, with label 2 on every vertex, or

(ii) the cycle C_{a} for a ≥ 3, with label 3 on every vertex, or

(iii) any graph Bis(S) where S is a simple connected cubic graph, with label 2 on the new vertices and label 3 on the (old) vertices of S, or

(iv) 1. the cycle C_{4a} for a ≥ 2, with labelling {2, 3, 4, 3} repeated cyclically on the vertices, or

2. any graph G_{≡}(a, b) for all pairs (a, b) with a > b ≥ 1 and a ≡ b (mod 3), except for (a, b) = (4, 1), labelled as in Fig. 4, or

(v) 1. the cycle C_{4a} for a ≥ 2, with labelling {2, 2, 4, 4} repeated cyclically on the vertices, or

2. any graph G_{≡}{a, b} from Theorem 4.15.

5 Extensions and Conclusions

Recall from Section 1 and [3] that if H is an arbitrary graph with t vertices and T_{1}, T_{2}, …, T_{t} are also arbitrary then the graph G = I(T_{1}, T_{2}, …, T_{t} : H) is obtained from H by replacing vertex i with a copy of T_{i} for each i = 1, 2, …, t, and then if ij ∈ E(H) joining T_{i} to T_{j}.

Our Theorem 3.2 applied to NAS graphs gives:

Theorem 5.1 Let G be a NAS graph with reduced graph G_{≡} on t vertices with labels ℓ_{1}, ℓ_{2}, …, ℓ_{t}. Then G = I(N_{ℓ_{1}}, N_{ℓ_{2}}, …, N_{ℓ_{t}} : G_{≡}).

The main result of Section 3 of [3] (Equation (1)) is our Theorem 5.1 applied to regular NAS graphs. Thus we have extended this result from regular NAS graphs to arbitrary NAS graphs G. We then used this extension to give two Algorithms for constructing all NAS graphs and all connected NAS graphs G from ND graphs H. The concept of a r-weight-regular-graph was then introduced to extend the classification of connected r-regular NAS graphs to r = 5 and 6.

Now we extend Theorem 2.11 of [3], quoted here for convenience with slight notational changes:

Let H be an arbitrary graph with t vertices and let T_{1}, T_{2}, …, T_{t} be a collection of t NAS graphs. Then G = I(T_{1}, T_{2}, …, T_{t} : H) is a NAS graph.

In our Section 3 we distinguished between vertices in G_{≡} with and without a parent. We extend Theorem 2.11 of [3] by noting that only a parentless vertex in H need be replaced with a NAS graph to obtain a NAS graph G. Vertices with a parent in H need not be replaced, or, equivalently, they can be ‘replaced’ with the non-NAS graph N_{1} or a NAS graph T.

Theorem 5.2 Let H be an arbitrary graph with t vertices {u_{1}, u_{2}, …, u_{t}} and let T_{1}, T_{2}, …, T_{t} be a collection of t NAS graphs. Then the graph G = I(T_{1}, T_{2}, …, T_{t} : H) in which, for each i = 1, 2, …, t, if u_{i} is parentless in H then it is replaced by T_{i}, or if u_{i} has a parent in H then either it is replaced by N_{1} or by T_{i}, is a NAS graph.

Proof. The proof follows the proof of Theorem 2.11 of [3] except when u_{i} has a parent u_{j} in H and is replaced by N_{1} in forming G. Then N_{H}(u_{i}) ⊆ N_{H}(u_{j}) and so N_{G}(u_{i}) ⊆ N_{G}(x) for any x ∈ V (T_{j}), (where V (T_{j}) = {u_{j}} if u_{j} itself is also replaced by N_{1}).

As an illustration of this extension of Theorem 2.11 of [3] we consider the 6 vertex NAS graph K_{3,3} − e. Using Theorem 2.11 of [3] it is not possible to construct K_{3,3} − e from a graph with fewer vertices except in the trivial manner: K_{3,3} − e = I(K_{3,3} − e : N_{1}), from the one vertex graph N_{1}. Now using Theorem 5.2 above we can construct K_{3,3} − e from the 4 vertex graph K_{2,2} − e. Let V (K_{2,2} − e) = {u, u^{p}, v, v^{p}} in this order, shown below. Then K_{3,3} − e = I(N_{1}, N_{2}, N_{1}, N_{2} : K_{2,2} − e). So the parentless vertices u^{p} and v^{p} are each replaced by the NAS graph N_{2}, and the vertices u and v with parents are each replaced by N_{1}.

u •  • v up •  • vp K_{2,2} − e  ^{u •  • v x_{2} •  • y_{2} x_{1} •  • y_{1} K_{3,3} − e}

Further we note that K_{2,2} − e suitably labelled with {1, 2, 1, 2} is (K_{3,3} − e)_{≡}, so this example is also an illustration of Theorem 5.1 above, i.e., K_{3,3} − e = I(N_{1}, N_{2}, N_{1}, N_{2} : (K_{3,3} − e)_{≡}).

Acknowledgement: We thank the referees for some helpful comments.

References

[1] A.Kotlov, L.Lovász. The Rank and Size of Graphs, Journal of Graph Theory, 23, No. 1, 185–189, (1996).

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

[3] 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).

[4] R.C.Read and R.J.Wilson, An Atlas of Graphs, Oxford University Press (1999).

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

[6] D.B.West. Introduction to Graph Theory, (2nd Edition), Prentice-Hall (2000).