Journal article

Graphs With Odd And Even Distances Between Non-Cut Vertices

Year:

2025

Published in:

Opuscula Mathematica
non-cut vertex
graph distance
line graph
block
strong unique independence tree

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.

Related by author

10 publications found

2024
Journal article

Dynamical Structure Of Metric And Linear Self‑Maps On Combinatorial Trees

Publisher: Discrete Mathematics Letters

Authors: Sergiy Kozerenko

2016
Journal article

Markov Graphs Of One–Dimensional Dynamical Systems And Their Discrete Analogues

Publisher: Romanian Journal of Mathematics and Computer Science

Authors: Sergiy Kozerenko

2020
Journal article

Periods In XOR Parallel Dynamical Systems Over Directed Dependency Graphs

Publisher: Applied Mathematics and Computation

Authors: Sergiy Kozerenko, Jose C. Valverde

2021
Journal article

More On Linear And Metric Tree Maps

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko

2023
Journal article

An Optimal Lower Bound For The Size Of Periodic Digraphs

Publisher: Discrete Mathematics Letters

Authors: Sergiy Kozerenko

2023
Journal article

Unique Eccentric Point Graphs And Their Eccentric Digraphs

Publisher: Discrete Mathematics

Authors: Sergiy Kozerenko, Artem Hak, Vladyslav Haponenko, Andrii Serdiuk

2024
Journal article

All‑Path Convexity: Two Characterizations, General Position Number, And One Algorithm

Publisher: Discrete Mathematics Letters

Authors: Sergiy Kozerenko, Vladyslav Haponenko

2017
Journal article

On The Abstract Properties Of Markov Graphs For Maps On Trees

Publisher: Matematicki Bilten

Authors: Sergiy Kozerenko

2018
Journal article

On Expansive And Anti‑Expansive Tree Maps

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko

2023
Working paper

Line Digraphs of Polytrees

Publisher: SSRN

Authors: Sergiy Kozerenko, Bohdan-Yarema Dekhtiar

You have reached the end of the list