Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Complete forcing numbers of primitive coronoids

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

Abstract

Let \(G\) be a graph with edge set \(E(G)\) that admits a perfect matching \(M\). A forcing set of \(M\) is a subset of \(M\) contained in no other perfect matching of \(G\). A complete forcing set of \(G\), recently introduced by Xu et al. (J Combin Optim 29(4):803–814, 2015c), is a subset of \(E(G)\) to which the restriction of any perfect matching is a forcing set of the perfect matching. The minimum possible cardinality of a complete forcing set of \(G\) is the complete forcing number of \(G\). Previously, Xu et al. (J Combin Optim 29(4):803–814, 2015c) gave an expression for the complete forcing number of a hexagonal chain and a recurrence relation for complete forcing numbers of catacondensed hexagonal systems. In this article, by the constructive proof, we give an explicit analytical expression for the complete forcing number of a primitive coronoid, a circular single chain consisting of congruent regular hexagons (i.e., Theorem 3.9).

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  • Adams P, Mahdian M, Mahmoodian ES (2004) On the forced matching numbers of bipartite graphs. Discret Math. 281:1–12

    Article  MathSciNet  MATH  Google Scholar 

  • Afshani P, Hatami H, Mahmoodian ES (2004) On the spectrum of the forced matching number of graphs. Aust J Combin 30:147–160

    MathSciNet  MATH  Google Scholar 

  • Chan WH, Xu S-J, Nong G (2015) A linear-time algorithm for computing the complete forcing number and the Clar number of catacondensed hexagonal systems. MATCH Commun Math Comput Chem 74(1):201–216

    MathSciNet  Google Scholar 

  • Cyvin SJ, Cyvin BN, Brunvoll J, Hosoya H, Zhang F, Klein DJ, Chen R, Polansky OE (1991) Kekulé structure counts: general gormulations for primitive coronoid hydrocarbons. Monatsh Chem 122:435–444

    Article  Google Scholar 

  • Cyvin SJ, Gutman I (1988) Kekulé structures in benzenoid hydrocarbons, vol 46., Lecture notes in chemistrySpringer, Berlin

    MATH  Google Scholar 

  • Diestel R (2000) Graph theory, 2nd edn. Springer, New York

    MATH  Google Scholar 

  • Gray K (1990) On the minimum number of blocks defining a design. Bull Aust Math Soc 41:97–112

    Article  MathSciNet  MATH  Google Scholar 

  • Harary F, Klein DJ, Živković TP (1991) Graphical properties of polyhexes: perfect matching vector and forcing. J Math Chem 6:295–306

    Article  MathSciNet  Google Scholar 

  • Klein DJ, Randić M (1987) Innate degree of freedom of a graph. J Comput Chem 8:516–521

    Article  MathSciNet  Google Scholar 

  • Kleinerman S (2006) Bounds on the forcing numbers of bipartite graphs. Discret Math 306:66–73

    Article  MathSciNet  MATH  Google Scholar 

  • Lam F, Pachter L (2003) Forcing numbers of stop signs. Theor Comput Sci 303:409–416

    Article  MathSciNet  MATH  Google Scholar 

  • Lovász L, Plummer M (1986) Matching theory, annals of discrete math, vol 29. North-Holland, Amsterdam

    MATH  Google Scholar 

  • Mahmoodian ES, Naserasr R, Zaker M (1997) Defining sets in vertex colorings of graphs and Latin rectangles. Discret Math 167(168):451–460

    Article  MathSciNet  MATH  Google Scholar 

  • Pachter L, Kim P (1998) Forcing matchings on square grids. Discret Math 190:287–294

    Article  MathSciNet  MATH  Google Scholar 

  • Randić M, Klein DJ (1985) Kekulé valence structures revisited. Innate degrees of freedom of \(\pi \)-electron couplings. In: Trinajstić N (ed) Mathematical and computational concepts in chemistry. Wiley, New York, pp 274–282

    Google Scholar 

  • Riddle ME (2002) The minimum forcing number for the torus and hypercube. Discret Math 245:283–292

    Article  MathSciNet  MATH  Google Scholar 

  • Vukičević D, Došlić T (2007) Global forcing number of grid graphs. Aust J Combin 38:47–62

    MathSciNet  MATH  Google Scholar 

  • Vukičević D, Sedlar J (2004) Total forcing number of the triangular grid. Math Commun 9:169–179

    MathSciNet  MATH  Google Scholar 

  • Xu S-J, Chang H, Xiao J-M (2015a) Complete forcing numbers of rectangular polyominoes, completed

  • Xu S-J, Xiao J-M, Chang H (2015b) Complete forcing numbers of triangular benzenoid systems, completed

  • Xu S-J, Zhang H, Cai J (2015c) Complete forcing numbers of catacondensed benzenoid. J Combin Optim 29(4):803–814

  • Zhang H, Ye D, Shiu WC (2010) Forcing matching numbers of fullerene graphs. Discret Appl Math 158:573–582

    Article  MathSciNet  MATH  Google Scholar 

  • Zhang H, Zhang F (2000) Plane elementary bipartite graphs. Discret Appl Math 105:291–311

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to sincerely thank the anonymous referees for the time they spent in checking the manuscript, as well as their many valuable suggestions. Additionally, this work is supported by National Natural Science Foundation of China (Grants Nos. 11001113, 11371180). The work of Wai Hong Chan is partially supported by the Research Grant Council, Hong Kong SAR (Grant No. GRF (810012)). Part of this work was completed while S.-J. Xu was visiting Department of Mathematics and Information Technology at Hong Kong Institute of Education, Tai Po, Hong Kong.

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Gansu Key Laboratory of Applied Mathematics and Complex Systems, Lanzhou University, Lanzhou, 730000, Gansu, People’s Republic of China

    Shou-Jun Xu, Xiu-Song Liu & Heping Zhang

  2. Department of Mathematics and Information Technology, The Hong Kong Institute of Education, Tai Po, Hong Kong, People’s Republic of China

    Wai Hong Chan

Authors
  1. Shou-Jun Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiu-Song Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wai Hong Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Heping Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Heping Zhang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, SJ., Liu, XS., Chan, W.H. et al. Complete forcing numbers of primitive coronoids. J Comb Optim 32, 318–330 (2016). https://doi.org/10.1007/s10878-015-9881-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-015-9881-y

Keywords

Search

Navigation