论文标题
扩展的固定图和主导问题
Expanded-clique graphs and the domination problem
论文作者
论文摘要
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 $。在这项工作中，在结果中，我们介绍了扩展的粘液图的两个特征，其中一个导致线性识别算法。关于统治号码，我们表明，对于平面两分的平面$ 3 $ expexed-clique-clique graphs和二分组图的立方线图是\ np complete。
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.
