Closed-Neighborhood Anti-Sperner Graphs

Authors

John P. McSorley, Southern Illinois University CarbondaleFollow
Alison Marr, Southern Illinois University Carbondale
Thomas D. Porter, Southern Illinois University Carbondale
Walter D. Wallis, Southern Illinois University Carbondale

Comments

Published in Australasian Journal of Combinatorics, 38, 63-76

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 closed-neighborhood 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.

Recommended Citation

McSorley, John P., Marr, Alison, Porter, Thomas D. and Wallis, Walter D. "Closed-Neighborhood Anti-Sperner Graphs." (Jun 2007).