Domination problems in directed graphs and weighted graphs

Dijkstra, Lukas 2025. Domination problems in directed graphs and weighted graphs. PhD Thesis, Cardiff University. Item availability restricted.

Preview	PDF - Accepted Post-Print Version Download (774kB) | Preview
	PDF (Cardiff University Electronic Publication Form) - Supplemental Material Restricted to Repository staff only Download (447kB)

Abstract

A dominating set in a graph G is a set of vertices X such that every vertex v in G is either in X or is connected by an edge {u,v} to a vertex u in X. Given a positive integer k, a k-dominating set Y in G requires every vertex v not in Y to be connected by some edges to a total of k vertices u1,...,uk in Y. A k-tuple dominating set Z in G instead requires every vertex v in G to be connected by some edges to k vertices u1,...,uk in Z (here v is considered to be connected to itself). The last two generalisations are often referred to as multiple dominating sets. The domination number γ(G) of G is the size of the smallest possible dominat ing set in G. There are also equivalent definitions for the k-domination number γk(G), as well as the k-tuple domination number γ×k(G). The research presented in this thesis consists of studying and developing vari ous methods of finding small and minimum size multiple dominating sets, along side generalisations of the problems to directed and vertex-weighted graphs. This includes providing new upper bounds for several multiple and weighted domi nation problems, in addition to new heuristic algorithms for efficiently finding small size multiple dominating sets in digraphs and low-weight dominating sets in vertex-weighted graphs. An analysis of the effectiveness of some of the heuris tics as approximation algorithms is also provided. A deterministic algorithm for f inding minimum size multiple dominating sets in small simple graphs is pre sented as well. The heuristic and deterministic algorithms and methods are then implemented, and computational experiments are conducted on large randomly generated vertex-weighted graphs and digraphs, as well as digraphs modelling real-world road networks

Item Type:	Thesis (PhD)
Date Type:	Completion
Status:	Unpublished
Schools:	Schools > Mathematics
Uncontrolled Keywords:	1. Graph theory 2. Dominating sets 3. Domination numbers 4. Directed graphs 5. Vertex-weighted graphs 6. Road networks
Funders:	EPSRC
Projects:	EP/V520159/1
Date of First Compliant Deposit:	31 March 2026
Last Modified:	01 Apr 2026 14:20
URI:	https://orca.cardiff.ac.uk/id/eprint/186103

Actions (repository staff only)

Edit Item