11. Invariants of multi-linkoidsBoštjan Gabrovšek, Neslihan Gügümcü, 2023, original scientific article Abstract: In this paper, we extend the definition of a knotoid to multilinkoids that consist of a finite number of knot and knotoid components. We study invariants of multi-linkoids, such as the Kauffman bracket polynomial, ordered bracket polynomial, the Kauffman skein module, and the $T$-invariant in relation with generalized $\Theta$-graphs.
Keywords: knotoid, multi-linkoid, spatial graph, Kauffman bracket polynomial, Kauffman bracket skein module, theta-curve, theta-graph
Published in DiRROS: 15.03.2024; Views: 112; Downloads: 66
 Full text (924,28 KB)
This document has many files! More... |
12. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, original scientific article Abstract: Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine.
Keywords: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number
Published in DiRROS: 14.03.2024; Views: 122; Downloads: 63
Full text (453,39 KB)
This document has many files! More... |
13. Outerplane bipartite graphs with isomorphic resonance graphsSimon Brezovnik, Zhongyuan Che, Niko Tratnik, Petra Žigert Pleteršek, 2024, original scientific article Abstract: We present novel results related to isomorphic resonance graphs of 2-connected outerplane bipartite graphs. As the main result, we provide a structure characterization for 2-connected outerplane bipartite graphs with isomorphic resonance graphs. Three additional characterizations are expressed in terms of resonance digraphs, via local structures of inner duals, as well as using distributive lattices on the set of order ideals of posets defined on inner faces of 2-connected outerplane bipartite graphs.
Keywords: distributive lattice, inner dual, isomorphic resonance graphs, order ideal, 2-connected outerplane bipartite graph
Published in DiRROS: 13.03.2024; Views: 120; Downloads: 64
Full text (452,02 KB)
This document has many files! More... |
14. Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problemSandi Klavžar, Eva Zmazek, 2024, original scientific article Abstract: A set of vertices $X$ of a graph $G$ is a strong edge geodetic set if to any pair of vertices from $X$ we can assign one (or zero) shortest path between them such that every edge of $G$ is contained in at least one on these paths. The cardinality of a smallest strong edge geodetic set of $G$ is the strong edge geodetic number ${\rm sg_e}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with ${\rm sg_e}(G) = n(G)$ are characterized and ${\rm sg_e}$ is determined for Cartesian products $P_n\,\square\, K_m$. The latter result in particular corrects an error from the literature.
Keywords: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
Published in DiRROS: 19.02.2024; Views: 165; Downloads: 68
Full text (430,75 KB)
This document has many files! More... |
15. |
