Expanded-clique graphs and the domination problem

Mitre C. Dourado; Rodolfo A. Oliveira; Vitor Ponciano; Alessandra B. QueirÃ³z; RÃ´mulo L. O. Silva

paper

Expanded-clique graphs and the domination problem

arXiv:2208.03411

Abstract

Given a graph $G$ such that each vertex $v_{i}$ has a value $f (v_{i})$ , the expanded-clique graph $H$ is the graph where each vertex $v_{i}$ of $G$ becomes a clique $V_{i}$ of size $f (v_{i})$ and for each edge $v_{i} v_{j} \in E (G)$ , there is a vertex of $V_{i}$ adjacent to an exclusive vertex of $V_{j}$ . In this work, among the results, we present two characterizations of the expanded-clique graphs, one of them leads to a linear-time recognition algorithm. Regarding the domination number, we show that this problem is \NP-complete for planar bipartite $3$ -expanded-clique graphs and for cubic line graphs of bipartite graphs.

17 pages, 5 figures