Some Classifications of Graphs with respect to a Set Adjacency Relation

For any finite simple undirected graph G = (V (G), E(G)) we consider the binary rela- tion ←G on the powerset P(V (G)) of its vertex set given by B ←G A if v∈B NG(v) ⊇ v∈A NG(v), where NG(v) denotes the neighborhood of a vertex v. We call the above relation set adiacence dependency (abbreviated sa)-dependency of G. With the relation ←G we associate an intersection-closed family CLsa(G) of vertex subsets and the cor- responding induced lattice C(G) := (CLsa(G), ⊆), which we call sa-lattice of G. Through the equality of sa-lattices, we introduce an equivalence relation ≡sa between graphs and propose three different classifications of graphs based on such a relation. Furthermore, we determine the sa-lattice for various graph families, such as complete graphs, complete bipartite graphs, cycles and paths and, next, we study such a lattice in relation to the Cartesian and the tensor product of graphs, verifying that in most cases it is a graded lattice. Finally, we provide two algorithms, namely the T-DI ALGORITHM and the O-F ALGORITHM, in order to provide two different computational ways to construct the sa-lattice of a graph. For the O-F ALGORITHM we also determine its computational complexity.