Кафедра математики

Permanent URI for this collection

https://ekmair.ukma.edu.ua/handle/123456789/12312

Browse

Browsing Кафедра математики by Author "Kozerenko, Sergiy"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    All-path convexity: two characterizations, general position number, and one algorithm
    (2024) Haponenko, Vladyslav; Kozerenko, Sergiy
    We present two characterizations for the all-path convex sets in graphs. Using the first criterion, we obtain a new characterization of connected block graphs and compute the general position number in a graph with respect to the all-path convexity. The second criterion allows us to provide a new algorithm for testing a set on all-path convexity.
  • Thumbnail Image
    Item
    Dynamical structure of metric and linear self-maps on combinatorial trees
    (2024) Kozerenko, Sergiy
    The dynamical structure of metric and linear self-maps on combinatorial trees is described. Specifically, the following question is addressed: given a map from a finite set to itself, under what conditions there exists a tree on this set such that the given map is either a metric or a linear map on this tree? The author proves that a necessary and sufficient condition for this is that the map has either a fixed point or a periodic point with period two, in which case all its periodic points must have even periods. The dynamical structure of tree automorphisms and endomorphisms is also described in a similar manner.
  • Thumbnail Image
    Item
    Graphs with odd and even distances between non-cut vertices
    (2025) Antoshyna, Kateryna; Kozerenko, Sergiy
    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.
  • Thumbnail Image
    Item
    On strongly connected Markov graphs of maps on combinatorial trees
    (2025) Kozerenko, Sergiy
    Markov graphs form a special class of digraphs constructed from self-maps on the vertex sets of combinatorial trees. In this paper, the trees that admit cyclic permutations of their vertex sets with non-strongly connected Markov graphs in terms of the existence of a special subset of edges are characterized. Additionally, the structure of self-maps of finite sets, which produce strongly connected Markov graphs for all trees, is described. A similar question, concerning which self-maps produce strongly connected Markov graphs for some trees, is answered for the class of permutations.
  • Thumbnail Image
    Item
    An optimal lower bound for the size of periodic digraphs
    (2023) Kozerenko, Sergiy
    A periodic digraph is the digraph associated with a periodic point of a continuous map from the unit interval to itself. This digraph encodes "covering" relation between minimal intervals in the corresponding orbit, which allows the application of purely combinatorial arguments in establishing results on the existence and co-existence of periods of periodic points (for example, in proving the famous Sharkovsky’s theorem). In this article, an optimal lower bound for the size of periodic digraphs is provided and thus some previous results of Pavlenko are tightened.
  • Thumbnail Image
    Item
    Unique eccentric point graphs and their eccentric digraphs
    (2023) Hak, Artem; Haponenko, Vladyslav; Kozerenko, Sergiy; Serdiuk, Andrii
    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.
  • Thumbnail Image
    Item
    The Unitary Cayley Graph of Upper Triangular Matrix Rings
    (2024) Hołubowski, Waldemar; Kozerenko, Sergiy; Oliynyk, Bogdana; Solomko, Viktoriia
    The unitary Cayley graph CR of a finite unital ring R is the simple graph with vertex set R in which two elements x and y are connected by an edge if and only if x − y is a unit of R. We characterize the unitary Cayley graph CTn(F) of the ring of all upper triangular matrices Tn(F) over a finite field F. We show that CTn(F) is isomorphic to the semistrong product of the complete graph Km and the antipodal graph of the Hamming graph A(H(n, pk)), where m = p kn(n−1) 2 and |F| = pk. In particular, if |F| = 2, then the graph CTn(F) has 2n−1 connected components, each component is isomorphic to the complete bipartite graph Km,m, where m = 2 n(n−1) 2 . We also compute the diameter, triameter, and clique number of the graph CTn(F).