Abstract
A vertex subset S of a graph G = (V,E) is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ t (G−v) < γ t (G). A total domination vertex critical graph G is called k-γ t -critical if γ t (G) = k. In this paper we first show that every 3-γ t -critical graph G of even order has a perfect matching if it is K 1,5-free. Secondly, we show that every 3-γ t -critical graph G of odd order is factor-critical if it is K 1,5-free. Finally, we show that G has a perfect matching if G is a K 1,4-free 4-γ t (G)-critical graph of even order and G is factor-critical if G is a K 1,4-free 4-γ t (G)-critical graph of odd order.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R. (eds): Graph Theory with Applications. Elsevier, North Holland (1976)
Cockayne E.J., Dawes R., Hedetniemi S.: Total domination in graphs. Networks 10, 211–219 (1980)
EI-Zahar M., Gravier S., Klobucar A.: On the total domination number of cross products of graphs. Discrete Math. 308, 2025–2029 (2008)
Favaron O., Henning M.A., Mynhardt C.M., Puech J.: Total domination in graphs with minimum degree three. J. Graph Theory 34, 9–19 (2000)
Henning M.A., Kang L.Y., Shan E.F., Yeo A.: On matching and total domination in graphs. Discrete Math. 308, 2313–2318 (2008)
Kratsch D.: Domination and total domination on asteroidal triple-free graphs. Discrete Appl. Math. 99, 111–123 (2000)
Shan E.F., Kang L.Y., Henning M.A.: Erratum to: a linear Vizing-like relation relating the size and total domination number of a graph. J. Graph Theory 54, 350–353 (2007)
Ananchuen N., Ananchuen W., Plummer M.D.: Matching properties in connected domination critical graphs. Discrete Math. 308, 1260–1267 (2008)
Ananchuen N., Plummer M.D.: Matching properties in domination critical graphs. Discrete Math. 277, 1–13 (2004)
Ananchuen N., Plummer M.D.: Matchings in 3-vertex-critical graphs: the even case. Networks 45, 210–213 (2005)
Ananchuen N., Plummer M.D.: Matchings in 3-vertex-critical graphs: The odd case. Discrete Math. 307, 1651–1658 (2007)
Ananchuen N., Plummer M.D.: 3-Factor-criticality in domination critical graphs. Discrete Math. 307, 3006–3015 (2007)
Wang T., Yu Q.L.: Factor-critical property in 3-dominating-critical graphs. Discrete Math. 309, 1079–1083 (2009)
Goddard W., Haynes T.W., Henning M.A., van der Merwe L.C.: The diameter of total domination vertex critical graphs. Discrete Math. 286, 255–261 (2004)
Chen X.G., Sohn M.Y.: A note on the total domination vertex critical graphs. Ars Combin. 88, 289–294 (2008)
Mojdeh D.A., Rad N.J.: On an open problem concerning total domination critical graphs. Expo. Math. 25, 175–179 (2007)
Wang C.X., Hu Z.Q., Li X.W.: A constructive characterization of total domination vertex critical graphs. Discrete Math. 309, 991–996 (2009)
Lovász, L., Plummer, M.D. (eds): Matching Theory. North-Holland Inc., Amsterdam (1986)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by the National Nature Science Foundation of China (No. 60773078), the PuJiang Project of Shanghai (No. 09PJ1405000) and Key Disciplines of Shanghai Municipality (S30104).
Rights and permissions
About this article
Cite this article
Wang, H., Kang, L. & Shan, E. Matching Properties in Total Domination Vertex Critical Graphs. Graphs and Combinatorics 25, 851–861 (2009). https://doi.org/10.1007/s00373-010-0889-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-010-0889-x