# 1-factors and characterization of reducible faces of plane elementary bipartite graphs

Andrej Taranenko; Aleksander Vesel

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 2, page 289-297
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAndrej Taranenko, and Aleksander Vesel. "1-factors and characterization of reducible faces of plane elementary bipartite graphs." Discussiones Mathematicae Graph Theory 32.2 (2012): 289-297. <http://eudml.org/doc/271025>.

@article{AndrejTaranenko2012,

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.
},

author = {Andrej Taranenko, Aleksander Vesel},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {plane elementary bipartite graph; reducible face; perfect matching; 1-factor; benzenoid graph},

language = {eng},

number = {2},

pages = {289-297},

title = {1-factors and characterization of reducible faces of plane elementary bipartite graphs},

url = {http://eudml.org/doc/271025},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Andrej Taranenko

AU - Aleksander Vesel

TI - 1-factors and characterization of reducible faces of plane elementary bipartite graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 2

SP - 289

EP - 297

AB -
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.

LA - eng

KW - plane elementary bipartite graph; reducible face; perfect matching; 1-factor; benzenoid graph

UR - http://eudml.org/doc/271025

ER -

## References

top- [1] S.J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons (Springer Verlag, Heidelberg, 1988). Zbl0722.05056
- [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. Zbl0993.05059
- [3] I. Gutman and S.J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons (Springer Verlag, Berlin, 1989). Zbl0722.05056
- [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. Zbl1119.05325
- [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. Zbl1081.05513
- [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. Zbl1025.05050
- [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. Zbl1142.05356
- [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. Zbl1131.05075
- [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. Zbl1152.05382
- [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. Zbl1273.92090
- [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. Zbl0684.05037
- [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. Zbl1218.05157
- [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. Zbl0877.05042
- [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. Zbl0957.05085

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.