[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Vertices in all minimum paired-dominating sets of block graphs

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

Abstract

Let G=(V,E) be a simple graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a linear-time algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Chen L, Lu C, Zeng Z (2009a) Hardness results and approximation algorithms for (weighted) paired-domination in graphs. Theor Comput Sci 410:5063–5071

    Article  MathSciNet  MATH  Google Scholar 

  • Chen L, Lu C, Zeng Z (2009b) A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inf Process Lett 110:20–23

    Article  MathSciNet  MATH  Google Scholar 

  • Chen L, Lu C, Zeng Z (2010a) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19:457–470

    Article  MathSciNet  MATH  Google Scholar 

  • Chen L, Lu C, Zeng Z (2010b) Graphs with unique minimum paired-dominating sets. Ars Comb (to appear)

  • Cockayne EJ, Henning MA, Mynhardt CM (2003) Vertices contained in all or in no minimum total dominating set of a tree. Discrete Math 260:37–44

    Article  MathSciNet  MATH  Google Scholar 

  • Dorbec P, Gravier S, Henning MA (2007) Paired-domination in generalized claw-free graphs. J Comb Optim 14:1–7

    Article  MathSciNet  MATH  Google Scholar 

  • Favaron O, Henning MA (2004) Paired-domination in claw-free cubic graphs. Graphs Comb 20:447–456

    Article  MathSciNet  MATH  Google Scholar 

  • Haynes TW, Slater PJ (1995) Paired-domination and the paired-domatic number. Congr Numer 109:65–72

    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 (eds) (1998a) Fundamentals of domination in graphs. Dekker, New York

    MATH  Google Scholar 

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

    MATH  Google Scholar 

  • Henning MA (2007) Graphs with large paired-domination number. J Comb Optim 13:61–78

    Article  MathSciNet  MATH  Google Scholar 

  • Henning MA, Plummer MD (2005) Vertices contained in all or in no minimum paired-dominating set of a tree. J Comb Optim 10:283–294

    Article  MathSciNet  MATH  Google Scholar 

  • Kang L, Sohn MY, Cheng TCE (2004) Paired-domination in inflated graphs. Theor Comput Sci 320:485–494

    Article  MathSciNet  MATH  Google Scholar 

  • Mynhardt CM (1999) Vertices contained in every minimum dominating set of a tree. J Graph Theory 31:163–177

    Article  MathSciNet  MATH  Google Scholar 

  • Qiao H, Kang LY, Caedei M, Du DZ (2003) Paired-domination of trees. J Glob Optim 25:43–54

    Article  MATH  Google Scholar 

  • West DB (2001) Introduction to graph theory, 2nd edn. Prentice Hall, New York

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Information Engineering, Shanghai Maritime University, Shanghai, 201306, China

    Lei Chen

  2. Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, 200062, China

    Lei Chen & Zhenbing Zeng

  3. Department of Mathematics, East China Normal University, Shanghai, 200241, China

    Changhong Lu

Authors
  1. Lei Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Changhong Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhenbing Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Changhong Lu.

Additional information

Supported in part by National Natural Science Foundation of China (Nos. 10971248 and 61073198) and Shanghai Leading Academic Discipline Project (No. B407) and the Fundamental Research Funds for the central Universities.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, L., Lu, C. & Zeng, Z. Vertices in all minimum paired-dominating sets of block graphs. J Comb Optim 24, 176–191 (2012). https://doi.org/10.1007/s10878-011-9375-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-011-9375-5

Keywords

Search

Navigation