Digitalni repozitorij raziskovalnih organizacij Slovenije

Iskanje po repozitoriju
A+ | A- | Pomoč | SLO | ENG

Iskalni niz: išči po
išči po
išči po
išči po

Možnosti:
  Ponastavi


Iskalni niz: "ključne besede" (number of trees) .

1 - 2 / 2
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Computational complexity aspects of super domination
Csilla 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: 96; Prenosov: 56
.pdf Celotno besedilo (453,39 KB)
Gradivo ima več datotek! Več...

2.
General position polynomials
Vesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite, 2024, izvirni znanstveni članek

Povzetek: A subset of vertices of a graph $G$ is a general position set if no triple of vertices from the set lie on a common shortest path in $G$. In this paper we introduce the general position polynomial as $\sum_{i \geq 0} a_i x^i$, where $a_i$ is the number of distinct general position sets of $G$ with cardinality $i$. The polynomial is considered for several well-known classes of graphs and graph operations. It is shown that the polynomial is not unimodal in general, not even on trees. On the other hand, several classes of graphs, including Kneser graphs $K(n,2)$, with unimodal general position polynomials are presented.
Ključne besede: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs
Objavljeno v DiRROS: 28.02.2024; Ogledov: 126; Prenosov: 84
.pdf Celotno besedilo (384,07 KB)
Gradivo ima več datotek! Več...
Iskanje izvedeno v 0.03 sek.
Na vrh