Digital repository of Slovenian research organisations

Search the repository
A+ | A- | Help | SLO | ENG

Query: search in
search in
search in
search in

Options:
  Reset


Query: "keywords" (number of trees) .

1 - 2 / 2
First pagePrevious page1Next pageLast page
1.
Computational complexity aspects of super domination
Csilla 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: 96; Downloads: 56
.pdf Full text (453,39 KB)
This document has many files! More...

2.
General position polynomials
Vesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite, 2024, original scientific article

Abstract: 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.
Keywords: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs
Published in DiRROS: 28.02.2024; Views: 125; Downloads: 84
.pdf Full text (384,07 KB)
This document has many files! More...
Search done in 0.07 sec.
Back to top