11. Invariants of multi-linkoidsBoštjan Gabrovšek, Neslihan Gügümcü, 2023, izvirni znanstveni članek Povzetek: 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.
Ključne besede: knotoid, multi-linkoid, spatial graph, Kauffman bracket polynomial, Kauffman bracket skein module, theta-curve, theta-graph
Objavljeno v DiRROS: 15.03.2024; Ogledov: 111; Prenosov: 66
 Celotno besedilo (924,28 KB)
Gradivo ima več datotek! Več... |
12. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, izvirni znanstveni članek Povzetek: 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.
Ključne besede: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number
Objavljeno v DiRROS: 14.03.2024; Ogledov: 118; Prenosov: 62
Celotno besedilo (453,39 KB)
Gradivo ima več datotek! Več... |
13. Outerplane bipartite graphs with isomorphic resonance graphsSimon Brezovnik, Zhongyuan Che, Niko Tratnik, Petra Žigert Pleteršek, 2024, izvirni znanstveni članek Povzetek: 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.
Ključne besede: distributive lattice, inner dual, isomorphic resonance graphs, order ideal, 2-connected outerplane bipartite graph
Objavljeno v DiRROS: 13.03.2024; Ogledov: 120; Prenosov: 64
Celotno besedilo (452,02 KB)
Gradivo ima več datotek! Več... |
14. Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problemSandi Klavžar, Eva Zmazek, 2024, izvirni znanstveni članek Povzetek: 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.
Ključne besede: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
Objavljeno v DiRROS: 19.02.2024; Ogledov: 162; Prenosov: 67
Celotno besedilo (430,75 KB)
Gradivo ima več datotek! Več... |
15. |
