Browse by author name (“Author name starts with…”).

Find ETDs with:

 All of these words Any of these words This exact phrase None of these words in any field title author name abstract university/publisher subjects/keywords department/discipline And / Or All of these words Any of these words This exact phrase None of these words in any field title author name abstract university/publisher subjects/keywords department/discipline And / Or All of these words Any of these words This exact phrase None of these words in any field title author name abstract university/publisher subjects/keywords department/discipline And / Or All of these words Any of these words This exact phrase None of these words in any field title author name abstract university/publisher subjects/keywords department/discipline

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for `subject:(digitally convex)`. One record found.

Search Limiters

No search limiters apply to these results.

▼ Search Limiters

University of Victoria

1. Carr, MacKenzie. 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

Record DetailsSimilar Records

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

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. http://hdl.handle.net/1828/11938.

MLA Handbook (7th 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