Artículos de revistas
On The Number Of Dissimilar Pfaffian Orientations Of Graphs
Registro en:
Rairo - Theoretical Informatics And Applications. , v. 39, n. 1, p. 93 - 113, 2005.
9883754
10.1051/ita:2005005
2-s2.0-16244369390
Autor
De Carvalho M.H.
Lucchesi C.L.
Murty U.S.R.
Institución
Resumen
The dissimilar Pfaffian orientations in planar and biparite graphs are discussed. An orientation D of graph G is Pfaffian if the number of edges of circuit C whose directions in D agree with any prescribed sense of orientation of c is odd. The properties of the matching covered graphs are used to study Pfaffian orientations of the graphs. A property of minimal graphs without a Pfaffian orientation is established and use it to give an alternative proof of the characterization of Pfaffian biparite graphs. 39 1 93 113 De Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R., The perfect matching polytope and solid bricks (2004) J. Combin. Theory B, 92, pp. 319-324 De Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R., Ear decompositions of matching covered graphs (1999) Combinatorial, 19, pp. 151-174 De Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R., On a conjecture of Lovász concerning bricks. I. The characteristic of a matching covered graph (2002) J. Comb. Theory B, 85, pp. 94-136 De Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R., On a conjecture of Lovász concerning bricks. II. Bricks of finite characteristic (2002) J. Comb. Theory B, 85, pp. 137-180 De Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R., Optimal ear decompositions of matching covered graphs (2002) J. Comb. Theory B, 85, pp. 59-93 Edmonds, J., Lovász, L., Pulleyblank, W.R., Brick decomposition and the matching rank of graphs (1982) Combinatorica, 2, pp. 247-274 Fischer, I., Little, C.H.C., A characterisation of Pfaffian near bipartite graphs (2001) J. Comb. Theory B, 82, pp. 175-222 Kasteleyn, P.W., Dimer statistics and phase transitions (1963) J. Math. Phys., 4, pp. 287-293 Little, C., A characterization of convertible (0, 1)-matrices (1975) J. Comb. Theory B, 18, pp. 187-208 Little, C.H.C., Rendl, F., Operations preserving the Pfaffian property of a graph (1991) J. Austral. Math. Soc. Ser. A, 50, pp. 248-275 Lovász, L., Matching structure and the matching lattice (1987) J. Comb. Theory B, 43, pp. 187-222 Lovász, L., Plummer, M.D., (1986) Matching Theory, 29. , Annals of Discrete Mathematics. Elsevier Science McCuaig, W., Brace generation (2001) J. Graph Theory, 38, pp. 124-169 Robertson, N., Seymour, P.D., Thomas, R., Permanents, Pfaffian orientations and even directed circuits (1999) Ann. Math., 150, pp. 929-975 Tutte, W.T., Graph theory as I have known it (1998) Oxford Lecture Ser. Math. Appl., 11. , Clarendon Press, Oxford Vazirani, V.V., Yanakakis, M., Pfaffian orientation of graphs, 0,1 permanents, and even cycles in digraphs (1989) Discrete Appl. Math., 25, pp. 179-180