1 March 2022 in Discrete Applied Mathematics
1 January 2023 in Opuscula Mathematica
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.
1 January 2025 in Opuscula Mathematica
We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation.
25 July 2023 in Discrete Mathematics
10 March 2015 in Commentationes Mathematicae Universitatis Carolinae
In his PhD thesis [Structural aspects of switching classes, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: “characterize the maximum size graphs in switching classes”. These are called s-maximal graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization of triangle-free s-maximal graphs and non-hamiltonian s-maximal graphs. We also obtain other interesting properties of s-maximal graphs.
1 January 2021 in Opuscula Mathematica
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.