熵、图同态与解离集
Entropy, Graph Homomorphisms, and Dissociation Sets.
作者信息
Wang Ziyuan, Tu Jianhua, Lang Rongling
机构信息
School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, China.
School of Electronics and Information Engineering, Beihang University, Beijing 100191, China.
出版信息
Entropy (Basel). 2023 Jan 13;25(1):163. doi: 10.3390/e25010163.
Given two graphs and , the mapping of f:V(G)→V(H) is called a graph homomorphism from to if it maps the adjacent vertices of to the adjacent vertices of . For the graph , a subset of vertices is called a dissociation set of if it induces a subgraph of containing no paths of order three, i.e., a subgraph of a maximum degree, which is at most one. Graph homomorphisms and dissociation sets are two generalizations of the concept of independent sets. In this paper, by utilizing an entropy approach, we provide upper bounds on the number of graph homomorphisms from the bipartite graph to the graph and the number of dissociation sets in a bipartite graph .
给定两个图(G)和(H)，映射(f:V(G)→V(H))若将(G)的相邻顶点映射为(H)的相邻顶点，则称其为从(G)到(H)的图同态。对于图(G)，顶点的一个子集若诱导出(G)的一个不包含三阶路径的子图，即一个最大度至多为(1)的子图，则称该子集为(G)的一个解离集。图同态和解离集是独立集概念的两种推广。在本文中，通过利用熵方法，我们给出了从二分图(G)到图(H)的图同态数量以及二分图(G)中解离集数量的上界。
Zotero 插件