ENUMERATING LABELLED GRAPHS WITH CERTAIN NEIGHBORHOOD PROPERTIES

L.H. Clark^{1}, S. Holliday^{2}, J.P. McSorley^{1}, and T.D. Porter^{1}

1 Department of Mathematics, Mailcode 4408, Southern Illinois University, Carbondale, IL 62901-4408

2 Department of Mathematics and Statistics, University of Tennessee, Martin, Martin, TN 38238-5049

Abstract. Properties of (connected) graphs whose closed or open neighborhood families are Sperner, anti-Sperner, distinct or none of the proceeding have been extensively examined. In this paper we examine 24 properties of the neighborhood family of a graph. We give asymptotic formulas for the number of (connected) labelled graphs for 12 of these properties. For the other 12 properties, we give bounds for the number of such graphs. We also determine the status (a.a.s. or a.a.n.) in G_{n,1/2} of all 24 of these properties. Our methods are both constructive and probabilistic.

1 Introduction

A simple graph G has vertex set V (G) and edge set E(G). The order of G is #V (G) and the size of G is #E(G). The sets N_{G}(v) = {w ∈ V (G) : vw ∈ E(G)} and N_{G}[v] = N_{G}(v)∪{v} are the open neighborhood and closed neighborhood of v in G, respectively.

The collection N_{G}[v]_{v∈V (G)} (respectively, N_{G}(v)_{v∈V (G)}) is the family of closed (respectively, open) neighborhoods of the graph G. Briefly, we say the closed (open) neighborhood family of G. In [5]-[8] graphs whose closed neighborhoods are distinct were studied. In [10] and [20, 21], graphs whose open neighborhoods are distinct were studied. Graphs whose closed neighborhood or open neighborhood family satisfy a particular property (CNAS and NAS; see definitions) have been extensively examined in [12]–[17]. We give results for all these properties in this paper. Results about graphs whose induced open neighborhood subgraphs consists of, for example, only paths or only cycles, can be found in [9] and [18]. Further results may be found in [2]-[4].

We focus on 24 properties (see definitions below) of the closed neighborhood or open neighborhood family of a graph. We examine the number of (connected) labelled graphs whose neighborhood families have these properties. Table 2 in Section 4 contains our main results. It gives asymptotic formulas for the number of labelled graphs with 12 of the properties (lines 1,2,5, and 6) and bounds for the other 12 properties. The properties are quite delicate: deleting a vertex, or adding or deleting an edge generally destroys the property. Hence finding generating functions for the number of labelled graphs with these properties by decomposing the graph into subgraphs with similar properties does not appear promising (cf. Chapter 5 of [19]). Consequently, elementary results about random graphs (with p = 1/2) aid in our enumeration. Along the way we determine the status (a.a.s. or a.a.n.) of all these properties for these random graphs (see Corollaries 2.5 and 3.5).

A set is a collection of distinct elements. A family F of subsets of a fixed set is Sperner if A ⊈ B and B ⊉ A for all A, B ∈ F.

We say a graph G is:

(1) closed neighborhood Sperner (CNS) ⇔ the closed neighborhood family of G is Sperner ⇔ ∀u ≠ v ∈ V (G), N_{G}[u] ⊈ N_{G}[v] and N_{G}[v] ⊈ N_{G}[u],

whose negation is

(2) ¬ closed neighborhood Sperner (¬CNS) ⇔ the closed neighborhood family of G is not Sperner ⇔ ∃u ≠ v ∈ V (G), N_{G}[u] ⊆ N_{G}[v];

(3) closed neighborhood anti-Sperner (CNAS) ⇔ the closed neighborhood family of G is anti-Sperner ⇔ ∀u ∃v ≠ u ∈ V (G), N_{G}[u] ⊆ N_{G}[v] ⇔ every maximal chain in the closed neighborhood family of G ordered by set inclusion has at least two maximum elements,

whose negation is

