Source author record

Audace A. V. Dossou-Olory

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On isomorphism classes of leaf-induced subtrees in topological trees

A subtree can be induced in a natural way by a subset of leaves of a rooted tree. We study the number of nonisomorphic such subtrees induced by leaves (leaf-induced subtrees) of a rooted tree with no vertex of outdegree 1 (topological tree). We show that only stars and binary caterpillars have the minimum nonisomorphic leaf-induced subtrees among all topological trees with a given number of leaves. We obtain a closed formula and a recursive formula for the families of $d$ -ary caterpillars and complete $d$ -ary trees, respectively. An asymptotic formula is found for complete $d$ -ary trees using polynomial recurrences. We also show that the complete binary tree of height $h>1$ contains precisely $\lfloor 2(1.24602...)^{2^h}\rfloor$ nonisomorphic leaf-induced subtrees.

preprint2020arXiv

Bounding the $k$ -Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence

The eccentric sequence of a connected graph $G$ is the nondecreasing sequence of the eccentricities of its vertices. The Wiener index of $G$ is the sum of the distances between all unordered pairs of vertices of $G$ . The unique trees that minimise the Wiener index among all trees with a given eccentric sequence were recently determined by the present authors. In this paper we show that these results hold not only for the Wiener index, but for a large class of distance-based topological indices which we term Wiener-type indices. Particular cases of this class include the hyper-Wiener index, the Harary index, the generalised Wiener index $W^λ$ for $λ>0$ and $λ<0$ , and the reciprocal complementary Wiener index. Our results imply and unify known bounds on these Wiener-type indices for trees of given order and diameter. We also present similar results for the $k$ -Steiner Wiener index of trees with a given eccentric sequence. The Steiner distance of a set $A\subseteq V(G)$ is theminimum number of edges in a subtree of $G$ whose vertex set contains $A$ , and the $k$ -Steiner Wiener index is the sum of distances of all $k$ -element subsets of $V(G)$ . As a corollary, we obtain a sharp lower bound on the $k$ -Steiner Wiener index of trees with given order and diameter, and determine in which cases the extremal tree is unique, thereby correcting an error in the literature.

preprint2020arXiv

Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs

Cut vertices are often used as a measure of nodes' importance within a network. They are those nodes whose failure disconnects a graph. Let N(G) be the number of connected induced subgraphs of a graph $G$ . In this work, we investigate the maximum of N(G) where $G$ is a unicyclic graph with $n$ nodes of which $c$ are cut vertices. For all valid $n,c$ , we give a full description of those maximal (that maximise N(.)) unicyclic graphs. It is found that there are generally two maximal unicyclic graphs. For infinitely many values of $n,c$ , however, there is a unique maximal unicyclic graph with $n$ nodes and $c$ cut vertices. In particular, the well-known negative correlation between the number of connected induced subgraphs of trees and the Wiener index (sum of distances) fails for unicyclic graphs with $n$ nodes and $c$ cut vertices: for instance, the maximal unicyclic graph with $n=3,4\mod 5$ nodes and $c=n-5>3$ cut vertices is different from the unique graph that was shown by Tan et al.~[{\em The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices}. J. Appl. Math. Comput., 55:1--24, 2017] to minimise the Wiener index. Our main characterisation of maximal unicyclic graphs with respect to the number of connected induced subgraphs also applies to unicyclic graphs with $n$ nodes, $c$ cut vertices and girth at most $g>3$ , since it is shown that the girth of every maximal graph with $n$ nodes and $c$ cut vertices cannot exceed $4$ .

preprint2020arXiv

Further results on the inducibility of $d$ -ary trees

A subset of leaves of a rooted tree induces a new tree in a natural way. The density of a tree $D$ inside a larger tree $T$ is the proportion of such leaf-induced subtrees in $T$ that are isomorphic to $D$ among all those with the same number of leaves as $D$ . The inducibility of $D$ measures how large this density can be as the size of $T$ tends to infinity. In this paper, we explicitly determine the inducibility in some previously unknown cases and find general upper and lower bounds, in particular in the case where $D$ is balanced, i.e., when its branches have at least almost the same size. Moreover, we prove a result on the speed of convergence of the maximum density of $D$ in strictly $d$ -ary trees $T$ (trees where every internal vertex has precisely $d$ children) of a given size $n$ to the inducibility as $n \to \infty$ , which supports an open conjecture.

preprint2020arXiv

Wiener index, number of subtrees, and tree eccentric sequence

The eccentricity of a vertex $u$ in a connected graph $G$ is the distance between $u$ and a vertex farthest from it; the eccentric sequence of $G$ is the nondecreasing sequence of the eccentricities of $G$ . In this paper, we determine the unique tree that minimises the Wiener index, i.e. the sum of distances between all unordered vertex pairs, among all trees with a given eccentric sequence. We show that the same tree maximises the number of subtrees among all trees with a given eccentric sequence, thus providing another example of negative correlation between the number of subtrees and the Wiener index of trees. Furthermore, we provide formulas for the corresponding extreme values of these two invariants in terms of the eccentric sequence. As a corollary to our results, we determine the unique tree that minimises the edge Wiener index, the vertex-edge Wiener index, the Schulz index (or degree distance), and the Gutman index among all trees with a given eccentric sequence.

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.

Audace A. V. Dossou-Olory

Research overview

Is this your work?

5 publications

On isomorphism classes of leaf-induced subtrees in topological trees

Bounding the $k$ -Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence

Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs

Further results on the inducibility of $d$ -ary trees

Wiener index, number of subtrees, and tree eccentric sequence

See the researcher in context

Building this map preview

Audace A. V. Dossou-Olory

Research overview

Is this your work?

5 publications

On isomorphism classes of leaf-induced subtrees in topological trees

Bounding the kkk-Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence

Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs

Further results on the inducibility of ddd-ary trees

Wiener index, number of subtrees, and tree eccentric sequence

See the researcher in context

Building this map preview

Bounding the $k$ -Steiner Wiener and Wiener-type indices of trees in terms of eccentric sequence

Further results on the inducibility of $d$ -ary trees