DMGT

Discussiones Mathematicae Graph Theory 32(2) (2012) 289-297
DOI: https://doi.org/10.7151/dmgt.1607

1-factors and Characterization of Reducible Faces of Plane Elementary Bipartite Graphs

Andrej Taranenko and Aleksander Vesel

Faculty of Natural Sciences and Mathematics
University of Maribor
Koroška cesta 160, 2000 Maribor, Slovenia

Abstract

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given.

A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of f and the outer cycle of G results in an elementary graph. We characterize the reducible faces of a plane elementary bipartite graph. This result generalizes the characterization of reducible faces of an elementary benzenoid graph.

Keywords: plane elementary bipartite graph, reducible face, perfect matching, 1-factor, benzenoid graph

2010 Mathematics Subject Classification: 05C70.

References

[1]	S.J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons (Springer Verlag, Heidelberg, 1988).
[2]	A.A. Dobrynin, I. Gutman, S. Klavžar and P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002) 247--294, doi: 10.1023/A:1016290123303.
[3]	I. Gutman and S.J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons (Springer Verlag, Berlin, 1989).
[4]	P. Hansen and M. Zheng, A linear algorithm for perfect matching in hexagonal systems, Discrete Math. 122 (2002) 179--196, doi: 10.1016/0012-365X(93)90294-4.
[5]	S. Klavžar and M. Kovše, The Lattice dimension of benzenoid systems, MATCH Commun. Math. Comput. Chem. 56 (2006) 637--648.
[6]	S. Klavžar, A. Vesel, P. Žigert and I. Gutman, Binary coding of Kekulé structures of catacondensed benzenoid hydrocarbons, Comput. & Chem. 25 (2001) 569--575, doi: 10.1016/S0097-8485(01)00068-7.
[7]	S. Klavžar, A. Vesel and P. Žigert, On resonance graphs of catacondensed hexagonal graphs: structure, coding, and hamilton path algorithm, MATCH Commun. Math. Comput. Chem. 49 (2003) 100--116.
[8]	P.C.B. Lam and H. Zhang, A distributive lattice on the set of perfect matchings of a plane biparite graph, Order 20 (2003) 13--29, doi: 10.1023/A:1024483217354.
[9]	L. Lovász and M.D. Plummer, Matching Theory (North-Holland, 1986).
[10]	I. Pesek and A. Vesel, Visualization of the resonance graphs of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 58 (2007) 215--232.
[11]	K. Salem and S. Klavžar, On plane bipartite graphs without fixed edges, Appl. Math. Lett. 20 (2007) 813--816, doi: 10.1016/j.aml.2006.08.014.
[12]	A. Taranenko and A. Vesel, Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs, Discrete Appl. Math. 156 (2008) 1711--1724, doi: 10.1016/j.dam.2007.08.029.
[13]	A. Taranenko and A. Vesel, On Elementary Benzenoid Graphs: New Characterization and Structure of Their Resonance Graphs, MATCH Commun. Math. Comput. Chem. 60 (2008) 193--216.
[14]	F. Zhang, X. Guo and R. Chen, Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405--415, doi: 10.1016/0012-365X(88)90233-6.
[15]	H. Zhang, P.C.B. Lam and W.C. Shiu, Resonance graphs and a binary coding for the 1-factors of benzenoid systems, SIAM J. Discret. Math. 22 (2008) 971--984, doi: 10.1137/070699287.
[16]	H. Zhang and F. Zhang, The rotation graphs of perfect matchings of plane bipartite graphs, Discrete Appl. Math. 73 (1997) 5--12, doi: 10.1016/S0166-218X(96)00024-8.
[17]	H. Zhang and F. Zhang, Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291--311, doi: 10.1016/S0166-218X(00)00204-3.

Received 30 November 2010
Revised 11 May 2011
Accepted 24 May 2011