Geodesic
1-factors and characterization of reducible faces of plane elementary bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 2, pp. 289-297.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: plane elementary bipartite graph, reducible face, perfect matching, 1-factor, benzenoid graph 
@article{DMGT_2012_32_2_a8,
     author = {Taranenko, Andrej and Vesel, Aleksander},
     title = {1-factors and characterization of reducible faces of plane elementary bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {289--297},
     publisher = {mathdoc},
     volume = {32},
     number = {2},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a8/}
}
TY  - JOUR
AU  - Taranenko, Andrej
AU  - Vesel, Aleksander
TI  - 1-factors and characterization of reducible faces of plane elementary bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 289
EP  - 297
VL  - 32
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a8/
LA  - en
ID  - DMGT_2012_32_2_a8
ER  - 
%0 Journal Article
%A Taranenko, Andrej
%A Vesel, Aleksander
%T 1-factors and characterization of reducible faces of plane elementary bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 289-297
%V 32
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a8/
%G en
%F DMGT_2012_32_2_a8
Taranenko, Andrej; Vesel, Aleksander. 1-factors and characterization of reducible faces of plane elementary bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 2, pp. 289-297. http://geodesic.mathdoc.fr/item/DMGT_2012_32_2_a8/

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