Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0959.05089
Henning, Michael A.
Graphs with large total domination number. (English)
[J] J. Graph Theory 35, No.1, 21-45 (2000). ISSN 0364-9024; ISSN 1097-0118/e

A subset $S$ of the vertex set $V(G)$ of a graph $G$ is called total dominating in $G$, if each vertex of $G$ is adjacent to a vertex of $S$. The minimum number of vertices of a total dominating set in $G$ is the total domination number $\gamma_t(G)$ of $G$. A graph $G$ is called $(4/7)$-minimal, if it is connected, the minimum degree $\delta(G)\ge 2$ and $\gamma_t(G)\ge 4n/7$, where $n$ is the number of vertices of $G$, and is minimal with respect to these properties. The main result is a characterization of $(4/7)$-minimal graphs. A graph $G$ is $(4/7)$-minimal if and only if either it is a circuit of length 3, 5, 6, 7, 10 or 13, or can be obtained from a tree in a certain way (described in the paper), or is isomorphic to a certain graph (depicted in the paper).
[Bohdan Zelinka (Liberec)]

MSC 2000:: *05C69 Dominating sets, independent sets, cliques

Keywords: total dominating set; total domination number; $(4/7)$-minimal graphs

Cited in: Zbl 1224.05369 Zbl 1158.05044

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]