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

Abstract

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

How to cite

top

Andrej 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. [1] S.J. Cyvin and I. Gutman, Kekulé Structures in Benzenoid Hydrocarbons (Springer Verlag, Heidelberg, 1988). Zbl0722.05056
  2. [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. [3] I. Gutman and S.J. Cyvin, Introduction to the Theory of Benzenoid Hydrocarbons (Springer Verlag, Berlin, 1989). Zbl0722.05056
  4. [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. [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. [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. [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. [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. [9] L. Lovász and M.D. Plummer, Matching Theory (North-Holland, 1986). 
  10. [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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.