Plane elementary bipartite graphs with forcing or anti-forcing edges. (English) Zbl 1416.05075
Summary: 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^\prime\) 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^\prime\), and any forcing face of \(G\) is a forcing face of \(G^\prime\) if it is still a face of \(G^\prime\). Furthermore, any forcing edge (resp., anti-forcing edge) of \(G\) is still a forcing edge (resp., an anti-forcing edge) of \(G^\prime\) if it is still an edge of \(G^\prime\). 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.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Che, Z., Chen, Z.: Forcing hexagons in hexagonal systems. MATCH Commun. Math. Comput. Chem. 56, 649-668 (2006) · Zbl 1119.05322 |
| [2] | Che, Z., Chen, Z.: Forcing faces in plane bipartite graphs. Discrete Math. 308, 2427-2439 (2008) · Zbl 1168.05357 · doi:10.1016/j.disc.2007.05.025 |
| [3] | Che, Z., Chen, Z.: Forcing on perfect matchings: a survey. MATCH Commun. Math. Comput. Chem. 66, 93-136 (2011) · Zbl 1265.05001 |
| [4] | Che, Z., Chen, Z.: Conjugated circuits and forcing edges. MATCH Commun. Math. Comput. Chem. 69, 721-732 (2013) · Zbl 1299.05262 |
| [5] | Che, Z., Chen, Z.: Forcing faces in plane bipartite graphs (II). Discrete Appl. Math. 161, 71-80 (2013) · Zbl 1254.05152 · doi:10.1016/j.dam.2012.08.016 |
| [6] | Che, Z., Chen, Z.: Forcing and anti-forcing edges in bipartite graphs. Discrete Appl. Math. 244, 70-77 (2018) · Zbl 1387.05127 · doi:10.1016/j.dam.2018.03.027 |
| [7] | Deng, H.: The anti-forcing number of hexagonal chains. MATCH Commun. Math. Comput. Chem. 58, 675-682 (2007) · Zbl 1142.05354 |
| [8] | Deng, H.: The anti-forcing number of double hexagonal chains. MATCH Commun. Math. Comput. Chem. 60, 183-192 (2008) · Zbl 1199.05282 |
| [9] | Deng, K., Zhang, H.: Anti-forcing spectra of perfect matchings of graphs. J. Comb. Optim. 33, 660-680 (2017) · Zbl 1390.90548 · doi:10.1007/s10878-015-9986-3 |
| [10] | He, W., He, W.: Some topological properties and generation of normal benzenoids. MATCH Commun. Math. Comput. Chem. 25, 237-249 (1990) · Zbl 0764.92020 |
| [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) · doi:10.1007/BF01192587 |
| [12] | Hansen, P., Zheng, M.: Bonds fixed by fixing bonds. J. Chem. Inf. Comput. Sci. 34, 297-304 (1994) · doi:10.1021/ci00018a011 |
| [13] | Li, X.: Hexagonal systems with forcing single edges. Discrete Appl. Math. 72, 295-301 (1997) · Zbl 0865.05069 · doi:10.1016/0166-218X(95)00116-9 |
| [14] | Lovász, L., Plummer, M.D.: Matching Theory. AMS Chelsea Publishing, Providence (2009). (Corrected Reprint of the 1986 Original) · Zbl 1175.05002 |
| [15] | Lei, H., Yeh, Y., Zhang, H.: Anti-forcing numbers of perfect matchings of graphs. Discrete Appl. Math. 202, 95-105 (2016) · Zbl 1330.05131 · doi:10.1016/j.dam.2015.08.024 |
| [16] | Vukiěević, D., Trinajstić, N.: On the anti-forcing number of benzenoids. J. Math. Chem. 42, 575-583 (2007) · Zbl 1127.92054 · doi:10.1007/s10910-006-9133-6 |
| [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) · Zbl 1196.92062 · doi:10.1007/s10910-006-9223-5 |
| [18] | Yang, Q., Zhang, H., Lin, Y.: On the anti-forcing number of fullerene graphs. MATCH Commun. Math. Comput. Chem. 74, 673-692 (2015) · Zbl 1462.05344 |
| [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) · Zbl 1262.92083 |
| [20] | Zhang, F., Li, X.: Hexagonal systems with forcing edges. Discrete Math. 140, 253-263 (1995) · Zbl 0832.05090 · doi:10.1016/0012-365X(93)E0184-6 |
| [21] | Zhang, H., Zhang, F.: Plane elementary bipartite graphs. Discrete Appl. Math. 105, 291-311 (2000) · Zbl 0957.05085 · doi:10.1016/S0166-218X(00)00204-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
