2017/03/17 by Magda Dettlaff, Magdalena Lemańska, Dettlaff, M. +5 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1703.06034
openalex publication_date 2017/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The neighbourhood of a vertex v of a graph G is the set N(v) of all vertices adjacent to v in G. For D⊆ V(G) we define D=V(G)∖ D. A set D⊆ V(G) is called a super dominating set if for every vertex u∈ D, there exists v∈ D such that N(v)∩ D=\u\. The super domination number of G is the minimum cardinality among all super dominating sets in G. In this article we obtain closed formulas and tight bounds for the super dominating number of lexicographic product graphs in terms of invariants of the factor graphs involved in the product. As a consequence of the study, we show that the problem of finding the super domination number of a graph is NP-Hard.