{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:40:08Z","timestamp":1760190008773,"version":"build-2065373602"},"reference-count":9,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T00:00:00Z","timestamp":1564444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2014-06571"],"award-info":[{"award-number":["2014-06571"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"For a graph \r\n \r\n \r\n \r\n G\r\n =\r\n (\r\n V\r\n ,\r\n E\r\n )\r\n \r\n \r\n \r\n , the \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -graph of G, denoted \r\n \r\n \r\n \r\n G\r\n (\r\n \u03b3\r\n )\r\n =\r\n (\r\n V\r\n (\r\n \u03b3\r\n )\r\n ,\r\n E\r\n (\r\n \u03b3\r\n )\r\n )\r\n \r\n \r\n \r\n , is the graph whose vertex set is the collection of minimum dominating sets, or \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -sets of G, and two \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -sets are adjacent in \r\n \r\n \r\n \r\n G\r\n (\r\n \u03b3\r\n )\r\n \r\n \r\n \r\n if they differ by a single vertex and the two different vertices are adjacent in G. In this paper, we consider \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -graphs of trees. We develop an algorithm for determining the \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -graph of a tree, characterize which trees are \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -graphs of trees, and further comment on the structure of \r\n \r\n \r\n \u03b3\r\n \r\n \r\n -graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.<\/jats:p>","DOI":"10.3390\/a12080153","type":"journal-article","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T11:15:56Z","timestamp":1564485356000},"page":"153","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["\u03b3-Graphs of Trees"],"prefix":"10.3390","volume":"12","author":[{"given":"Stephen","family":"Finbow","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, St. Francis Xavier University, Antigonish, NS B2G2W5, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2687-9127","authenticated-orcid":false,"given":"Christopher M.","family":"van Bommel","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2019,7,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","article-title":"A linear algorithm for the domination number of a tree","volume":"4","author":"Cockayne","year":"1975","journal-title":"Inform. Process. Lett."},{"key":"ref_2","first-page":"23","article-title":"A note on \u03b3-graphs","volume":"8","author":"Connelly","year":"2011","journal-title":"AKCE J. Graphs Combin."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"703","DOI":"10.7151\/dmgt.2044","article-title":"Reconfiguring minimum dominating sets: The \u03b3-graph of a tree","volume":"38","author":"Edwards","year":"2018","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.7151\/dmgt.1562","article-title":"\u03b3-graphs of graphs","volume":"31","author":"Fricke","year":"2011","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_5","unstructured":"Chung, F., Graham, R., Hoffman, F., Hogben, L., Mullin, R., and West, D. Reconfiguration of colourings and dominating sets in graphs. 50 Years of Combinatorics, Graph Theory, and Computing, CRC Press. (in press)."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Rote, G. (2019, January 6\u20139). The maximum number of minimal dominating sets in a tree. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA.","DOI":"10.1137\/1.9781611975482.73"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1007\/BF01162967","article-title":"Graph multiplication","volume":"72","author":"Sabidussi","year":"1960","journal-title":"Math. Z."},{"key":"ref_8","first-page":"17","article-title":"\u03b3-graph of a graph","volume":"5","author":"Subramanian","year":"2008","journal-title":"Bull. Kerala Math. Assoc."},{"key":"ref_9","first-page":"30","article-title":"The Cartesian product of graphs","volume":"9","author":"Vizing","year":"1963","journal-title":"Vycisl. Sistemy"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/153\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:11:14Z","timestamp":1760188274000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,30]]},"references-count":9,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080153"],"URL":"https:\/\/doi.org\/10.3390\/a12080153","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,7,30]]}}}