Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Opuscula Mathematica

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: total domination

Sortuj według:

Ogranicz wyniki do:

Graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set

Haynes Teresa W., Henning Michael A.

Opuscula Mathematica

2024

Vol. 44, no. 4

543--563

A graph G whose vertex set can be partitioned into a total dominating set and an independent dominating set is called a TI-graph. We give constructions that yield infinite families of graphs that are TI-graphs, as well as constructions that yield infinite families of graphs that are not TI-graphs. We study regular graphs that are TI-graphs. Among other results, we prove that all toroidal graphs are TI-graphs.

The complexity of open k-monopolies in graphs for negative k

Peterin Iztok

Opuscula Mathematica

2019

Vol. 39, no. 3

425--431

Let G be a graph with vertex set V(G), δ (G) minimum degree of G and [formula]. Given a nonempty set M ⊆ V(G) a vertex v of G is said to be k-controlled by M if [formula] where δM(v) represents the number of neighbors of v in M. The set M is called an open k-monopoly for G if it fc-controls every vertex v of G. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer k is NP-complete even restricted to chordal graphs.

An upper bound on the total outer-independent domination number of a tree

Krzywkowski M.

Opuscula Mathematica

2012

Vol. 32, no. 1

153-158

A total outer-independent dominating set of a graph G = (V (G),E(G)) is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V (G) \ D is independent. The total outer-independent domination number of a graph G, denoted by [formula], is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every tree T of order n ≥ 4, with l leaves and s support vertices we have [formula], and we characterize the trees attaining this upper bound.

Neighbourhood total domination in graphs

Arumugam S., Sivagnanam C.

Opuscula Mathematica

2011

Vol. 31, no. 4

519-531

Let G = (V, E) be a graph without isolated vertices. A dominating set S of G is called a neighbourhood total dominating set (ntd-set) if the induced subgraph 〈 N(S) 〉 has no isolated vertices. The minimum cardinality of a ntd-set of G is called the neighbourhood total domination number of G and is denoted by ϒnt(G). The maximum order of a partition of V into ntd-sets is called the neighbourhood total domatic number of G and is denoted by dnt(G). In this paper we initiate a study of these parameters.