University of Victoria
Enumerating digitally convex sets in graphs.
Degree: Department of Mathematics and Statistics, 2020, University of Victoria
Given a finite set V, a convexity, C, is a collection of subsets of V that contains both the empty set and the set V and is closed under intersections. The elements of C are called convex sets. We can define several different convexities on the vertex set of a graph. In particular, the digital convexity, originally proposed as a tool for processing digital images, is defined as follows: a subset S of V(G) is digitally convex if, for every vertex v in V(G), we have N[v] a subset of N[S] implies v in S. Or, in other words, each vertex v that is not in the digitally convex set S needs to have a private neighbour in the graph with respect to S. In this thesis, we focus on the generation and enumeration of digitally convex sets in several classes of graphs. We establish upper bounds on the number of digitally convex sets of 2-trees, k-trees and simple clique 2-trees, as well as conjecturing a lower bound on the number of digitally convex sets of 2-trees and a generalization to k-trees. For other classes of graphs, including powers of cycles and paths, and Cartesian products of complete graphs and of paths, we enumerate the digitally convex sets using recurrence relations. Finally, we enumerate the digitally convex sets of block graphs in terms of the number of blocks in the graph, rather than in terms of the order of the graph.
Advisors/Committee Members: Oellermann, Ortrud R. (supervisor), Mynhardt, C. M. (supervisor).
Subjects/Keywords: graph; convex; digitally convex; graph theory
to Zotero / EndNote / Reference
APA (6th Edition):
Carr, M. (2020). Enumerating digitally convex sets in graphs. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/11938
Chicago Manual of Style (16th Edition):
Carr, MacKenzie. “Enumerating digitally convex sets in graphs.” 2020. Masters Thesis, University of Victoria. Accessed October 19, 2020.
MLA Handbook (7th Edition):
Carr, MacKenzie. “Enumerating digitally convex sets in graphs.” 2020. Web. 19 Oct 2020.
Carr M. Enumerating digitally convex sets in graphs. [Internet] [Masters thesis]. University of Victoria; 2020. [cited 2020 Oct 19].
Available from: http://hdl.handle.net/1828/11938.
Council of Science Editors:
Carr M. Enumerating digitally convex sets in graphs. [Masters Thesis]. University of Victoria; 2020. Available from: http://hdl.handle.net/1828/11938