The rotation graphs of perfect matchings of plane bipartite graphs. (English) Zbl 0877.05042
Authors’ abstract: The minimal proper alternating cycle (MPAC) rotation graph \(R(G)\) of perfect matchings of a plane bipartite graph \(G\) is defined. We show that an MPAC rotation graph \(R(G)\) of \(G\) is a directed rooted tree, and thus extend such a result for generalized polyhex graphs to arbitrary plane bipartite graphs. As an immediate result, we describe a one-to-one correspondence between MPAC systems and perfect matchings in \(G\).
Reviewer: B.Mohar (Ljubljana)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Keywords:
Kekulé patterns; alternating cycle; rotation graph; perfect matchings; plane bipartite graph; directed rooted tree; polyhex graphsReferences:
| [1] | Chen, Z., Directed tree structure of the set of Kekulé patterns of polyhex graphs, Chem. Phys. Lett., 115, 291-293 (1985) |
| [2] | Guo, X.; Zhang, F., Mathematical properties and structures of sets of sextet patterns of generalized polyhexes, J. Math. Chem., 9, 279-290 (1992) |
| [3] | Guo, X.; Zhang, F., An efficient algorithm for generating all Kekulé patterns of a generalized benzenoid systems, J. Math. Chem., 12, 163-171 (1993) |
| [4] | Gutman, I., The \(R\)-polynomial: a new combinatorial technique in resonance theory, Bull. Soc. Chim. Beograd, 46, 3, 17-22 (1981) |
| [5] | He, W.; He, W., Topological properties of KHF-graphs and a proof of a one-to-one correspondence between Kekulé and sextet patterns of KHF-graphs, Theoret. Chim. Acta, 70, 447-453 (1986) |
| [6] | Hosoya, H., On some counting polynomials in chemistry, Discrete Appl. Math., 19, 239-257 (1988) · Zbl 0633.05006 |
| [7] | Hosoya, H., Clar’s aromatic sextets and sextet polynomial, (Advances in the Theory of Benzenoid Hydrocarbons. Advances in the Theory of Benzenoid Hydrocarbons, Topics in Current Chemistry, 153 (1989)), 255-272 |
| [8] | Jiang, W., Several topological properties of hexagonal systems, J. Neimengu Univ., 18, 412 (1987) · Zbl 1332.92090 |
| [9] | Ohkami, N.; Hosoya, H., Theoret. Chim. Acta, 64, 153-170 (1985) |
| [10] | Ohkami, N.; Motoyama, A.; Yamaguchi, T.; Hosoya, H.; Gutman, I., Graph-theoretical analysis of the Clar’s aromatic sextet, Tetrahedron, 37, 1113-1122 (1981) |
| [11] | Zhang, F.; Guo, X., Directed tree structure of the set of Kekulé patterns of generalized polyhex graphs, Discrete Appl. Math., 32, 295-302 (1991) · Zbl 0742.05068 |
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.
