Induced-paired domatic numbers of graphs

Bohdan Zelinka

Displaying similar documents to “Induced-paired domatic numbers of graphs”

Antidomatic number of a graph

Bohdan Zelinka (1997)

Archivum Mathematicum

Similarity:

A subset $D$ of the vertex set $V (G)$ of a graph $G$ is called dominating in $G$ , if for each $x \in V (G) - D$ there exists $y \in D$ adjacent to $x$ . An antidomatic partition of $G$ is a partition of $V (G)$ , none of whose classes is a dominating set in $G$ . The minimum number of classes of an antidomatic partition of $G$ is the number $\bar{d} (G)$ of $G$ . Its properties are studied.

A note on the domination number of a graph and its complement

Dănuţ Marcu (2001)

Mathematica Bohemica

Similarity:

If $G$ is a simple graph of size $n$ without isolated vertices and $\bar{G}$ is its complement, we show that the domination numbers of $G$ and $\bar{G}$ satisfy $γ (G) + γ (\bar{G}) \leq \}\begin{matrix} n - δ + 2 if γ (G) > 3, δ + 3 if γ (\bar{G}) > 3, \end{matrix}$ where $δ$ is the minimum degree of vertices in $G$ .

Domination in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_{i}$ denote the least number of vertices needed in G to dominate $V_{i}$ . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...