Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `+publisher:"University of Victoria" +contributor:("Oellermann, Ortrud R.")`

.
Showing records 1 – 2 of
2 total matches.

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

MLA Handbook (7^{th} Edition):

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

Vancouver:

Carr M. Enumerating digitally convex sets in graphs. [Internet] [Masters thesis]. University of Victoria; 2020. [cited 2020 Oct 22]. 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

University of Victoria

2. Anderson, Rachel Jean Selma. Graph Convexity and Vertex Orderings.

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

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

In discrete mathematics, a convex space is an ordered pair (V,M) where M is a family of subsets of a finite set V , such that: ∅ ∈M, V ∈M, andMis closed under intersection. The elements of M are called convex sets. For a set S ⊆ V , the convex hull of S is the smallest convex set that contains S. A point x of a convex set X is an extreme point of X if X{x} is also convex. A convex space (V,M) with the property that every convex set is the convex hull of its extreme points is called a convex geometry. A graph G has a P-elimination ordering if an ordering v1, v2, ..., vn of the vertices exists such that vi has property P in the graph induced by vertices vi, vi+1, ..., vn for all i = 1, 2, ...,n. Farber and Jamison [18] showed that for a convex geometry (V,M), X ∈Mif and only if there is an ordering v1, v2, ..., vk of the points of V − X such that vi is an extreme point of {vi, vi+1, ..., vk}∪ X for each i = 1, 2, ...,k. With these concepts in mind, this thesis surveys the literature and summarizes results regarding graph convexities and elimination orderings. These results include classifying graphs for which different types of convexities give convex geometries, and classifying graphs for which different vertex ordering algorithms result in a P-elimination ordering, for P the characteristic property of the extreme points of the convexity. We consider the geodesic, monophonic, m3, 3-Steiner and 3-monophonic convexities, and the vertex ordering algorithms LexBFS, MCS, MEC and MCC. By considering LexDFS, a recently introduced vertex ordering algorithm of Corneil and Krueger [11], we obtain new results: these are characterizations of graphs for which all LexDFS orderings of all induced subgraphs are P-elimination orderings, for every characteristic property P of the extreme vertices for the convexities studied in this thesis.
*Advisors/Committee Members: Oellermann, Ortrud R. (supervisor), MacGillivray, Gary (supervisor).*

Subjects/Keywords: discrete mathematics; graph theory; graph convexity; vertex orderings; vertex ordering algorithms

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Anderson, R. J. S. (2014). Graph Convexity and Vertex Orderings. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/5289

Chicago Manual of Style (16^{th} Edition):

Anderson, Rachel Jean Selma. “Graph Convexity and Vertex Orderings.” 2014. Masters Thesis, University of Victoria. Accessed October 22, 2020. http://hdl.handle.net/1828/5289.

MLA Handbook (7^{th} Edition):

Anderson, Rachel Jean Selma. “Graph Convexity and Vertex Orderings.” 2014. Web. 22 Oct 2020.

Vancouver:

Anderson RJS. Graph Convexity and Vertex Orderings. [Internet] [Masters thesis]. University of Victoria; 2014. [cited 2020 Oct 22]. Available from: http://hdl.handle.net/1828/5289.

Council of Science Editors:

Anderson RJS. Graph Convexity and Vertex Orderings. [Masters Thesis]. University of Victoria; 2014. Available from: http://hdl.handle.net/1828/5289