[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Perfect matchings in paired domination vertex critical graphs

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γ pr (G), is the minimum cardinality of a paired dominating set of G. A graph with no isolated vertex is called paired domination vertex critical, or briefly γ pr -critical, if for any vertex v of G that is not adjacent to any vertex of degree one, γ pr (G−v)<γ pr (G). A γ pr -critical graph G is said to be k-γ pr -critical if γ pr (G)=k. In this paper, we firstly show that every 4-γ pr -critical graph of even order has a perfect matching if it is K 1,5-free and every 4-γ pr -critical graph of odd order is factor-critical if it is K 1,5-free. Secondly, we show that every 6-γ pr -critical graph of even order has a perfect matching if it is K 1,4-free.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Berge C (1958) Acad C R Sci Paris Ser I Math 247:258–259. Graphs and hypergraphs. North-Holland, Amsterdam (1973) (Chapter 8, Theorem 12)

    MathSciNet  MATH  Google Scholar 

  • Bondy JA, Murty USR (1976) Graph theory with application. Elsevier/North Holland, Amsterdam

    Google Scholar 

  • Brigham RC, Chinn PZ, Dutton RD (1988) Vertex domination-critical graphs. Networks 18:173–179

    Article  MathSciNet  MATH  Google Scholar 

  • Brigham RC, Haynes TW, Henning MA, Rall DF (2005) Bicritical domination. Discrete Math 305:18–32

    Article  MathSciNet  MATH  Google Scholar 

  • Edwards M (2006) Criticality concepts for paired domination in graphs. Masters Thesis, University of Victoria

  • Fulman J, Hanson D, MacGillivray G (1995) Vertex domination-critical graphs. Networks 25:41–43

    Article  MathSciNet  MATH  Google Scholar 

  • Goddard W, Haynes TW, Henning MA, van der Merwe LC (2004) The diameter of total domination vertex critical graphs. Discrete Math 286:255–261

    Article  MathSciNet  MATH  Google Scholar 

  • Haynes TW, Slater PJ (1998) Paired-domination in graphs. Networks 32:199–206

    Article  MathSciNet  MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, New York

    MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998b) Domination in graphs: advanced topics. Marcel Dekker, New York

    MATH  Google Scholar 

  • Henning MA, Mynhardt CM (2008) The diameter of paired-domination vertex critical graphs. Czechoslov Math J 58(133):887–897

    Article  MathSciNet  MATH  Google Scholar 

  • Hou XM, Edward M (2008) Paired domination vertex critical graphs. Graphs Comb 24:453–459

    Article  MATH  Google Scholar 

  • Sumner DP, Blitch P (1983) Domination critical graphs. J Comb Theory, Ser B 34:65–76

    Article  MathSciNet  MATH  Google Scholar 

  • Wang HC, Kang LY, Shan EF (2009) Matching properties in total domination vertex critical graphs. Graphs Comb 25:851–861

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Shanghai University, Shanghai, 200444, China

    Shenwei Huang, Erfang Shan & Liying Kang

Authors
  1. Shenwei Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erfang Shan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liying Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Erfang Shan.

Additional information

This research was partially supported by the National Nature Science Foundation of China (No. 60773078), PuJiang Project of Shanghai (No. 09PJ1405000) and Shanghai Leading Academic Discipline Project (No. S30104).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huang, S., Shan, E. & Kang, L. Perfect matchings in paired domination vertex critical graphs. J Comb Optim 23, 507–518 (2012). https://doi.org/10.1007/s10878-010-9368-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-010-9368-9

Keywords