Search the repository

Abstract: In PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB) we are given a graph G = (V, E), and an edge set property Π, and asked whether G can be decomposed into two graphs, H and its complement H̄, for some graph H, in such a way that the edge cut [V(H), V(H̄)] satisfies the property Π. Motivated by previous work, we consider COMP-SUB(Π) when the property Π=PM specifies that the edge cut of the decomposition is a perfect matching. We prove that COMP-SUB(PM) is GI-hard when the graph G is C_5-free or G is {C_k ≥ 7, C̄_k ≥ 7}-free. On the other hand, we show that COMP-SUB(PM) is polynomial-time solvable on hole-free graphs and on P5-free graphs. Furthermore, we present characterizations of COMP-SUB(PM) on chordal, distance-hereditary, and extended P_4-laden graphs.
Keywords: graph partitioning, complementary subgraphs, perfect matching, matching cut, graph isomorphism
Published in RUP: 21.10.2025; Views: 209; Downloads: 2
Full text (420,94 KB)

Abstract: In this paper, we determine the full automorphism groups of rose window graphs that are not edge-transitive. As the full automorphism groups of edge-transitive rose window graphs have been determined, this complete the problem of calculating the full automorphism group of rose window graphs. As a corollary, we determine which rose window graphs are vertex-transitive. Finally, we determine the isomorphism classes of non-edge-transitive rose window graphs.
Keywords: rose window graphs, automorphism group, isomorphism problem, vertex-transitive graph
Published in RUP: 31.12.2021; Views: 2402; Downloads: 43
Full text (275,74 KB)

Keywords: Cayley isomorphism problem, Cayley graph, CI-group
Published in RUP: 18.07.2018; Views: 3015; Downloads: 93
Link to full text

Keywords: bi-Cayley graph, BCI-group, graph isomorphism
Published in RUP: 02.03.2018; Views: 21473; Downloads: 110
Link to full text

Keywords: cage, graph, isomorphism
Published in RUP: 03.04.2017; Views: 3528; Downloads: 74
Link to full text