Journal article

On graphs with maximum size in their switching classes

Year:

2015

Published in:

Charles University in Prague
Seidel switching
switching class
maximum size graph

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.

Related by author

24 publications found

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

2025
Journal article

Graphs With Odd And Even Distances Between Non‑Cut Vertices

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko, Kateryna Antoshyna

2024
Journal article

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

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

2025
Conference proceedings

Полідерева зі слабко зв’язними реберними орграфами

Publisher: КПІ ім. Ігоря Сікорського

Authors: Sergiy Kozerenko, Bohdan-Yarema Dekhtiar

2025
Conference proceedings

Unique eccentric point graphs of diameter at most four

Publisher: XV Ukraine Algebra Conference

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

2020
Journal article

Periods In XOR Parallel Dynamical Systems Over Directed Dependency Graphs

Publisher: Applied Mathematics and Computation

Authors: Sergiy Kozerenko, Jose C. Valverde

2017
Journal article

On The Abstract Properties Of Markov Graphs For Maps On Trees

Publisher: Matematicki Bilten

Authors: Sergiy Kozerenko

2021
Journal article

More On Linear And Metric Tree Maps

Publisher: Opuscula Mathematica

Authors: Sergiy Kozerenko