Signed total domination number of a graph

Bohdan Zelinka

Czechoslovak Mathematical Journal (2001)

  • Volume: 51, Issue: 2, page 225-229
  • ISSN: 0011-4642

Abstract

top
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 ) { - 1 , 1 } , where V ( G ) is the vertex set of G , is called a signed total dominating function (STDF) on G , if x N ( v ) f ( x ) 1 for each v V ( G ) . The minimum of values x 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 stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on n -side prisms. At the end it is proved that γ s t ( G ) is not bounded from below in general.

How to cite

top

Zelinka, Bohdan. "Signed total domination number of a graph." Czechoslovak Mathematical Journal 51.2 (2001): 225-229. <http://eudml.org/doc/30630>.

@article{Zelinka2001,
abstract = {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) \rightarrow \lbrace -1, 1\rbrace $, 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) \ge 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 $\gamma _\{\mathrm \{s\}t\}(G)$. A theorem stating lower bounds for $\gamma _\{\mathrm \{s\}t\}(G)$ is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on $n$-side prisms. At the end it is proved that $\gamma _\{\mathrm \{s\}t\}(G)$ is not bounded from below in general.},
author = {Zelinka, Bohdan},
journal = {Czechoslovak Mathematical Journal},
keywords = {signed total dominating function; signed total domination number; regular graph; circuit; complete graph; complete bipartite graph; Cartesian product of graphs; signed total dominating function; signed total domination number; regular graph; circuit; complete graph; complete bipartite graph; Cartesian product of graphs},
language = {eng},
number = {2},
pages = {225-229},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Signed total domination number of a graph},
url = {http://eudml.org/doc/30630},
volume = {51},
year = {2001},
}

TY - JOUR
AU - Zelinka, Bohdan
TI - Signed total domination number of a graph
JO - Czechoslovak Mathematical Journal
PY - 2001
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 51
IS - 2
SP - 225
EP - 229
AB - 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) \rightarrow \lbrace -1, 1\rbrace $, 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) \ge 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 $\gamma _{\mathrm {s}t}(G)$. A theorem stating lower bounds for $\gamma _{\mathrm {s}t}(G)$ is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on $n$-side prisms. At the end it is proved that $\gamma _{\mathrm {s}t}(G)$ is not bounded from below in general.
LA - eng
KW - signed total dominating function; signed total domination number; regular graph; circuit; complete graph; complete bipartite graph; Cartesian product of graphs; signed total dominating function; signed total domination number; regular graph; circuit; complete graph; complete bipartite graph; Cartesian product of graphs
UR - http://eudml.org/doc/30630
ER -

References

top
  1. Signed domination in graphs, Graph Theory, Combinatorics and Application, Proceedings 7th Internat. Conf. Combinatorics, Graph Theory, Applications, vol. 1, Y. Alavi, A. J. Schwenk (eds.), John Willey & Sons, Inc., 1995, pp. 311–322. (1995) MR1405819
  2. Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York-Basel-Hong Kong, 1998. (1998) MR1605684

Citations in EuDML Documents

top
  1. Lutz Volkmann, Upper Bounds on the Signed Total (K, K)-Domatic Number of Graphs
  2. Laura M. Harris, Johannes H. Hattingh, Michael A. Henning, Algorithmic aspects of total-subdomination in graphs
  3. Hua Ming Xing, Liang Sun, Xue-Gang Chen, On signed majority total domination in graphs
  4. Hua Ming Xing, Hai-Long Liu, Minus total domination in graphs
  5. Hongyu Liang, Some Sharp Bounds on the Negative Decision Number of Graphs
  6. Miroslav Fiedler, Professor Bohdan Zelinka (May 16, 1940--February 5, 2005)

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.