{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T23:24:42Z","timestamp":1778714682503,"version":"3.51.4"},"reference-count":20,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,13]],"date-time":"2023-01-13T00:00:00Z","timestamp":1673568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Research Foundation for Advanced Talents of Beijing Technology and Business University","award":["19008022331"],"award-info":[{"award-number":["19008022331"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Given two graphs G and H, the mapping of f:V(G)\u2192V(H) is called a graph homomorphism from G to H if it maps the adjacent vertices of G to the adjacent vertices of H. For the graph G, a subset of vertices is called a dissociation set of G if it induces a subgraph of G 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 G to the graph H and the number of dissociation sets in a bipartite graph G.<\/jats:p>","DOI":"10.3390\/e25010163","type":"journal-article","created":{"date-parts":[[2023,1,16]],"date-time":"2023-01-16T02:04:45Z","timestamp":1673834685000},"page":"163","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Entropy, Graph Homomorphisms, and Dissociation Sets"],"prefix":"10.3390","volume":"25","author":[{"given":"Ziyuan","family":"Wang","sequence":"first","affiliation":[{"name":"School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7667-2116","authenticated-orcid":false,"given":"Jianhua","family":"Tu","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rongling","family":"Lang","sequence":"additional","affiliation":[{"name":"School of Electronics and Information Engineering, Beihang University, Beijing 100191, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1017\/S0963548301004631","article-title":"An entropy approach to the hard-core model on bipartite graphs","volume":"10","author":"Kahn","year":"2001","journal-title":"Comb. Probab. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1017\/S0963548309990538","article-title":"The number of independent sets in a regular graph","volume":"19","author":"Zhao","year":"2010","journal-title":"Comb. Probab. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.jctb.2019.01.007","article-title":"The number of independent sets in an irregular graph","volume":"138","author":"Sah","year":"2019","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Sason, I. (2021). A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs. Entropy, 23.","DOI":"10.3390\/e23030270"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1002\/jgt.22629","article-title":"On the maximum number of maximum independent sets in connected graphs","volume":"96","author":"Mohr","year":"2021","journal-title":"J. Graph Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","article-title":"On cliques in graphs","volume":"3","author":"Moon","year":"1965","journal-title":"Isr. J. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1002\/jgt.20186","article-title":"Maximal and maximum independent sets in graphs with at most r cycles","volume":"53","author":"Sagan","year":"2006","journal-title":"J. Graph Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1112\/jlms.12056","article-title":"Independent sets, matchings, and occupancy fractions","volume":"96","author":"Davies","year":"2017","journal-title":"J. Lond. Math. Soc."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1016\/j.disc.2018.11.025","article-title":"On the maximum number of minimum dominating sets in forests","volume":"342","author":"Alvarado","year":"2019","journal-title":"Discrete Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1002\/jgt.22627","article-title":"The maximum number of maximum dissociation sets in trees","volume":"96","author":"Tu","year":"2021","journal-title":"J. Graph Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1090\/dimacs\/063\/07","article-title":"On weighted graph homomorphisms","volume":"63","author":"Galvin","year":"2004","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"827","DOI":"10.4169\/amer.math.monthly.124.9.827","article-title":"Independent Sets and Graph Homomorphisms","volume":"124","author":"Zhao","year":"2017","journal-title":"Amer. Math. Monthly"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"11","DOI":"10.37236\/1098","article-title":"Bounding the partition function of spin-systems","volume":"13","author":"Galvin","year":"2006","journal-title":"Electron. J. Combin."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","article-title":"Node-deletion problems on bipartite graphs","volume":"10","author":"Yannakakis","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1352","DOI":"10.1016\/j.dam.2011.04.023","article-title":"The complexity of dissociation set problems in graphs","volume":"159","author":"Orlovich","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"ref_16","unstructured":"Galvin, D. (2014, January 15\u201316). Three tutorial lectures on entropy and counting. Proceedings of the 1st Lake Michigan Workshop on Combinatorics and Graph Theory, Kalamazoo, MI, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF02772952","article-title":"Independent sets in regular graphs and sum-free subsets of finite groups","volume":"73","author":"Alon","year":"1991","journal-title":"Isr. J. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.ejc.2015.02.005","article-title":"Counting independent sets in graphs","volume":"48","author":"Samotij","year":"2015","journal-title":"Eur. J. Comb."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s13119-011-0002-7","article-title":"The k-observer problem in computer networks","volume":"1","author":"Acharya","year":"2012","journal-title":"Netw. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","article-title":"Minimum k-path vertex cover","volume":"159","year":"2011","journal-title":"Discrete Appl. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/163\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:05:30Z","timestamp":1760119530000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,13]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["e25010163"],"URL":"https:\/\/doi.org\/10.3390\/e25010163","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,13]]}}}