Search

An edge imbalance provides a local measure of how irregular a given graph is. In this paper, we study graphs with graphic imbalance sequences. We give a new proof of imbalance graphicness for trees and use the new idea to prove that the same holds for unicyclic graphs. We then show that antiregular graphs are imbalance graphic and consider the join operation on graphs as well as the double graph operation. Our main results are concerning imbalance graphicness of three classes of block graphs: block graphs having all cut vertices in a single block; block graphs in which the subgraph induced by the cut vertices is either a star or a path. In the end, we discuss open questions and conjectures regarding imbalance graphic graphs. [ABSTRACT FROM AUTHOR]

In this article, we answer three questions from the paper (Das, 2021). We observe a tight lower bound for the triameter of trees in terms of order and number of leaves. We show that in a connected block graph any triametral triple of vertices contains a diametral pair and that any diametral pair of vertices can be extended to a triametral triple. We also present several open problems concerning the interplay between triametral triples, diametral pairs and peripheral vertices in median and distance-hereditary graphs. [ABSTRACT FROM AUTHOR]

We consider linear and metric self-maps on vertex sets of finite combinatorial trees. Linear maps are maps which preserve intervals between pairs of vertices whereas metric maps are maps which do not increase distances between pairs of vertices. We obtain criteria for a given linear or a metric map to be a positive (negative) under some orientation of the edges in a tree, we characterize trees which admit maps with Markov graphs being paths and prove that the converse of any partial functional digraph is isomorphic to a Markov graph for some suitable map on a tree. [ABSTRACT FROM AUTHOR]

With every self-map on the vertex set of a finite tree one can associate the directed graph of a special type which is called the Markov graph. Expansive and anti-expansive tree maps are two extremal classes of maps with respect to the number of loops in their Markov graphs. In this paper we prove that a tree with at least two vertices has a perfect matching if and only if it admits an expansive cyclic permutation of its vertices. Also, we show that for every tree with at least three vertices there exists an expansive map with a weakly connected (strongly connected provided the tree has a perfect matching) Markov graph as well as anti-expansive map with a strongly connected Markov graph. [ABSTRACT FROM AUTHOR]

We analyze the periodic structure of parallel dynamical systems over directed dependency graphs, whose evolution operator is the Boolean function XOR. We prove that such systems can present periodic orbits of any period. Moreover, we demonstrate that any kinds of periods can coexist at the same time. In view of these results, we study the periodic structure of these dynamical systems over complete digraphs, complete bipartite digraphs, acyclic digraphs and out-trees. [ABSTRACT FROM AUTHOR]

The imbalance of a given edge in a graph is the absolute difference between the degrees of its vertices. The multiset of all edge imbalances in G is called its imbalance sequence and denoted by MG. In this paper, we focus on unary and binary graph operations that preserve the graphicness of imbalance sequences. For example, we prove that if a graph G' is obtained from G by "replacing" each vertex with a complete graph of sufficiently large order, then the graphicness of MG implies the graphicness of MG0. Also, we discuss several conjectures related to the graphicness of the imbalance sequence of a graph and explore connections between them. [ABSTRACT FROM AUTHOR]

We study graph-theoretic properties of eccentric digraphs of unique eccentric point graphs (shortly, uep-graphs). The latter are the connected graphs in which every vertex has a unique eccentric vertex. In particular, we characterize uep-graphs and the corresponding eccentric digraphs in the following classes: self-centered graphs having the number of vertices twice as diameter, block graphs, and graphs with diameter three. Also, we obtain non-trivial properties of weak components in eccentric digraphs of uep-graphs with diameter four and pose several open questions in this direction. [ABSTRACT FROM AUTHOR]