1. |
2. Perfect matching cuts partitioning a graph into complementary subgraphsDiane Castonguay, Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento, Uéverton S. Souza, 2025, original scientific article 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: 686; Downloads: 3
 Full text (420,94 KB) |
3. Posplošitev Lijeve domneve in popolna klasifikacija cikličnih m-(D)CI-grup : magistrsko deloLuka Šinkovec, 2023, master's thesis Keywords: (un)directed Cayley graph, cyclic group, (un)directed circulant graph, Cayley isomorphism, (un)directed CI-graph, (D)CI-group, m-(D)CI-group, key, generalised multiplier
Published in RUP: 11.09.2023; Views: 2373; Downloads: 40
Full text (520,27 KB) |
4. The automorphism groups of non-edge transitive rose window graphsEdward Tauscher Dobson, István Kovács, Štefko Miklavič, 2015, original scientific article 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: 2964; Downloads: 45
Full text (275,74 KB) |
5. |
6. |
7. |
8. |
9. |
10. |
