Source author record

Sonwabile Mafunda

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

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

An Extremal Problem on Rainbow Spanning Trees in Graphs

A spanning tree of an edge-colored graph is rainbow provided that each of its edges receives a distinct color. In this paper we consider the natural extremal problem of maximizing and minimizing the number of rainbow spanning trees in a graph $G$ . Such a question clearly needs restrictions on the colorings to be meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles, known in the literature as JL-colorings, there turns out to be a particularly nice way of counting the rainbow spanning trees and we solve this problem completely for JL-colored complete graphs $K_n$ and complete bipartite graphs $K_{n,m}$ . In both cases, we find tight upper and lower bounds; the lower bound for $K_n$ , in particular, proves to have an unexpectedly chaotic and interesting behavior. We further investigate this question for JL-colorings of general graphs and prove several results including characterizing graphs which have JL-colorings achieving the lowest possible number of rainbow spanning trees. We establish other results for general $n-1$ colorings, including providing an analogue of Kirchoff's matrix tree theorem which yields a way of counting rainbow spanning trees in a general graph $G$ .

preprint2020arXiv

Proximity and Remoteness in Directed and Undirected Graphs

Let $D$ be a strongly connected digraph. The average distance $\barσ(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$ . The remoteness $ρ(D)$ and proximity $π(D)$ of $D$ are the maximum and the minimum of the average distances of the vertices of $D$ , respectively. We obtain sharp upper and lower bounds on $π(D)$ and $ρ(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$ , we have $π(T)=ρ(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $π(D)=ρ(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $π(D)=ρ(D).$ We describe such a family for undirected graphs as well.

preprint2020arXiv

Proximity and remoteness in triangle-free and C_4-free graphs in terms of order and minimum degree

Let $G$ be a finite, connected graph. The average distance of a vertex $v$ of $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$ . The remoteness $ρ(G)$ and the proximity $π(G)$ of $G$ are the maximum and the minimum of the average distances of the vertices of $G$ . In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of $C_4$ -free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.

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.

Sonwabile Mafunda

Research overview

Is this your work?

3 publications

An Extremal Problem on Rainbow Spanning Trees in Graphs

Proximity and Remoteness in Directed and Undirected Graphs

Proximity and remoteness in triangle-free and C_4-free graphs in terms of order and minimum degree

See the researcher in context

Building this map preview