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, izvirni znanstveni članek Opis: 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.
Ključne besede: graph partitioning, complementary subgraphs, perfect matching, matching cut, graph isomorphism
Objavljeno v RUP: 21.10.2025; Ogledov: 364; Prenosov: 2
 Celotno besedilo (420,94 KB) |
3. Posplošitev Lijeve domneve in popolna klasifikacija cikličnih m-(D)CI-grup : magistrsko deloLuka Šinkovec, 2023, magistrsko delo Ključne besede: (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
Objavljeno v RUP: 11.09.2023; Ogledov: 2090; Prenosov: 30
Celotno besedilo (520,27 KB) |
4. The automorphism groups of non-edge transitive rose window graphsEdward Tauscher Dobson, István Kovács, Štefko Miklavič, 2015, izvirni znanstveni članek Opis: 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.
Ključne besede: rose window graphs, automorphism group, isomorphism problem, vertex-transitive graph
Objavljeno v RUP: 31.12.2021; Ogledov: 2663; Prenosov: 44
Celotno besedilo (275,74 KB) |
5. |
6. |
7. |
8. |
9. |
10. |
