Plane Elementary Bipartite Graphs with Forcing or Anti-forcing Edges | Graphs and Combinatorics Skip to main content
Springer Nature Link
Log in

Plane Elementary Bipartite Graphs with Forcing or Anti-forcing Edges

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Let G be a plane elementary bipartite graph with more than one finite face. We first characterize forcing edges and anti-forcing edges of G in terms of handles and forcing faces. We then introduce the concept of a nice pair of faces of G, which allows us to provide efficient algorithms to construct plane minimal elementary bipartite graphs from G. We show that if \(G'\) is a minimal elementary spanning subgraph of G, then all vertices of a forcing face of G are contained in a forcing face of \(G'\), and any forcing face of G is a forcing face of \(G'\) if it is still a face of \(G'\). Furthermore, any forcing edge (resp., anti-forcing edge) of G is still a forcing edge (resp., an anti-forcing edge) of \(G'\) if it is still an edge of \(G'\). We conclude the paper with the co-existence property of forcing edges and anti-forcing edges for those plane minimal elementary bipartite graphs that remain 2-connected when any handle of length one (if exists) is deleted.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Che, Z., Chen, Z.: Forcing hexagons in hexagonal systems. MATCH Commun. Math. Comput. Chem. 56, 649–668 (2006)

    MathSciNet  MATH  Google Scholar 

  2. Che, Z., Chen, Z.: Forcing faces in plane bipartite graphs. Discrete Math. 308, 2427–2439 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. Che, Z., Chen, Z.: Forcing on perfect matchings: a survey. MATCH Commun. Math. Comput. Chem. 66, 93–136 (2011)

    MathSciNet  MATH  Google Scholar 

  4. Che, Z., Chen, Z.: Conjugated circuits and forcing edges. MATCH Commun. Math. Comput. Chem. 69, 721–732 (2013)

    MathSciNet  MATH  Google Scholar 

  5. Che, Z., Chen, Z.: Forcing faces in plane bipartite graphs (II). Discrete Appl. Math. 161, 71–80 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  6. Che, Z., Chen, Z.: Forcing and anti-forcing edges in bipartite graphs. Discrete Appl. Math. 244, 70–77 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  7. Deng, H.: The anti-forcing number of hexagonal chains. MATCH Commun. Math. Comput. Chem. 58, 675–682 (2007)

    MathSciNet  MATH  Google Scholar 

  8. Deng, H.: The anti-forcing number of double hexagonal chains. MATCH Commun. Math. Comput. Chem. 60, 183–192 (2008)

    MathSciNet  MATH  Google Scholar 

  9. Deng, K., Zhang, H.: Anti-forcing spectra of perfect matchings of graphs. J. Comb. Optim. 33, 660–680 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  10. He, W., He, W.: Some topological properties and generation of normal benzenoids. MATCH Commun. Math. Comput. Chem. 25, 237–249 (1990)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  12. Hansen, P., Zheng, M.: Bonds fixed by fixing bonds. J. Chem. Inf. Comput. Sci. 34, 297–304 (1994)

    Article  Google Scholar 

  13. Li, X.: Hexagonal systems with forcing single edges. Discrete Appl. Math. 72, 295–301 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  14. Lovász, L., Plummer, M.D.: Matching Theory. AMS Chelsea Publishing, Providence (2009). (Corrected Reprint of the 1986 Original)

    MATH  Google Scholar 

  15. Lei, H., Yeh, Y., Zhang, H.: Anti-forcing numbers of perfect matchings of graphs. Discrete Appl. Math. 202, 95–105 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  16. Vukiěević, D., Trinajstić, N.: On the anti-forcing number of benzenoids. J. Math. Chem. 42, 575–583 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  17. Vukiěević, D., Trinajstić, N.: On the anti-Kekulé number and anti-forcing number of cata-condensed benzenoids. J. Math. Chem. 43, 719–726 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Yang, Q., Zhang, H., Lin, Y.: On the anti-forcing number of fullerene graphs. MATCH Commun. Math. Comput. Chem. 74, 673–692 (2015)

    MathSciNet  MATH  Google Scholar 

  19. Zhang, Q., Bian, H., Vumar, E.: On the anti-Kekulé and anti-forcing number of cata-condensed phenylenes. MATCH Commun. Math. Comput. Chem. 65, 799–806 (2011)

    MathSciNet  MATH  Google Scholar 

  20. Zhang, F., Li, X.: Hexagonal systems with forcing edges. Discrete Math. 140, 253–263 (1995)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Penn State University, Beaver Campus, Monaca, PA, 15061, USA

    Zhongyuan Che

  2. Department of Mathematics, Penn State University, Greater Allegheny Campus, McKeesport, PA, 15132, USA

    Zhibo Chen

Authors
  1. Zhongyuan Che
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Zhibo Chen
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Zhongyuan Che.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Che, Z., Chen, Z. Plane Elementary Bipartite Graphs with Forcing or Anti-forcing Edges. Graphs and Combinatorics 35, 959–971 (2019). https://doi.org/10.1007/s00373-019-02051-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02051-0

Keywords