(4) ¬ closed neighborhood anti-Sperner (¬CNAS) ⇔ the closed neighborhood family of G is not anti-Sperner ⇔ ∃u ∀v ≠ u ∈ V (G), N_{G}[u] ⊈ N_{G}[v] ⇔ there exists a maximal chain in the closed neighborhood family of G ordered by set inclusion with a unique maximum element;

(5) closed neighborhood distinct (CND) ⇔ the closed neighborhood family of G is a set ⇔ ∀u ≠ v ∈ V (G), N_{G}[u] ≠ N_{G}[v],

whose negation is

(6) ¬ closed neighborhood distinct (¬CND) ⇔ the closed neighborhood family of G is not a set ⇔ ∃u ≠ v ∈ V (G), N_{G}[u] = N_{G}[v].

Analogous definitions for these 6 properties hold with “closed” replaced with “open” , we suppress the “O” in the acronym.

A property P of graphs is a collection of graphs which is closed under isomorphism. For a property P, we say G is a connP graph if G is connected and has property P. Hence, we examine 2 (connected or arbitrary)× 2 (closed or open) × 6 = 24 properties in this paper.

Let G_{n} denote the set of all graphs with vertex set [n] = {1, …, n}. The probability space G_{n,p} consists of all graphs G ∈ G_{n} where each edge of G is chosen independently with probability p = p(n). Hence, G ∈ G_{n,p} has probability p^{m}q^{N−m} when G has m edges and N −m non-edges where N = \binom{n}{2} and q = 1 − p. We write G_{n,p} in place of G ∈ G_{n,p}. A graph property P is asymptotically almost sure (a.a.s.) provided Pr(G_{n,p} ∈ P) → 1 as n → ∞, and asymptotically almost null (a.a.n.) provided Pr(G_{n,p} ∈ P) → 0 as n → ∞. We refer the reader to [1].

Since we have constructive lower bounds for the number of connCNAS and connNAS graphs in G_{n} (see [13] and [14] respectively) and

