Expanded-clique graphs and the domination problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913349395021824 |
|---|---|
| author | Dourado, Mitre C. Oliveira, Rodolfo A. Ponciano, Vitor Queiróz, Alessandra B. Silva, Rômulo L. O. |
| author_facet | Dourado, Mitre C. Oliveira, Rodolfo A. Ponciano, Vitor Queiróz, Alessandra B. Silva, Rômulo L. O. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_03411 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Expanded-clique graphs and the domination problem Dourado, Mitre C. Oliveira, Rodolfo A. Ponciano, Vitor Queiróz, Alessandra B. Silva, Rômulo L. O. Discrete Mathematics Combinatorics 05C85 G.2.2 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. |
| title | Expanded-clique graphs and the domination problem |
| topic | Discrete Mathematics Combinatorics 05C85 G.2.2 |
| url | https://arxiv.org/abs/2208.03411 |