×

Plane elementary bipartite graphs. (English) Zbl 0957.05085

A connected graph is elementary if the union of all perfect matchings induces a connected subgraph. It is well known that a connected bipartite graph is elementary if and only if it is \(1\)-extendable, i.e., each edge is contained in a perfect matching. In this paper the authors mainly study properties of plane elementary bipartite graphs. Firstly, they show that a plane bipartite graph \(G\) is elementary if and only if the boundary of each face is an alternating cycle with respect to some perfect matching of \(G\). Secondly, the concept of the so-called \(Z\)-transformation graph \(Z(G)\) of a hexagonal system \(G\) (whose vertices represent the perfect matchings of \(G\)) is extended to an arbitrary plane bipartite graph \(G\), and some results analogous to those for hexagonal systems are presented. Thirdly, they obtain the reducible face decomposition for plane elementary bipartite graphs, where a peripheral face \(f\) is called reducible if the removal of the internal vertices and edges of the path that is the intersection of \(f\) and the exterior face results in a plane elementary bipartite graph. Using the well-known bipartite ear decomposition, it follows that a plane bipartite graph different from \(K_2\) is elementary if and only if it has a reducible face decomposition. Furthermore, sharp upper and lower bounds for the number of reducible faces are derived.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, Macmillan, London, 1976.; J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, Macmillan, London, 1976. · Zbl 1226.05083
[2] Clar, E., The Aromatic Sextet (1972), Wiley: Wiley London
[3] S.J. Cyvin, I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons, Lectures Notes in Chemistry, Vol. 46, Springer, Berlin, 1988.; S.J. Cyvin, I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons, Lectures Notes in Chemistry, Vol. 46, Springer, Berlin, 1988.
[4] Dias, J. R., Study of the origin of subspectrality in molecular graphs, Theory Chim. Acta, 76, 153-171 (1989)
[5] Guo, X.; Zhang, F., \(k\)-cycle resonant graphs, Discrete Math., 135, 113-120 (1994) · Zbl 0810.05047
[6] Gutman, I.; Cyvin, S. J., Introduction to the Theory of Benzenoid Hydrocarbons (1989), Springer: Springer Berlin · Zbl 0722.05056
[7] Gutman, I.; Cyvin, S. J., Advances in the Theory of Benzenoid Hydrocarbons (1990), Springer: Springer Berlin
[8] Hansen, P.; Zheng, M., Bonds fixed by fixing bonds, J. Chem. Inform. Comput. Sci., 34, 297-304 (1994)
[9] Harary, F.; Klein, D. J.; Zivković, T. P., Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem., 6, 295-306 (1991)
[10] He, W. C.; He, W. J., Some topological properties of normal benzenoids and coronoids, Match, 25, 225-236 (1990) · Zbl 0764.92019
[11] Hetyei, G., Rectangular configurations which can be covered by 2× 1 rectangles, Pécsi Tan. Főisk. Közl, 8, 351-367 (1964)
[12] John, P., Eine erste graphentheoretische Bemerkung zur Resonanztheorie benzenoider Kohlenwasserstoffe, Z. Phys. Chem.-Leipzig, 270, 1023-1030 (1989)
[13] John, P., Eine zweite graphentheoretische Bemerkung zur Resonanztheorie benzenoider Kohlenwasserstoffe, Match (Comm. Math. Chem.), 26, 155-170 (1991) · Zbl 0764.92022
[14] John, P. E., Eine dritte graphentheoretische Bemerkung zur Resonanztheorie benzenoider Kohlenwasserstoffe, Match (Comm. Math. Chem.), 28, 165-180 (1991)
[15] Kasteleyn, P. W., The statistics of dimers on a lattice. I., The number of dimer arrangements on a quadratic lattice, Physica, 27, 1209-1225 (1961) · Zbl 1244.82014
[16] König, D., Line systems and determinant, Math. Termész. Ért., 33, 221-229 (1915) · JFM 45.0266.04
[17] Lovász, L.; Plummer, M. D., On minimal elementary bipartite graphs, J. Combin. Theory Ser. B, 23, 127-138 (1977) · Zbl 0375.05036
[18] Lovász, L.; Plummer, M. D., Matching Theory, Annals of Discrete Mathematics, Vol. 29 (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[19] Plummer, M. D., On \(n\)-extendable graphs, Discrete Math., 31, 201-210 (1980) · Zbl 0442.05060
[20] Plummer, M. D., A theorem on matchings in the plane, Graph Theory in Memory of G.A. Dirac, Ann. Discrete Math., 41, 347-354 (1989)
[21] Plummer, M. D., Extending matchings in graphs: a survey, Discrete Math., 127, 277-292 (1994) · Zbl 0798.05040
[22] Randić, M., On the role of Kekulé valence of structure, Pure Appl. Chem., 55, 2, 347-354 (1988)
[23] Sachs, H., Perfect matchings in hexagonal systems, Combinatorica, 4, 1, 89-99 (1980) · Zbl 0542.05048
[24] Trinajstić, N., Chemical Graph Theory (1983), CRC Press: CRC Press Boca Raton, FL
[25] Tutte, W. T., Graph Theory (1984), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Menlo Park, London · Zbl 0554.05001
[26] Zhang, F.; Chen, R., When each hexagon of a hexagonal system covers it, Discrete Appl. Math., 30, 63-75 (1991) · Zbl 0763.05087
[27] Zhang, F.; Guo, X.; Chen, R., Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math., 72, 405-415 (1988) · Zbl 0684.05037
[28] Zhang, F.; Guo, X.; Chen, R., The connectivity of Z-transformation graphs of perfect matchings of hexagonal systems, Acta Math. Appl. Sinica, 4, 2, 131-135 (1988) · Zbl 0733.05057
[29] Zhang, F.; Li, X., Hexagonal systems with forcing edges, Discrete Math., 140, 253-263 (1995) · Zbl 0832.05090
[30] F. Zhang, Y. Liu, Estimation of the resonance energy of benzenoid hydrocarbons, Chinese Sci. Bull. 38 (1993) 1391-1394 (in Chinese).; F. Zhang, Y. Liu, Estimation of the resonance energy of benzenoid hydrocarbons, Chinese Sci. Bull. 38 (1993) 1391-1394 (in Chinese).
[31] Zhang, F.; Zheng, M., Generalized hexagonal systems with each hexagon being resonant, Discrete Appl. Math., 36, 67-73 (1992) · Zbl 0774.05077
[32] Zhang, H., The connectivity of Z-transformation graphs of perfect matchings of polyominoes, Discrete Math., 158, 257-272 (1996) · Zbl 0869.05022
[33] Zhang, H.; Zhang, F., The rotation graphs of perfect matchings of plane bipartite graphs, Discrete Appl. Math., 73, 5-12 (1997) · Zbl 0877.05042
[34] Zhang, H.; Zhang, F., Perfect matchings of polyomino graphs, Graphs Combin., 13, 295-304 (1997) · Zbl 0895.05051
[35] Zhang, H.; Zhang, F., Block graph of Z-transformation graph of perfect matchings of plane elementary bipartite graphs, Ars Combin., 53, 309-314 (1999) · Zbl 0994.05115
[36] Zheng, M., The \(k\)-resonant benzenoid systems, J. Mol. Struct. (Theochem), 231, 321-334 (1991)
[37] Zheng, M., Construction of 3-resonant benzenoid systems, J. Mol. Struct. (Theochem), 277, 1-14 (1992)
[38] M. Zheng, Perfect matchings in hexagonal systems, Doctoral Thesis, Rutgers University, 1992.; M. Zheng, Perfect matchings in hexagonal systems, Doctoral Thesis, Rutgers University, 1992.
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.