Expanded-clique graphs and the domination problem

Autor:	Dourado, Mitre C., Oliveira, Rodolfo A., Ponciano, Vitor, Queiróz, Alessandra B., Silva, Rômulo L. O.
Rok vydání:	2022
Předmět:	Computer Science - Discrete Mathematics Mathematics - Combinatorics 05C85 G.2.2
Druh dokumentu:	Working Paper
Popis:	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_iv_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. Comment: 17 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2208.03411 Zobrazit plný text záznamu View this record from Arxiv