Quasiperfect domination in triangular lattices

Italo J. Dejter

Displaying similar documents to “Quasiperfect domination in triangular lattices”

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s d_{γ} (G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...

Coalescing Fiedler and core vertices

Didar A. Ali, John Baptist Gauci, Irene Sciriha, Khidir R. Sharaf (2016)

Czechoslovak Mathematical Journal

Similarity:

The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex...

Matchings and total domination subdivision number in graphs with few induced 4-cycles

Odile Favaron, Hossein Karami, Rana Khoeilar, Seyed Mahmoud Sheikholeslami (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $s d_{γ ₜ (G)}$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal...

Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{\times 2} (G)$ , is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{\times 2}$ -vertex critical graph ( $γ_{\times 2}$ -vertex stable graph, respectively) if the removal of any vertex different...

Inequalities involving independence domination, $f$ -domination, connected and total $f$ -domination numbers

San Ming Zhou (2000)

Czechoslovak Mathematical Journal

Similarity:

Let $f$ be an integer-valued function defined on the vertex set $V (G)$ of a graph $G$ . A subset $D$ of $V (G)$ is an $f$ -dominating set if each vertex $x$ outside $D$ is adjacent to at least $f (x)$ vertices in $D$ . The minimum number of vertices in an $f$ -dominating set is defined to be the $f$ -domination number, denoted by $γ_{f} (G)$ . In a similar way one can define the connected and total $f$ -domination numbers $γ_{c, f} (G)$ and $γ_{t, f} (G)$ . If $f (x) = 1$ for all vertices $x$ , then these are the ordinary domination number, connected domination number and total...

Total domination versus paired domination

Oliver Schaudt (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has...

Independent transversal domination in graphs

Ismail Sahul Hamid (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by $γ_{i t} (G)$ . In this paper we begin an investigation of this parameter.

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

Similarity:

The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$ , then $N (v)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$ . A mapping $f : V (G) \to {- 1, 1}$ , where $V (G)$ is the vertex set of $G$ , is called a signed total dominating function (STDF) on $G$ , if $\sum_{x \in N (v)} f (x) \geq 1$ for each $v \in V (G)$ . The minimum of values $\sum_{x \in V (G)} f (x)$ , taken over all STDF’s of $G$ , is called the signed total domination number of $G$ and denoted by $γ_{s t} (G)$ . A theorem stating lower bounds for $γ_{s t} (G)$ is...

A note on perfect matchings in uniform hypergraphs with large minimum collective degree

Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi (2008)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

For an integer $k \geq 2$ and a $k$ -uniform hypergraph $H$ , let $δ_{k - 1} (H)$ be the largest integer $d$ such that every $(k - 1)$ -element set of vertices of $H$ belongs to at least $d$ edges of $H$ . Further, let $t (k, n)$ be the smallest integer $t$ such that every $k$ -uniform hypergraph on $n$ vertices and with $δ_{k - 1} (H) \geq t$ contains a perfect matching. The parameter $t (k, n)$ has been completely determined for all $k$ and large $n$ divisible by $k$ by Rödl, Ruci’nski, and Szemerédi in [, submitted]. The values of $t (k, n)$ are very close to $n / 2 - k$ . In fact, the function $t (k, n) = n / 2 - k + c_{n, k}$ ,...