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 relation ← G on the powerset 𝒫 (V (G)) of its vertex set given by B ← G A if ⋂ v ∈ B N G (v) ⊇ ⋂ v ∈ A N G (v) , where N G (v) denotes the neighborhood of a vertex v. We call the above relation set adiacence dependency (sa)-dependency of G. With the relation ← G we associate an intersection-closed family C L s a (G) of vertex subsets and the corresponding induced lattice ℭ (G) : = (C L s a (G) , ⊆) , which we call sa-lattice of G. Through the equality of sa-lattices, we introduce an equivalence relation ≡ s a 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. [ABSTRACT FROM AUTHOR]