Source author record

Ortrud R. Oellermann

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Enumerating the Digitally Convex Sets of Powers of Cycles and Cartesian Products of Paths and Complete Graphs

Given a finite set $V$ , a convexity $\mathscr{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 $\mathscr{C}$ are called convex sets. The digital convexity, originally proposed as a tool for processing digital images, is defined as follows: a subset $S\subseteq V(G)$ is digitally convex if, for every $v\in V(G)$ , we have $N[v]\subseteq N[S]$ implies $v\in S$ . The number of cyclic binary strings with blocks of length at least $k$ is expressed as a linear recurrence relation for $k\geq 2$ . A bijection is established between these cyclic binary strings and the digitally convex sets of the $(k-1)^{th}$ power of a cycle. A closed formula for the number of digitally convex sets of the Cartesian product of two complete graphs is derived. A bijection is established between the digitally convex sets of the Cartesian product of two paths, $P_n \square P_m$ , and certain types of $n \times m$ binary arrays.

preprint2020arXiv

The Threshold Dimension and Irreducible Graphs

Let $G$ be a graph, and let $u$ , $v$ , and $w$ be vertices of $G$ . If the distance between $u$ and $w$ does not equal the distance between $v$ and $w$ , then $w$ is said to resolve $u$ and $v$ . The metric dimension of $G$ , denoted $β(G)$ , is the cardinality of a smallest set $W$ of vertices such that every pair of vertices of $G$ is resolved by some vertex of $W$ . The threshold dimension of $G$ , denoted $τ(G)$ , is the minimum metric dimension among all graphs $H$ having $G$ as a spanning subgraph. In other words, the threshold dimension of $G$ is the minimum metric dimension among all graphs obtained from $G$ by adding edges. If $β(G) = τ(G)$ , then $G$ is said to be irreducible. We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order $n$ has threshold dimension $O (\log_2 n)$ . We show that several infinite families of graphs, known to have metric dimension $3$ , are in fact irreducible. Finally, we show that for any integers $n$ and $b$ with $1 \leq b < n$ , there is an irreducible graph of order $n$ and metric dimension $b$ .

preprint2020arXiv

The Threshold Dimension of a Graph

Let $G$ be a graph, and let $u$ , $v$ , and $w$ be vertices of $G$ . If the distance between $u$ and $w$ does not equal the distance between $v$ and $w$ , then $w$ is said to resolve $u$ and $v$ . The metric dimension of $G$ , denoted $β(G)$ , is the cardinality of a smallest set $W$ of vertices such that every pair of vertices of $G$ is resolved by some vertex of $W$ . The threshold dimension of a graph $G$ , denoted $τ(G)$ , is the minimum metric dimension among all graphs $H$ having $G$ as a spanning subgraph. In other words, the threshold dimension of $G$ is the minimum metric dimension among all graphs obtained from $G$ by adding edges. If $β(G) = τ(G)$ , then $G$ is said to be \emph{irreducible}; otherwise, we say that $G$ is reducible. If $H$ is a graph having $G$ as a spanning subgraph and such that $β(H)=τ(G)$ , then $H$ is called a threshold graph of $G$ . The threshold dimension of a graph is expressed in terms of a minimum number of strong products of paths that admits a certain type of embedding of the graph. A sharp upper bound for the threshold dimension of trees is established. It is also shown that the irreducible trees are precisely those of metric dimension at most 2. Moreover, if $T$ is a tree with metric dimension 3 or 4, then $T$ has threshold dimension $2$ . It is shown, in these two cases, that a threshold graph for $T$ can be obtained by adding exactly one or two edges to $T$ , respectively. However, these results do not extend to trees with metric dimension $5$ , i.e., there are trees of metric dimension $5$ with threshold dimension exceeding $2$ .

preprint2020arXiv

The Threshold Strong Dimension of a Graph

Let $G$ be a connected graph and $u,v$ and $w$ vertices of $G$ . Then $w$ is said to {\em strongly resolve} $u$ and $v$ , if there is either a shortest $u$ - $w$ path that contains $v$ or a shortest $v$ - $w$ path that contains $u$ . A set $W$ of vertices of $G$ is a {\em strong resolving set} if every pair of vertices of $G$ is strongly resolved by some vertex of $W$ . A smallest strong resolving set of a graph is called a {\em strong basis} and its cardinality, denoted $β_s(G)$ , the {\em strong dimension} of $G$ . The {\em threshold strong dimension} of a graph $G$ , denoted $τ_s(G)$ , is the smallest strong dimension among all graphs having $G$ as spanning subgraph. A graph whose strong dimension equals its threshold strong dimension is called $β_s$ -{\em irreducible}. In this paper we establish a geometric characterization for the threshold strong dimension of a graph $G$ that is expressed in terms of the smallest number of paths (each of sufficiently large order) whose strong product admits a certain type of embedding of $G$ . We demonstrate that the threshold strong dimension of a graph is not equal to the previously studied threshold dimension of a graph. Graphs with strong dimension $1$ and $2$ are necessarily $β_s$ -irreducible. It is well-known that the only graphs with strong dimension $1$ are the paths. We completely describe graphs with strong dimension $2$ in terms of the strong resolving graphs introduced by Oellermann and Peters-Fransen. We obtain sharp upper bounds for the threshold strong dimension of general graphs and determine exact values for this invariant for certain subclasses of trees.

preprint2016arXiv

Global cycle properties in graphs with large minimum clustering coefficient

The clustering coefficient of a vertex in a graph is the proportion of neighbours of the vertex that are adjacent. The minimum clustering coefficient of a graph is the smallest clustering coefficient taken over all vertices. A complete structural characterization of those locally connected graphs, with minimum clustering coefficient 1/2 and maximum degree at most 6, that are fully cycle extendable is given in terms of strongly induced subgraphs with given attachment sets. Moreover, it is shown that all locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 are weakly pancyclic, thereby proving Ryjacek's conjecture for this class of locally connected graphs.

preprint2016arXiv

Global cycle properties in locally isometric graphs

A graph G is locally isometric if the subgraph induced by the neighbourhood of every vertex is an isometric subgraph of G. It is shown that the hamilton cycle problem for locally isometric graphs with maximum degree at most 8 is NP-complete. Structural characterizations of locally isometric graphs, with maximum degree at most 6, that are fully cycle extendable, are established and these results are used to show that locally isometric graphs with maximum degree at most 6 are weakly pancyclic. This proves Ryjacek's conjecture for a subclass of locally connected graphs.

preprint2013arXiv

On the strong metric dimension of Cartesian and direct products of graphs

Let $G$ be a connected graph. A vertex $w$ {\em strongly resolves} a pair $u, v$ of vertices of $G$ if there exists some shortest $u-w$ path containing $v$ or some shortest $v-w$ path containing $u$ . A set $W$ of vertices is a {\em strong resolving set} for $G$ if every pair of vertices of $G$ is strongly resolved by some vertex of $W$ . The smallest cardinality of a strong resolving set for $G$ is called the {\em strong metric dimension} of $G$ . It is known that the problem of computing the strong metric dimension of a graph is NP-hard. In this paper we obtain closed formulae for the strong metric dimension of several families of Cartesian product graphs and direct product graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ortrud R. Oellermann

Research overview

Is this your work?

7 publications

Enumerating the Digitally Convex Sets of Powers of Cycles and Cartesian Products of Paths and Complete Graphs

The Threshold Dimension and Irreducible Graphs

The Threshold Dimension of a Graph

The Threshold Strong Dimension of a Graph

Global cycle properties in graphs with large minimum clustering coefficient

Global cycle properties in locally isometric graphs

On the strong metric dimension of Cartesian and direct products of graphs

See the researcher in context

Building this map preview