Advanced search options

Advanced Search Options 🞨

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

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

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

Search Limiters

Last 2 Years | English Only

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 RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

.