On The Number Of Dissimilar Pfaffian Orientations Of Graphs

dc.creatorDe Carvalho M.H.
dc.creatorLucchesi C.L.
dc.creatorMurty U.S.R.
dc.date2005
dc.date2015-06-26T14:08:08Z
dc.date2015-11-26T14:07:36Z
dc.date2015-06-26T14:08:08Z
dc.date2015-11-26T14:07:36Z
dc.date.accessioned2018-03-28T21:08:15Z
dc.date.available2018-03-28T21:08:15Z
dc.identifier
dc.identifierRairo - Theoretical Informatics And Applications. , v. 39, n. 1, p. 93 - 113, 2005.
dc.identifier9883754
dc.identifier10.1051/ita:2005005
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-16244369390&partnerID=40&md5=0c80d9ae6de5793d679a536406d3359d
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/93505
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/93505
dc.identifier2-s2.0-16244369390
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1240818
dc.descriptionThe 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.
dc.description39
dc.description1
dc.description93
dc.description113
dc.descriptionDe 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
dc.descriptionDe Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R., Ear decompositions of matching covered graphs (1999) Combinatorial, 19, pp. 151-174
dc.descriptionDe 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
dc.descriptionDe 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
dc.descriptionDe 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
dc.descriptionEdmonds, J., Lovász, L., Pulleyblank, W.R., Brick decomposition and the matching rank of graphs (1982) Combinatorica, 2, pp. 247-274
dc.descriptionFischer, I., Little, C.H.C., A characterisation of Pfaffian near bipartite graphs (2001) J. Comb. Theory B, 82, pp. 175-222
dc.descriptionKasteleyn, P.W., Dimer statistics and phase transitions (1963) J. Math. Phys., 4, pp. 287-293
dc.descriptionLittle, C., A characterization of convertible (0, 1)-matrices (1975) J. Comb. Theory B, 18, pp. 187-208
dc.descriptionLittle, C.H.C., Rendl, F., Operations preserving the Pfaffian property of a graph (1991) J. Austral. Math. Soc. Ser. A, 50, pp. 248-275
dc.descriptionLovász, L., Matching structure and the matching lattice (1987) J. Comb. Theory B, 43, pp. 187-222
dc.descriptionLovász, L., Plummer, M.D., (1986) Matching Theory, 29. , Annals of Discrete Mathematics. Elsevier Science
dc.descriptionMcCuaig, W., Brace generation (2001) J. Graph Theory, 38, pp. 124-169
dc.descriptionRobertson, N., Seymour, P.D., Thomas, R., Permanents, Pfaffian orientations and even directed circuits (1999) Ann. Math., 150, pp. 929-975
dc.descriptionTutte, W.T., Graph theory as I have known it (1998) Oxford Lecture Ser. Math. Appl., 11. , Clarendon Press, Oxford
dc.descriptionVazirani, V.V., Yanakakis, M., Pfaffian orientation of graphs, 0,1 permanents, and even cycles in digraphs (1989) Discrete Appl. Math., 25, pp. 179-180
dc.languageen
dc.publisher
dc.relationRAIRO - Theoretical Informatics and Applications
dc.rightsfechado
dc.sourceScopus
dc.titleOn The Number Of Dissimilar Pfaffian Orientations Of Graphs
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución