DMGT

Discussiones Mathematicae Graph Theory 31(1) (2011) 197-202
DOI: https://doi.org/10.7151/dmgt.1538

A CHARACTERIZATION OF LOCATING-TOTAL DOMINATION EDGE CRITICAL GRAPHS

Mostafa Blidia

LAMDA-RO, Department of Mathematics
University of Blida, B.P. 270, Blida, Algeria
e-mail: m_blidia@yahoo.fr.

Widad Dali

Department R-O
University of Algiers, Algeria
e-mail: widdal@yahoo.fr.

Abstract

For a graph G = (V,E) without isolated vertices, a subset D of vertices of V is a total dominating set (TDS) of G if every vertex in V is adjacent to a vertex in D. The total domination number γ_t(G) is the minimum cardinality of a TDS of G. A subset D of V which is a total dominating set, is a locating-total dominating set, or just a LTDS of G, if for any two distinct vertices u and v of V(G)∖D, N_G(u)∩D ≠ N_G(v)∩D. The locating-total domination number γ_L^t(G) is the minimum cardinality of a locating-total dominating set of G. A graph G is said to be a locating-total domination edge removal critical graph, or just a γ_L^t+-ER-critical graph, if γ_L^t(G−e) > γ_L^t(G) for all e non-pendant edge of E. The purpose of this paper is to characterize the class of γ_L^t+-ER-critical graphs.

Keywords: locating-domination, critical graph.

2010 Mathematics Subject Classification: 05C69, 05C15.

References

[1]	M. Blidia and W. Dali, A characterization of a locating-domination edge critical graphs, Australasian J. Combin. 44 (2009) 297-300.
[2]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[3]	D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory (B) 34 (1983) 65-76, doi: 10.1016/0095-8956(83)90007-2.
[4]	T.W. Haynes, M.A. Henning and J. Howard, Locating and total dominating sets in trees, Discrete Appl. Math. 154 (2006) 1293-1300, doi: 10.1016/j.dam.2006.01.002.

Received 8 December 2008
Revised 20 December 2009
Accepted 21 January 2010