The cobondage number of a graph

V.R. Kulli; B. Janakiram

Displaying similar documents to “The cobondage number of a graph”

A bound on the $k$ -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a graph with vertex set $V (G)$ , and let $k \geq 1$ be an integer. A subset $D \subseteq V (G)$ is called a if every vertex $v \in V (G) - D$ has at least $k$ neighbors in $D$ . The $k$ -domination number $γ_{k} (G)$ of $G$ is the minimum cardinality of a $k$ -dominating set in $G$ . If $G$ is a graph with minimum degree $δ (G) \geq k + 1$ , then we prove that $γ_{k + 1} (G) \leq \frac{| V (G) | + γ_{k} (G)}{2} .$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand, Donald W. Vanderjagt, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

A 2-stratified graph $G$ is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of $G$ . Two $2$ -stratified graphs $G$ and $H$ are isomorphic if there exists a color-preserving isomorphism $φ$ from $G$ to $H$ . A $2$ -stratified graph $G$ is said to be homogeneously embedded in a $2$ -stratified graph $H$ if for every vertex $x$ of $G$ and every vertex $y$ of $H$ , where $x$ and $y$ are colored the same, there exists an induced $2$ -stratified subgraph $H^{'}$ of $H$ containing $y$ and a color-preserving...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

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$ .

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star $K_{1, t}$ . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

Displaying similar documents to “The cobondage number of a graph”

A bound on the k -domination number of a graph

Homogeneously embedding stratified graphs in stratified graphs

Restrained domination in unicyclic graphs

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

Vertex-disjoint stars in graphs

A bound on the $k$ -domination number of a graph