P r(G_{n,1/2} ∈ P) = \frac{#(P ∩ G_{n})}{2^{\binom{n}{2}}},

we focus on G_{n,1/2} only. We do not consider other values of p.

CND  ¬CNAS connCND  CNS conn¬CNAS connCNS In G_{n,1/2}: a.a.s. (Corollary 2.5)  ⟹ ⟸  ⟹ ⟺ ⟹ ⟹ all properties hold with probability at least 1 − n^{2} 2^{−0.415037n+1} ¬CNS ¬CND conn¬CNS CNAS conn¬CND connCNAS a.a.n. (Corollary 2.5)  ⟹ ⟹ ⟺ ⟹ ⟹ ⟹ all properties hold with probability at most n^{2} 2^{−0.415037n} Table 1a

Table 1a gives the logical implications (⇒) and certain probabilistic bounds in G_{n,1/2} among the 12 closed properties. We do not show Table 1b which is identical to Table 1a but with “closed” replaced by “open”. Tables 1a, 1b are the Hasse diagrams of the 4 sets of 6 properties we examine in this paper, partially ordered by logical implication, and where equality is logical equivalence. The probabilistic bounds in Tables 1a, 1b imply the probabilistic status (a.a.s. or a.a.n.) in G_{n,1/2} of these 24 properties (see Corollaries 2.5 and 3.5).

To conclude this Section we note that the threshold for G_{n,p} to be connected is p = ln n/n (cf. [1]). We give a rough estimate for the probability that G_{n,1/2} is connected that is adequate for our purposes.

Lemma 1.1. We have

Pr(G_{n,1/2} is connected) ≥ 1 − n^{2}2^{−n}.

Proof. Fix A ⊆ [n] with |A| = a ∈ {1, …, n − 1}. Let E_{A,A^{c}} denote the event “ there are no edges between A and A^{c} ”. By independence, Pr(E_{A,A^{c}}) = 2^{−a(n−a)}.

Let E denote the event ⋃_{such A,A^{c}} E_{A,A^{c}}, i.e., the event “ G_{n,1/2} is disconnected ”.

Then

Pr(E) ≤ \frac{1}{2} ∑_{a=1}^{n−1} \binom{n}{a}2^{−a(n−a)}.

The terms in the sum decrease to a = ⌊(n + 1)/2⌋ and increase thereafter; the maximum occurs at both a = 1, n−1. Hence, Pr(G_{n,1/2} is disconnected) = Pr(E) ≤ n^{2}2^{−n}, which implies the result.

For the constants that appear in the paper we only write the first six digits of their infinite decimal expansions. We assume throughout that n ≥ 4.

2 Closed neighborhood properties of a graph

We start with property ¬CNS since it lies at the top of the lower Hasse diagram in Table 1a.

Theorem 2.1. We have

Pr(G_{n,1/2} is ¬CNS) ≤ n^{2} 2^{−0.415037n},

where 2^{−0.415037} = 0.75, (−0.415037 = \frac{ln 0.75}{ln 2}).

Proof. Fix u ≠ v ∈ [n], A ⊆ B ⊆ [n] − {u, v}. Let E_{u,v,A,B} denote the event “N_{G}[u] = A ∪ {u, v} and N_{G}[v] = B ∪ {u, v}”, so u ∼ v. Let 0 ≤ a = |A| ≤ |B| = b ≤ n − 2. Then, using independence,

Pr(E_{u,v,A,B}) = 2^{−1}2^{−a}2^{−b}2^{−(n−a−2)}2^{−(n−b−2)} = 2^{−(2n−3)}.

Let E_{u,v,a,b} denote the event ⋃_{such A,B} E_{u,v,A,B} for a fixed a and b. Then,

Pr(E_{u,v,a,b}) ≤ \binom{n − 2}{a}\binom{n − 2 − a}{b − a}2^{−(2n−3)}.

Let E_{u,v} be the event “N_{G}[u] ⊆ N_{G}[v]”, i.e., ⋃_{{a=0,1,...,n−2 \atop a≤b≤n−2}} E_{u,v,a,b}.

Then,

\begin{aligned}Pr(E_{u,v}) & ≤ ∑_{a=0}^{n−2} \binom{n − 2}{a} \{∑_{b=a}^{n−2} \binom{n − 2 − a}{b − a}\} 2^{−(2n−3)} \\ & = ∑_{a=0}^{n−2} \binom{n − 2}{a}2^{n−2−a}2^{−(2n−3)} = 2^{−n+1} ∑_{a=0}^{n−2} \binom{n − 2}{a}2^{−a} = \frac{8}{9}(0.75)^{n}. \end{aligned}

Now G_{n,1/2} is ¬CNS if there exists a pair {u, v} of vertices with N_{G}[u] ⊆ N_{G}[v]. There are \binom{n}{2} pairs \{u, v\} so:

Pr(G_{n,1/2} is ¬CNS) ≤ \frac{n^{2}}{2} \frac{8}{9}(0.75)^{n} ≤ n^{2}(0.75)^{n}.

Theorem 2.2. We have

Pr(G_{n,1/2} is ¬CND) ≥ 2^{−n+1},

equivalently,

Pr(G_{n,1/2} is CND) ≤ 1 − 2^{−n+1}.

Proof. Fix A ⊆ [n] − {1, 2} with |A| = a. Let E_{A} denote the event “N_{G}[1] = N_{G}[2] = A ∪ {1, 2}”. Similar to before, we have Pr(E_{A}) = 2^{−(2n−3)}.

Let E denote the event ⋃_{such A}E_{A}; note that the E_{A} are pair-wise disjoint

events. Then

Pr(E) = ∑_{a=0}^{n−2} \binom{n − 2}{a}2^{−(2n−3)} = 2^{−n+1}.

Since E ⊆ “G_{n,1/2} is ¬CND”, then Pr(G_{n,1/2} is ¬CND) ≥ Pr(E) = 2^{−n+1}, hence the result.

Recall that graphs G and H are equal (G = H) ⇔ V (G) = V (H) and E(G) = E(H). When V (G) = V (H), G and H are distinct (G ≠ H) ⇔ E(G) ≠ E(H), i.e., distinct edge-sets give distinct graphs.

We require a construction from [14]: Let V (G) = [n], and E(G) = {12} ∪ {1k, 2k : k ∈ [n] − {1, 2}}. Let B denote the set of edges with both end-vertices in [n] − \{1, 2\}, so |B| = \binom{n}{2}. Now define a graph G_{A} with V (G_{A}) = [n] and E(G_{A}) = E(G) ∪ A where A ⊆ B.

Theorem ([13]). The graph G_{A} is a CNAS graph, a connCNAS graph, and a conn¬CND graph for all A ⊆ B.

Proof. Clearly G_{A} is connected. Observe that N_{G_{A}}[1] = N_{G_{A}}[2] = [n] ⊇ N_{G_{A}}[k] for all k ∈ [n] − {1, 2}.

Theorem 2.3. For P any of the properties CNAS, connCNAS, or conn¬CND

Pr(G_{n,1/2} is P) ≥ 2^{−2n+3},

equivalently,

Pr(G_{n,1/2} is ¬P) ≤ 1 − 2^{−2n+3}.

Proof. Distinct edge-sets A ⊆ B give distinct graphs G_{A}, so #P_{n} ≥ 2^{\binom{n−2}{2}}. Each graph in G_{n,1/2} has probability 2^{−\binom{n}{2}}, so Pr(G_{n,1/2} is P) ≥ 2^{−2n+3}, hence the result.

Theorem 2.4. We have

Pr(G_{n,1/2} is connCNS) ≥ 1 − n^{2}2^{−0.415037n+1}.

Proof. From Theorem 2.1 and Lemma 1.1,

Pr(G_{n,1/2} is ¬CNS or disconnected) ≤ n^{2} 2^{−0.415037n} + n^{2}2^{−n}
≤ n^{2}2^{−0.415037n+1},

which implies the result.

Corollary 2.5. For P any of the properties on a fixed line of the table below Pr(G_{n,1/2} is P) is bounded by the values in the left-hand and righthand columns.

P

CNS, connCNS,

1 1 − n^{2} 2^{−0.415037n+1} ≤  CND, connCND,  ≤ 1 − 2^{−n+1}
2 1 − n^{2} 2^{−0.415037n+1} ≤ ¬CNAS, conn¬CNAS ≤ 1 − 2^{−2n+3}

conn¬CNS, CNAS,

3  2^{−2n+3}  ≤ connCNAS, conn¬CND ≤ n^{2} 2^{−0.415037n}
4  2^{−n+1}  ≤  ¬CNS, ¬CND  ≤ n^{2} 2^{−0.415037n}

Proof. For the upper half of this table see the Hasse diagram in the upper half of Table 1a. Line 1 comes from Theorems 2.4 (lower bound) and 2.2 (upper bound) and line 2 from Theorems 2.4 and 2.3, and monotonicity. Hence, each of these six properties is a.a.s. in G_{n,1/2} .

For the lower half see the lower half of Table 1a. Line 3 comes from Theorems 2.3 and 2.1 and line 4 from Theorems 2.2 and 2.1, and monotonicity. Hence, each of these six properties is a.a.n. in G_{n,1/2} .

Lines 1–4 of Table 2 follow from Corollary 2.5 upon multiplying by 2^{\binom{n}{2}}.

3 Open neighborhood properties of a graph

We now consider open neighborhood properties of a graph, where our results are similar, but different, to before.

Theorem 3.1. We have

Pr(G_{n,1/2} is ¬NS) ≤ n^{2} 2^{−0.415037n}.

Proof. Similar to the notation in the proof of Theorem 2.1, for u ≠ v, let E′_{u,v,A,B} denote the event “N_{G}(u) = A and N_{G}(v) = B”. Then u ≁ v and Pr(E′_{u,v,A,B}) = 2^{−(2n−3)}. Then we define the “open” analogue of events E_{u,v,a,b}, namely E′_{u,v,a,b}, and E_{u,v}, namely E′_{u,v}: “N_{G}(u) ⊆ N_{G}(v)”; and the remainder of the proof is precisely as in Theorem 2.1.

Theorem 3.2. We have

Pr(G_{n,1/2} is ¬ND) ≥ 2^{−n+1}

equivalently,

Pr(G_{n,1/2} is ND) ≤ 1 − 2^{−n+1}.

Proof. Again, similar to the notation in the proof of Theorem 2.2, let E′_{A} denote the event “N_{G}(1) = N_{G}(2) = A”. We then define E′ as the event ⋃_{such A}E′_{A} and the proof proceeds as in Theorem 2.2.

Assume n = 2m ≥ 4. Let V (G) = [2m] = [m] ∪ ([2m] − [m]) and E(G) = {1k, 2k : k ∈ [2m] − [m]} ∪ {(m + 1)k, (m + 2)k : k ∈ [m]}. Set B = \{ij : i ∈ [m], j ∈ [2m]−[m]\}−E(G), so |B| = (\frac{n−4}{2})^{2} = 0.25n^{2}−2n+4. Let V (G_{A}) = V (G) and E(G_{A}) = E(G) ∪ A where A ⊆ B. A similar definition holds with [2m] replaced by [2m + 1].

Theorem ([14]). The graph G_{A} is a NAS graph, a connNAS graph, and a conn¬ND graph for all A ⊆ B.

Proof. Clearly G_{A} is connected. Observe that N_{G_{A}}(1) = N_{G_{A}}(2) = [2m] − [m] ⊇ N_{G_{A}}(k) for all k ∈ [m], and N_{G_{A}}(m + 1) = N_{G_{A}}(m + 2) = [m] ⊇ N_{G_{A}}(k) for all k ∈ [2m] − [m].

Theorem 3.3. For P any of the properties NAS, connNAS, or conn¬ND

Pr(G_{n,1/2} is P) ≥ 2^{−0.25n^{2}−1.5n+4},

equivalently,

Pr(G_{n,1/2} is ¬P) ≤ 1 − 2^{−0.25n^{2}−1.5n+4}.

Proof. For even n ≥ 4 distinct edge-sets A ⊆ B give distinct graphs G_{A}, so #P_{n} ≥ 2^{0.25n^{2}−2n+4}. And each graph in G_{n,1/2} has probability 2^{−\binom{n}{2}}, so Pr(G_{n,1/2} is P) ≥ 2^{−0.25n^{2}−1.5n+4}, which gives the result. A slight modification of this argument is needed for odd n ≥ 5.

Theorem 3.4. We have

Pr(G_{n,1/2} is connNS) ≥ 1 − n^{2}2^{−0.415037n+1}.

Proof. This follows from Lemma 1.1 and Theorem 3.1, as in the proof of Theorem 2.4.

Corollary 3.5. For P any of the properties on a fixed line of the table below Pr(G_{n,1/2} is P) is bounded by the values in the left-hand and righthand columns.

P

NS, connNS,

1 1 − n^{2} 2^{−0.415037n+1} ≤  ND, connND,  ≤ 1 − 2^{−n+1}
2 1 − n^{2} 2^{−0.415037n+1} ≤ ¬NAS, conn¬NAS ≤ 1 − 2^{−0.25n^{2}−1.5n+4}

conn¬NS, NAS,

3 2^{−0.25n^{2}−1.5n+4} ≤ connNAS, conn¬ND ≤ n^{2} 2^{−0.415037n}
4  2^{−n+1}  ≤  ¬NS, ¬ND  ≤ n^{2} 2^{−0.415037n}

Proof. For the upper half of this table consider the Hasse diagram in the upper half of Table 1b (not shown). Line 1 comes from Theorems 3.4 (lower bound) and 3.2 (upper bound), and line 2 from Theorems 3.4 and 3.3, and monotonicity. Hence, each of these six properties is a.a.s. in G_{n,1/2} .

For the lower half consider the lower half of Table 1b. Line 3 comes from Theorems 3.3 and 3.1 and line 4 from Theorems 3.2 and 3.1, and monotonicity. Hence, each of these six properties is a.a.n. in G_{n,1/2} .

Lines 5–8 of Table 2 follow from Corollary 3.5 upon multiplying by 2^{\binom{n}{2}}.

4 Main Results and Asymptotics

Recall,

f(n) ∼ g(n) if and only if lim_{n→∞} \frac{f(n)}{g(n)} = 1,

and for a property P of graphs, and P_{n} = P ∩ G_{n} is the set of distinct graphs on [n] having property P.

For P any of the properties on a fixed line of Table 2, #P_{n} is bounded by the values in the left-hand and right-hand columns (see the comments after Corollaries 2.5 and 3.5).

For the 12 properties P in lines 1, 2, 5, and 6 of Table 2, we have

#P_{n} ∼ 2^{\binom{n}{2}},

and for the 8 properties in lines 3, 4, and 8 of Table 2, we have

log_{2} #P_{n} ∼ \frac{n^{2}}{2} .

Table 2

#P_{n}
#CNS_{n}, #connCNS_{n},
1 2^{\binom{n}{2}}(1 − n^{2} 2^{−0.415037n+1}) ≤ #CND_{n}, #connCND_{n}, ≤  2^{\binom{n}{2}}(1 − 2^{−n+1})
2 2^{\binom{n}{2}}(1 − n^{2} 2^{−0.415037n+1}) ≤ #¬CNAS_{n}, #conn¬CNAS_{n} ≤  2^{\binom{n}{2}}(1 − 2^{−2n+3})

#conn¬CNS_{n}, #CNAS_{n},
3  2^{0.5n^{2}−2.5n+3}  ≤ #connCNAS_{n}, #conn¬CND_{n} ≤ n^{2} 2^{0.5n^{2}−0.915037n}
4  2^{0.5n^{2}−1.5n+1}  ≤  #¬CNS_{n}, #¬CND_{n}  ≤ n^{2} 2^{0.5n^{2}−0.915037n}

#NS_{n}, #connNS_{n},

5 2^{\binom{n}{2}}(1 − n^{2} 2^{−0.415037n+1}) ≤  #ND_{n}, #connND_{n},  ≤  2^{\binom{n}{2}}(1 − 2^{−n+1})
6 2^{\binom{n}{2}}(1 − n^{2} 2^{−0.415037n+1}) ≤ #¬NAS_{n}, #conn¬NAS_{n} ≤ 2^{\binom{n}{2}}(1 − 2^{−0.25n^{2}−1.5n+4})

#conn¬NS_{n}, #NAS_{n},
7  2^{0.25n^{2}−2n+4}  ≤ #connNAS_{n}, #conn¬ND_{n} ≤ n^{2} 2^{0.5n^{2}−0.915037n}
8  2^{0.5n^{2}−1.5n+1}  ≤  #¬NS_{n}, #¬ND_{n}  ≤ n^{2} 2^{0.5n^{2}−0.915037n}

From lines 1 and 2 in the tables of Corollaries 2.5 and 3.5, for P any one of the 12 properties CNS, connCNS, CND, connCND, ¬CNAS, conn¬CNAS, NS, connNS, ND, connND, ¬NAS, or conn¬NAS, we have lim_{n→∞} Pr(G_{n,1/2} is P) = 1. Hence

lim_{n→∞} Pr(G_{n,1/2} is P)^{1/n} = 1.

From line 3 in the table of Corollary 2.5, for P any one of the 4 properties conn¬CNS, CNAS, connCNAS, or conn¬CND, we have

8 (0.25)^{n} ≤ Pr(G_{n,1/2} is P) ≤ n^{2} (0.75)^{n}.

Hence

0.25 ≤ lim inf_{n→∞} Pr(G_{n,1/2} is P)^{1/n}

≤ lim sup_{n→∞} Pr(G_{n,1/2} is P)^{1/n} ≤ 0.75.

(1)

Similarly, from line 3 in the table of Corollary 3.5, for P any one of the 4 properties conn¬NS, NAS, connNAS, or conn¬ND, we have

0 ≤ lim inf_{n→∞} Pr(G_{n,1/2} is P)^{1/n}

≤ lim sup_{n→∞} Pr(G_{n,1/2} is P)^{1/n} ≤ 0.75.

(2)

Finally, from line 4 in the tables of Corollaries 2.5 and 3.5, for P any of the 4 properties ¬CNS, ¬CND, ¬NS, or ¬ND, then

0.5 ≤ lim inf_{n→∞} Pr(G_{n,1/2} is P)^{1/n}

≤ lim sup_{n→∞} Pr(G_{n,1/2} is P)^{1/n} ≤ 0.75.

(3)

Conjecture. We conjecture that lim_{n→∞} Pr(G_{n,1/2} is P)^{1/n} exists for each of the 12 properties considered in Equations (1), (2), and (3).

Observations 4.1 and 4.2 below and Fekete’s lemma [11] may bear on the proof.

Suppose graphs G and H have disjoint vertex sets V (G) and V (H), respectively. The join G ∨ H of G and H is the graph with V (G ∨ H) = V (G)∪V (H) and E(G∨H) = E(G)∪E(H)∪{uv : u ∈ V (G), v ∈ V (H)}.

For the remainder of this Section let P be any of our 24 properties except ¬CNAS, conn¬CNAS, CND, or connCND. Note that the 12 properties P considered in the above Conjecture are amongst these 20 properties. Observation 4.1. Suppose G_{i} and H_{i} are P graphs with V (G_{i}) = V and V (H_{i}) = W for i = 1, 2 where V and W are disjoint sets. Then G_{i} ∨ H_{i} is a connected P graph. If G_{1} ≠ G_{2} or H_{1} ≠ H_{2}, then G_{1} ∨ H_{1} ≠ G_{2} ∨ H_{2} .

Proof. We prove the Theorem for one property only, namely the CNAS property. We also show why the Theorem is false for the ¬CNAS property. The proofs for the remaining properties are similar.

For any v ∈ V, we have N_{G_{1}∨H_{1}}[v] = N_{G_{1}}[v] ∪ W. Now for an arbitrary v ∈ V, if N_{G_{1}}[v] ⊆ N_{G_{1}}[u] for some u ∈ V with u ≠ v, then N_{G_{1}∨H_{1}}[v] ⊆ N_{G_{1}∨H_{1}}[u]. Similarly for an arbitrary w ∈ W. Thus N_{G_{1}∨H_{1}} is CNAS. Now observe that G_{1} ∨ H_{1} is connected for all G_{1} and H_{1}. Hence G_{1} ∨ H_{1} is a connected P graph if G_{1} and H_{1} are P graphs. Clearly, G_{1} ∨ H_{1} ≠ G_{2} ∨ H_{2} if G_{1} ≠ G_{2} or H_{1} ≠ H_{2}.

Suppose v ∈ V has N_{G_{1}}[v] = V and for all u ∈ V with u ≠ v then N_{G_{1}}[u] ⊂ V, and suppose w ∈ W has N_{H_{1}}[w] = W and for all x ∈ W with x ≠ w then N_{H_{1}}[x] ⊂ W. Then both G_{1} and H_{1} are ¬CNAS but N_{G_{1}∨H_{1}} is CNAS since N_{G_{1}∨H_{1}}[v] = N_{G_{1}∨H_{1}}[w] = V ∪ W.

Let f_{P} (n) denote the number of distinct P graphs on [n].

Observation 4.2. For n, m ≥ 1, we have f_{P} (n + m) ≥ f_{P} (n)f_{P} (m).

Proof. Let 𝔑 and 𝔐 be the set of P graphs on [n] and [n + m] − [n], respectively. Hence, |𝔑| = f_{P} (n) and |𝔐| = f_{P} (m). By Observation 4.1, {G ∨ H : G ∈ 𝔑, H ∈ 𝔐} is a set of f_{P} (n)f_{P} (m) distinct (connected) P graphs on [n + m]. Hence, f_{P} (n + m) ≥ f_{P} (n)f_{P} (m).

Slight improvements of the lower bound (a further quadratic factor in n) in Observation 4.2 can be made which we do not include.

5 Questions and Comments

We list several questions, with comments, that we find interesting.

(i) We have found an asymptotic formula, #P_{n} ∼ 2^{\binom{n}{2}}, for the number of labelled graphs of order n for the 12 properties P in lines 1,2,5, and 6 of Table 2. Find an asymptotic formula for the number of labelled graphs of order n for the 12 properties P in lines 3,4,7, and 8 of Table 2.

(ii) Find the correct quadratic term in the exponent of 2 for the properties P in line 7 of Table 2. Improve the linear term in the exponent of 2 for the properties in lines 3,4, and 8 of Table 2.

(iii) Prove or disprove the above Conjecture concerning the limits in (1), (2), and (3). If these limits exist, find their values.

Acknowledgment. We thank the referees for comments that simplified the results of this paper, and improved its presentation.

References

[1] B. Bollobás, Random Graphs (Second Edition), Cambridge University Press, New York (2001).

[2] M. Borowiecki and P. Mihók, On graphs with a local hereditary property, Discrete Mathematics 236 (2001), no. 1–3, 53–58.

[3] M. Borowiecki and E. Sidorowicz, Some extremal problems of graphs with local constraints, Discrete Mathematics 251 (2002), no. 1–3, 19–32.

[4] M. Brown and R. Connelly, On graphs with constant link, in: New Directions in the Theory of Graphs, Academic Press, New York, (1973), pp. 19–51.

[5] G-L. Chia and C-K. Lim, On supercompact graphs I: the nucleus, Ars Combinatoria, 20 (1985), 101–110.

[6] G-L. Chia and C-K. Lim, On supercompact graphs II: |G_{0}| = 2, Bulletin of the Malaysian Mathematical Society (2), 8 (1985), 27–34.

[7] G-L. Chia and C-K. Lim, On supercompact graphs III: the edge nucleus, in, Graph Theory (Singapore 1983), Springer-Verlag, Lecture Notes in Mathematics 1073 1–10.

[8] G-L. Chia and C-K. Lim, On supercompact graphs IV: (n, m)−graphs, Ars Combinatoria, 25 (1988), 203–220.

[9] L.H. Clark, R.C. Entringer, J.E. McCanna and L.A. Székely, Extremal problems for local properties of graphs, Australasian Journal of Combinatorics 4 (1991), 25–31.

[10] R.C. Entringer and L.D. Gassman, Line-critical point determining and point distinguishing graphs, Discrete Mathematics 10 (1974), 43–55.

[11] M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten, Mathmatische Zeitschrift 17 (1923), 228-249.

[12] J.P. McSorley, Constructing and classifying neighborhood anti-Sperner graphs, Discrete Mathematics 308 (2008), 5428–5445.

[13] J.P. McSorley, Closed-neighborhood anti-Sperner graphs-II; extremal graphs, in preparation.

[14] J.P. McSorley, Further properties of neighborhood anti-Sperner graphs; extremal graphs, in preparation.

[15] J.P. McSorley, A. Marr, T.D. Porter and W.D. Wallis, Closedneighborhood anti-Sperner graphs, Australasian Journal of Combinatorics 38 (2007), 63–76.

[16] T.D. Porter, Graphs with the anti-neighborhood Sperner property, Journal of Combinatorial Mathematics and Combinatorial Computing 50 (2004), 123–127.

[17] T.D. Porter and J.L. Yucas, Graphs whose vertex-neighborhoods are anti-Sperner, Bulletin of the Institute of Combinatorics and Its Applications 44 (2005), 69–77.

[18] A. Seress and T. Szabó, Dense graphs with cycle neighborhoods, Journal of Combinatorial Theory Series B 63 (1995), no. 2, 281–293.

[19] R.P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, New York (1999).

[20] D.P. Sumner, Point determination in graphs, Discrete Mathematics 5 (1973), 179–187.

[21] D.P. Sumner, The nucleus of a point determining graph, Discrete Mathematics 14 (1976), 91–97.