Advanced search options

You searched for `subject:(digitally convex)`

. One record found.

▼ Search Limiters

University of Victoria

1.
Carr, MacKenzie.
Enumerating *digitally* *convex* sets in graphs.

Degree: Department of Mathematics and Statistics, 2020, University of Victoria

URL: http://hdl.handle.net/1828/11938

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

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} 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 (16^{th} Edition):

Carr, MacKenzie. “Enumerating digitally convex sets in graphs.” 2020. Masters Thesis, University of Victoria. Accessed October 19, 2020. http://hdl.handle.net/1828/11938.

MLA Handbook (7^{th} Edition):

Carr, MacKenzie. “Enumerating digitally convex sets in graphs.” 2020. Web. 19 Oct 2020.

Vancouver:

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